【数据结构】排序详解二

计数排序

计数排序的基本思想是把每个数出现的次数记录在另外一个数组中，然后我们知道数组下标是有大小的，这样根据数组下标的从小到大去让我们的原数组有序

我们既然要创建一个数组，那么就表明原数组的值的范围不能差别太大，要尽量集中，这样我们创建的数组就可以比较小，就可以满足我们的需求了

void CountSort(int* a, int n) {
	int max = a[0];
	int min = a[0];
	for (int i = 0; i < n; i++) {
		if (a[i] > max) {
			max = a[i];
		}
		if (a[i] < min) {
			min = a[i];
		}
	}
	int num = max - min + 1;
	int* tmp = (int*)malloc(sizeof(int) * num);
	if (tmp == NULL) {
		perror("malloc failed");
		exit(-1);
	}
	memset(tmp, 0, sizeof(int) * num);
	for (int i = 0; i < n; i++) {
		tmp[a[i] - min]++;
	}
	int j = 0;
	for (int i = 0; i < num; i++) {
		while (tmp[i]--) {
			a[j++] = i + min;
		}
	}
}
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

我们创建数组的话肯定不能说下标从0到原数组中的最大值，而范围应该是原数组中从最小值到最大值的那么多范围。这样既缩小了数组的大小，也方便找到原数组中的每个值。

快速排序

快速排序的基本思想就是选取一个key值，把小于key值的放在左边，把大于等于key值的放在右边，这样key就值可以放到它最终该待的位置了，并且同样按照这个思路，去递归处理key左边的值和key右边的值。这就是Hoare大佬最开始发明的排序方法

void QuickSort1(int* a, int begin, int end) {
	if (begin >= end) {
		return;
	}
	int tmp = a[begin];
	int left = begin;
	int right = end;
	while (left < right) {
		while (a[right] >= tmp&&left<right) {
			right--;
		}
		while (a[left] <= tmp&&left<right) {
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[begin]);
	QuickSort1(a, begin, left - 1);
	QuickSort1(a, left + 1, end);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

之后人们觉得这个思路坑很多，很容易写错，于是根据这个思路就发明了挖坑法，就是最初的key值的位置变成了一个坑，从数组的右边找小值放到坑中，坑就更新，再从左边找大值放到右边的新坑中，坑再更新，直到两个指针相遇，然后还是对左边和右边用递归。

void QuickSort2(int* a, int begin, int end) {
	if (begin >= end) {
		return;
	}
	int tmp = a[begin];
	int pit = begin;
	int left = begin;
	int right = end;
	while (left < right) {
		while (left < right && a[right] >= tmp) {
			right--;
		}
		a[pit] = a[right];
		pit = right;
		while (left < right && a[left] <= tmp) {
			left++;
		}
		a[pit] = a[left];
		pit = left;
	}
	a[pit] = tmp;
	QuickSort2(a, begin, pit - 1);
	QuickSort2(a, pit+1, end);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

后人又提出了前后指针法，两个指针都是从最左边开始，找小于key值的，放到左边，直到找不到。慢指针的这个位置就是存放key值的，最后也是递归实现前面的和后面的部分。

void QuickSort3(int* a, int begin, int end) {
	if (begin >= end) {
		return;
	}
	int tmp = a[begin];
	int left = begin;
	int right = begin;
	while (right <= end) {
		if (tmp > a[right]&&++left!=right) {
			Swap(&a[left], &a[right]);
		}
		right++;
	}
	Swap(&a[begin], &a[left]);
	QuickSort3(a, begin, left - 1);
	QuickSort3(a, left + 1, end);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

快速排序可以递归实现，当然也可以非递归实现，这里就要借用栈了，用栈去保存我们要处理的begin和end值，取出来处理完后再保存它的子范围的两个范围值。直到栈为空为止

void QuickSortNonR(int* a, int begin, int end) {
	ST st;
	STInit(&st);
	STPush(&st, end);
	STPush(&st, begin);
	while (!STEmpty(&st)) {
		int left = STTop(&st);
		STPop(&st);
		int right = STTop(&st);
		STPop(&st);
		int tmp = a[left];
		int left1 = left;
		int right1 = right;
		while (left < right) {
			while (left < right && a[right] >= tmp) {
				right--;
			}
			while (left < right && a[left] <= tmp) {
				left++;
			}
			Swap(&a[left], &a[right]);
		}
		Swap(&a[left1], &a[left]);
		if (left1 < left - 1) {
			STPush(&st, left-1);
			STPush(&st, left1);
		}
		if (left+1 < right1) {
			STPush(&st, right1);
			STPush(&st, left + 1);
		}
	}
}
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
29
30
31
32
33

这里的一些有关栈的函数可以去看我以前的博客
链接：栈和队列

归并排序

归并排序也可以用递归实现，先将整个数组的小部分有序，然后有序的范围再扩大，然后使整个数组有序。

void _MergeSort(int* a, int* tmp, int begin, int end) {
	if (begin >= end)
		return;
	int mid = (begin + end) / 2;
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	_MergeSort(a, tmp, begin1, end1);
	_MergeSort(a, tmp, begin2, end2);
	int cur = begin;
	while (begin1 <= end1 && begin2 <= end2) {
		if (a[begin1] < a[begin2]) {
			tmp[cur++] = a[begin1++];
		}
		else {
			tmp[cur++] = a[begin2++];
		}
	}
	while (begin1 <= end1) {
		tmp[cur++] = a[begin1++];
	}
	while (begin2 <= end2) {
		tmp[cur++] = a[begin2++];
	}
	memcpy(a+begin, tmp+begin, sizeof(int)*(end - begin + 1));

}
void MergeSort(int* a, int n) {
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL) {
		perror("malloc failed");
		exit(-1);
	}
	_MergeSort(a, tmp, 0, n - 1);
	free(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
29
30
31
32
33
34
35

能用递归实现当然也能用非递归实现，下标范围是有规律的，所以可以利用这个特性去实现非递归

void MergeSortNonR(int* a, int n) {
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL) {
		perror("malloc failed");
		exit(-1);
	}
	int gap = 1;
	while (gap < n) {
		gap *= 2;
		for (int i = 0; i < n; i += gap) {
			int begin1 = i;
			int begin2 = i + gap / 2;
			int end1 = begin2 - 1;
			int end2 = begin2 + end1 - begin1;
			if (begin2 >= n) {
				break;
			}
			if (end2 >= n) {
				end2 = n - 1;
			}
			int cur = begin1;
			while (begin1 <= end1 && begin2 <= end2) {
				if (a[begin1] < a[begin2]) {
					tmp[cur++] = a[begin1++];
				}
				else {
					tmp[cur++] = a[begin2++];
				}
			}
			while (begin1 <= end1) {
				tmp[cur++] = a[begin1++];
			}
			while (begin2 <= end2) {
				tmp[cur++] = a[begin2++];
			}
			memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));
		}
	}
}
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
29
30
31
32
33
34
35
36
37
38
39