【数据结构】排序详解一

冒泡排序

其实我们之前就用到过很多次的冒泡排序，它的原理就是相邻的两个元素互换。
我们就想象一下，对于一个初始无序的数组，我们排序第一遍的话（就是从第一个开始，第一个与第二个交换，第二个与第三个交换…第n-1个与第n个交换），这时最大的是不是就到了它合适的位置。下面又是从头开始，只不过这时呢就要排序前n-1个数据了，以此类推，直到还剩两个数据，这时排一遍不就行了嘛。所以我们一共排了n-1回。
现在我们算一下每排一回要比较多少次，排第一回时第一个与第二个比较，一直到第n-1个和第n个比较，这是n-1回，下边还有n-1个数据，这时就比较n-2回，直到最后的1回。

于是我们的代码就有了

void BubbleSort(int* a, int n) {
	for (int i = 0; i < n - 1; i++) {
	int exchange=0;
		for (int j = 0; j < n - 1 - i; j++) {
			if (a[j] > a[j + 1]) {
				int tmp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = tmp;
				exchange=1;
			}
		}
		if(exchange==1){
		break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

我们这里的i跟上面说的一样，循环n-1次，j第一回循环n-1次，后面每回减一，正好根据i加一的特性，直接让它减去个i就可以了

插入排序

插入排序我们在生活中用的最多的可能就是摸扑克牌了，我们要在一个有序的牌中插入一个刚摸的牌，是不是要逐个的比较，然后选择合适的位置，这里就是我们的插入排序了。
现在给定一个数组，第一个数据肯定是有序的，从第二个数据开始，进行插入排序，使两个数据有序，再找第三个，以此类推，直到全部有序。
从第二个元素到第n个元素，一共要循环n-1回，我们每次循环，以升序为例，我们先把第i个元素记下来，如果前面的元素大于它，那么前面的数据往后覆盖，直到找到比它小的数据，把它放在这个数据的前面。

然后我们的代码就有了

void InsertSort(int* a, int n) {
	for (int i = 1; i < n; i++) {
		int tmp = a[i];
		int end = i - 1;
		while (end >= 0) {
			if (a[end] > tmp) {
				a[end + 1] = a[end];
			}
			else {
				break;
			}
			end--;
		}
		a[end + 1] = tmp;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

希尔排序

希尔排序其实本质上就是多次的插入排序，多次的插入排序？可能你会觉得它肯定比插入排序慢吧，其实相反，希尔排序在处理大量数据时快的多
我们知道，插入排序在处理较为有序的数据时是比较快的，因为进行插入排序时只要处理的数据比前面要比较的数据大（以升序为例），就跳出循环就行了
所以我们希尔排序的前几步就是预排序的过程，就是把这一堆数据先排成大致有序。具体步骤就是，隔几个值去插入排序，然后逐步减少这个值，最后让这个值等于一，就是我们的插入排序

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		//gap = gap / 2;
		gap = gap / 3 + 1;

		for (int i = 0; i < n - gap; ++i)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

当然我们这个动图是从中间的数据开始的，只需要把代码改一下就行

void ShellSort(int* a, int n) {
	int gap = n;
	while (gap > 1) {
		gap = gap / 3 + 1;
		for (int i = gap; i < n ; i++) {
 			int tmp = a[i];
			int end = i-gap;
			while (end >= 0) {
				if (tmp < a[end]) {
					a[end + gap] = a[end];
				}
				else {
					break;
				}
				end -= gap;
			}
			a[end + gap] = tmp;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

选择排序

选择排序顾名思义就是一次选出一组数据中最小的那个，把它和第一个交换数据，第一个就排好了，下面找后面中最小的，与第二个交换数据，以此类推，一个一个的就排好了

void SelectSort(int* a, int n) {
	for (int i = 0; i < n - 1; i++) {
		int mini = i;
		for (int j = i + 1; j < n; j++) {
			if (a[j] < a[mini]) {
				mini = j;
			}
		}
		Swap(&a[i], &a[mini]);
	}
}
1
2
3
4
5
6
7
8
9
10
11

当然一次只选一个最小的确实有些浪费，我们也可以同时选出一个最大的，把最大的放到最后一个位置，这样遍历一次不就放好两个值了嘛，这样效率会更高一下

void SelectSort(int* a, int n) {
	int start = 0;
	int end = n - 1;
	while (start < end) {
		int maxi = start;
		int mini = start;
		for (int i = start + 1; i <= end; i++) {
			if (a[i] > a[maxi]) {
				maxi = i;
			}
			if (a[i] < a[mini]) {
				mini = i;
			}
		}
		Swap(&a[start], &a[mini]);
		if (start == maxi) {
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);
		start++;
		end--;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

最后一个if要注意一下，这里为什么要判断呢？因为如果说最大值的下标就为start的话，我们在倒数第二个Swap当中就会把最大值给交换走，此时下标为maxi的数据就不是最大的了，所以我们的maxi要跟着最大值走，最大值被交换到了下标为mini的位置，我们就要修正一下maxi