冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//冒泡排序，a为vector数组
//从小到大排序
for (int i = 0; i < a.size() - 1; i++)
{
	for (int j = 0; j < a.size() - 1 - i; j++)
	{
		if (a[j] > a[j + 1])
		{
			int temp = a[j];
			a[j] = a[j + 1];
			a[j + 1] = temp;
		}
	}
}

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//选择排序,a为vector数组
int min;//存储每个循环里的最小值的下标
for (int i = 0; i < a.size() - 1; i++)
{
	min = i;
	for (int j = i+1; j < a.size(); j++)
	{
		if (a[j] < a[min])min = j;
	}
	if (min != i)
	{
		int temp = a[i];
		a[i] = a[min];
		a[min] = temp;
	}
}

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template<typename Comparable>
void insertionSort(vector<Comparable>& a)
{
	for (int p = 1; p < a.size(); p++)//a的下标从0开始
	{
		Comparable temp = move(a[p]);
		int j;
		for (j = p; j > 0 && a[j - 1] > temp; j--)
		{
			a[j] = move(a[j - 1]);
		}
		a[j] = move(temp);
	}
}
//------------------------------------------
//进行排序
insertionSort<int>(a);

希尔排序 Shellsort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void shellsort(vector<Comparable>& a)
{
	for (int gap = a.size() / 2; gap > 0; gap/= 2)//增量序列
	{
		for (int i = gap; i < a.size(); i++)//插入排序
		{
			Comparable temp = move(a[i]);
			int j = i;
			for (; j >= gap && a[j - gap] > temp; j -= gap)
			{
				a[j] = move(a[j - gap]);
			}
			a[j] = move(temp);
		}
	}
}

希尔排序