阅读量:2
排序
二、常见排序的实现
8、快速排序的优化
当我们使用快速排序时，最坏的情况就是数组有序，此时的时间复杂度为O(N^2)
最好的情况就是key每次取中位数
所以我们为了避免最坏情况的发生，我们在快速排序的基础上衍生了一种优化的方法叫做三数取中
还有一种方法是随机选key，但随机选key的效果不如三数取中
int GetMidIndex(int* a, int left, int right) { int mid = (left + right) / 2; if (a[left] < a[mid]) { if (a[mid] < a[right]) return mid; else if (a[left] < a[right]) return right; else return left; } else { if (a[mid] > a[right]) return mid; else if (a[left] > a[right]) return right; else return left; } } 将三个比较出中间的数字作为key然后换到left上，进行partsort
在每个partsort的最前边加上这条语句，就优化了这个快速排序的结构
int PartSort(int* a, int left, int right) { int midi = GetMidIndex(a, left, right); Swap(&a[left], &a[midi]); ...... } 9、非递归快速排序
（1）基本思想
前边我们讲的快速排序是基于递归条件下实现的，但我们知道，递归会消耗栈上的空间，并且栈上的空间比较小，不能实现大量数据的快速排序，所以我们要将这个过程放在空间更大的堆上，也就是使用栈来实现
栈的作用就是存储区间，这个区间由两个整数组成，通过出入栈来模拟递归的过程
（2）代码实现
这里需要包含一下以前我们写过的栈的头文件
void QuickSortNonR(int* a, int left, int right) { Stack st; StackInit(&st); StackPush(&st,right); StackPush(&st, left); while (!StackEmpty(&st)) { int left = StackTop(&st); StackPop(&st); int right = StackTop(&st); StackPop(&st); //取出区间 int keyi = PartSort1(a, left, right); //通过keyi将数据区间一分为二 if (keyi + 1 < right) { StackPush(&st, right); StackPush(&st, keyi + 1); } if (left < keyi - 1) { StackPush(&st, keyi - 1); StackPush(&st, left); } //存入区间 } StackDestroy(&st); } 
（3）时间复杂度
同递归方式的快速排序，为O(log₂N * N)
（4）空间复杂度
同递归方式的快速排序，为O(log₂N)
10、归并排序
（1）基本思想
将一个待排序的序列分为若干个子序列，每个子序列都是有序的，然后再将有序的序列合并为整体的有序序列
（2）代码实现
void _MergeSort(int* a, int left, int right, int* tmp) { if (left == right) return; //找到中间下标 int midi = (left + right) / 2; //一分为二二分为四的分开 _MergeSort(a, left, midi, tmp); _MergeSort(a, midi + 1, right, tmp); int begin1 = left, end1 = midi; int begin2 = midi + 1, end2 = right; //i用来记录容器数组中对应的下标 int i = left; //将两个数组中按升序归并到容器数组中 while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) tmp[i++] = a[begin1++]; else tmp[i++] = a[begin2++]; } //如果左右两个区间的数字还没有全部入到容器数组中，将它们按顺序输入 while (begin1 <= end1) tmp[i++] = a[begin1++]; while (begin2 <= end2) tmp[i++] = a[begin2++]; //将容器数组复制到原来的数组上 memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1)); } void MergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); _MergeSort(a, 0, n - 1, tmp); free(tmp); } 
（3）时间复杂度
归并排序分为两个过程
一是分解过程，这是一个类二叉树的过程，由中间下标分为两个区间，再分为四个区间，以此类推，此过程的时间复杂度是O(log₂N)
二是合并过程，合并过程中需要遍历整个数组，找到谁大谁小然后排序，这个过程的时间复杂度是O(N)
整个过程的时间复杂度就是O(N*log₂N)
（4）空间复杂度
该过程需要在堆上开辟n个空间，以及递归所需要的log₂n个在栈上的空间，由于对于n来说log₂n很小，所以它的空间复杂度为O(N)
11、非递归归并排序
（1）基本思想
与快速排序相同，递归方式的归并排序需要使用栈中空间，在处理大量数据时空间不够，所以我们可以用循环的方法减少栈的使用，这就是非递归的归并排序
（2）代码实现
void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); int gap = 1; while (gap < n) { int j = 0;//作为tmp的下标 for (int i = 0; i < n; i += 2*gap)//每次跳过两组数据 { //这里的间隔差gap，每次比较两组数据 int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + gap * 2 - 1; //以下同上 if (end1 >= n || begin2 >= n) break; if (end2 >= n) end2 = n - 1; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) tmp[j++] = a[begin1++]; else tmp[j++] = a[begin2++]; } while (begin1 <= end1) tmp[j++] = a[begin1++]; while (begin2 <= end2) tmp[j++] = a[begin2++]; memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1)); } gap *= 2;//while结束后把间隔调两倍 } free(tmp); } 
（3）时间复杂度
for循环每次gap*=2，时间复杂度为O(log₂N)，for循环中遍历了一遍数组，时间复杂度为O(N)
总的时间复杂度为O(N * log₂N)
（4）空间复杂度
申请了堆上的n个空间，空间复杂度为O(N)
12、非比较排序
（1）基本思想
计数排序是一种非比较排序，实现过程中不需要任何的比较
第一步：统计相同元素出现的次数
第二步：根据统计的结果将序列回收到原来的序列当中
这个排序适用于数据比较集中的序列
（2）代码实现
void CountSort(int* a, int n) { int min, max; min = max = a[0]; for (int i = 0; i < n; i++) { if (a[i] > max) max = a[i]; if (a[i] < min) min = a[i]; } int range = max - min + 1; //找到这一组数据中最大和最小的数相减得出这组数据的范围 int* countA = (int*)malloc(sizeof(int) * range); memset(countA, 0, sizeof(int)*range); //创建一个在堆上的数组作为计数数组，大小为这组数据的范围，将其中的元素全部重置为0 for (int i = 0; i < n; i++) countA[a[i] - min]++; //将每个数字出现的次数记录 int k = 0; for (int i = 0; i < range; i++) { while (countA[i]--) a[k++] = i + min; } }//下标加上整个数组的最小值就是当前数据的大小，countA为0时退出循环，不为0就记录下来 
（3）时间复杂度
找出最大最小值需要遍历一遍数组，记录数字走for循环中range
所以时间复杂度为O(N+range），当数据比较集中时，时间复杂度接近O(N)
到底是O(N）还是O(range）取决于它们俩哪个大
（4）空间复杂度
在堆上开辟了range个空间，空间复杂度为O(range），当数据比较集中时，空间复杂度接近O(1)
三、各个排序方法所用时间的比较
1、代码实现
void TestOP() { srand(time(0)); const int N = 100000; int* a1 = (int*)malloc(sizeof(int) * N); int* a2 = (int*)malloc(sizeof(int) * N); int* a3 = (int*)malloc(sizeof(int) * N); int* a4 = (int*)malloc(sizeof(int) * N); int* a5 = (int*)malloc(sizeof(int) * N); int* a6 = (int*)malloc(sizeof(int) * N); int* a7 = (int*)malloc(sizeof(int) * N); int* a8 = (int*)malloc(sizeof(int) * N); for (int i = 0; i < N; ++i) { a1[i] = rand();//取随机值 a2[i] = a1[i]; a3[i] = a1[i]; a4[i] = a1[i]; a5[i] = a1[i]; a6[i] = a1[i]; a7[i] = a1[i]; a8[i] = a1[i]; //赋值给所有数据 } int begin1 = clock(); InsertSort(a1, N); int end1 = clock(); //clock是一个函数，用于记录当前时间点，在开始时记录一下，在结束后记录一下 //得出的时间差就是这个排序所用的时间 int begin2 = clock(); ShellSort(a2, N); int end2 = clock(); int begin3 = clock(); BubbleSort(a3, N); int end3 = clock(); int begin4 = clock(); SelectSort(a4, N); int end4 = clock(); int begin5 = clock(); HeapSort(a5, N); int end5 = clock(); int begin6 = clock(); QuickSort(a6, 0, N - 1); int end6 = clock(); int begin7 = clock(); MergeSort(a7, N); int end7 = clock(); int begin8 = clock(); CountSort(a8, N); int end8 = clock(); printf("InsertSort:%d\n", end1 - begin1); printf("ShellSort:%d\n", end2 - begin2); printf("BubbleSort:%d\n", end3 - begin3); printf("SelcetSort:%d\n", end4 - begin4); printf("HeapSort:%d\n", end5 - begin5); printf("QuickSort:%d\n", end6 - begin6); printf("MergeSort:%d\n", end7 - begin7); printf("CountSort:%d\n", end8 - begin8); free(a1); free(a2); free(a3); free(a4); free(a5); free(a6); free(a7); free(a8); } 2、分析
当数据给到10W个时，我们可以明显看出各个排序的差距
最拉胯的就是冒泡排序，跟其他排序所用时间都不在一个量级上
然后就是直接插入以及选择插入
然后就是希尔排序、堆排序、快速排序、归并排序
因为随机数的生成是由时间戳实现的，两个随机数之间差的并不多，所以范围比较集中，这就使得计数排序超级快
四、各个排序的稳定性
1、基本概念
稳定性好就是一个序列中存在着两个即两个以上的相同数据，这两个数据在排序前后相对位置不变，反之就是不好
这里的前后相对位置不变不是指它们两个数据一直待在原来的位置，而是前边的数字a1在排列后还在后边的数字a2前边，而不是跑到它的后边了
2、各个排序的稳定性复杂度一览表
| 排序方法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(N^2) | O(N) | O(N^2) | O(1) | 稳定 |
| 简单选择排序 | O(N^2) | O(N^2) | O(N^2) | O(1) | 不稳定 |
| 直接插入排序 | O(N^2) | O(N) | O(N^2) | O(1) | 稳定 |
| 希尔排序 | O(N ^log₂N)~O(N ^2) | O(N^1.3) | O(N^2) | O(1) | 不稳定 |
| 堆排序 | O(N^log₂N) | O(N^log₂N) | O(N^log₂N) | O(1) | 不稳定 |
| 归并排序 | O(N^log₂N) | O(N^log₂N) | O(N^log₂N) | O(N) | 稳定 |
| 快速排序 | O(N^log₂N) | O(N^log₂N) | O(N^2) | O(log₂N)~O(N) | 不稳定 |
感谢观看
