排序算法
排序的概念及其运用
排序的概念
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
全文以升序为例，降序类似
常见排序：
插入排序
直接插入排序是一种简单的插入排序法，其基本思想是：
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。
实际中我们玩扑克牌时，就用了插入排序的思想
直接插入排序:
当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移
其实就是将前面i个数视为一个有序数组，即使是一个也是有序数组，第i+1的数和前一个数比较，如果比它小就不变，比它大就让大的数往后移，一直到遇到比它小的数为止。这里指的是升序。
直接插入排序的特性总结：
元素集合越接近有序，直接插入排序算法的时间效率越高
时间复杂度：O(N2)
空间复杂度：O(1)，它是一种稳定的排序算法
稳定性：稳定
代码实现：
void InsertSort(int* a, int n) { for (int i = 0; i < n-1; ++i) { int end=i; int x=a[i+1]; while(a[end]>x&&end>=0) { a[end+1]=a[end]; end--; } a[end+1]=x; } }
希尔排序(缩小增量排序)
希尔排序法又称缩小增量法。
希尔排序法的基本思想是：先选定一个整数gap，把待排序文件中所有记录分成个组，
所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。
然后，gap不断取小，重复上述分组和排序的工作。
当到达=1时，所有记录在统一组内排好序。
希尔排序的特性总结：
希尔排序是对直接插入排序的优化。
当gap > 1时都是预排序，目的是让数组更接近于有序。
当gap == 1时，数组已经接近有序的了，再让gap等于1以后，
就是前面未优化的直接插入排序方式排序一次，这样就会很快。
这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定
《数据结构(C语言版)》— 严蔚敏
《数据结构-用面相对象方法与C++描述》— 殷人昆
稳定性：不稳定
代码实现：
void ShellSort(int* a, int n) { int gap=n; while(gap>1){ //gap=gap/2;//shell的方式 gap=gap/3+1;//knuth的方式 for (int i = 0; i < n-gap; i++) { //多次预排序+最后一次gap==1直接插入排序 //预排序使得数组更加有序，后面直接排序便可加快效率 int end=i; int x=a[i+gap]; while(a[end]>x&&end>=0) { a[end+gap]=a[end]; end-=gap; } a[end+gap]=x; } } }
选择排序
基本思想：
每一次从待排序的数据元素中选出最小（或最大）的一个元素，
存放在序列的起始位置，直到全部待排序的数据元素排完 。
直接选择排序
在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素
若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，
直到集合剩余1个元素
也就是说，每次遍历都选出最大或者最小的值放到一端，这样到最后就是有序的了。
直接选择排序的特性总结：
直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：不稳定
代码实现：
void SelectSort(int* a, int n) { int begin = 0, end = n - 1; while (begin < end) { int mini = begin, maxi = begin; for (int i = begin; i <= end; ++i) { if (a[i] < a[mini]) mini = i; if (a[i] > a[maxi]) maxi = i; } Swap(&a[begin], &a[mini]); // begin == maxi时，最大被换走了，修正一下maxi的位置 if (begin == maxi) maxi = mini; Swap(&a[end], &a[maxi]); ++begin; --end; } }
这个排序整体来说是最差的排序方式，因为无论什么情况都是时间复杂度O(N2)
堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
前面我们讲述二叉树的时候就已经讲过这个排序方式了
直接选择排序的特性总结：
堆排序使用堆来选数，效率就高了很多。
时间复杂度：O(N*logN)
空间复杂度：O(1)
稳定性：不稳定
skills:
在这里建堆最好使用向下调整来建堆，如果使用向上调整来建堆，
建堆的时间复杂度就要O(N*logN),而向下调整时间复杂度为O(N)，
这些都在http://t.csdn.cn/LcTKm讲过了。
交换排序
基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置
交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
冒泡排序
冒泡排序的特性总结：
冒泡排序是一种非常容易理解的排序
时间复杂度：O(N2)
空间复杂度：O(1)
稳定性：稳定
简单来说：冒泡排序就是在[0,n-1]两两对比选出最大值放到a[n-1]，
再从[0,n-2]先选出最大值放到a[n-2],如此循环下去就排好序了。
冒泡排序最好的情况是，数组本就是有序，此时经过一轮遍历后，
没有发生交换，就可以判断是有序数组了，最好情况的时间复杂度为O(N),
但是一般情况不会是这样，仍需要一个个选出最大值，时间复杂度为O(N2).
代码实现：
void BubbleSort(int* a, int n) { int end = n; while (end > 0) { int exchange = 0; for (int i = 1; i < end; ++i) { if (a[i - 1] > a[i]) { exchange = 1; Swap(&a[i - 1], &a[i]); } } --end; if (exchange == 0) { break; } } }
快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法
其基本思想为：任取待排序元素序列中的某元素作为基准值，
按照该排序码将待排序集合分割成两子序列，
左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，
然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
// 假设按照升序对array数组中[left, right)区间中的元素进行排序 void QuickSort(int array[], int left, int right) { if(right - left <= 1) return; // 按照基准值对array数组的 [left, right)区间中的元素进行划分 int div = partion(array, left, right); // 划分成功后以div为边界形成了左右两部分 [left, div-1] 和 [div+1, right) // 递归排[left, div) QuickSort(array, left, div—1); // 递归排[div+1, right) QuickSort(array, div+1, right); }
我们会发现，这很像二叉树的前序遍历，只不过要注意基准值的改变，以及边界的改变。
将其划分左右两部分的方式主要有两种：
hoare版本
思路：
取最左边的值为keyi，然后R往左走找到比a[keyi]小的值就停，
L往右走找到比a[keyi]大的值就停，然后交换两个值，
继续循环直到二者相遇值为x，把a[keyi]与a[x]交换，
自此keyi左边的值比a[keyi]小，keyi右边的值比a[keyi]大
代码实现：
int Partion1(int* a, int left, int right) { int keyi=left; while(left<right) { while(a[keyi]<=a[right]&&left<right) right--; while (a[keyi]>=a[left]&&left<right) left++; Swap(&a[left],&a[right]); } Swap(&a[keyi],&a[left]); return left; }
挖坑法
思路：
与上面的思路相似，取最左边的值为keyi，
把a[keyi]备份，试想左边这个为坑
然后R往左走找到比a[keyi]小的值就把它放到坑中，
然后L往右走找到比a[keyi]大的值就把它放到坑中，
继续循环直到二者相遇值为x，把备份的a[keyi]放到坑中，
自此keyi左边的值比a[keyi]小，keyi右边的值比a[keyi]大
代码实现：
int Partion2(int* a, int left, int right) { int key = a[left]; int pivot = left; while (left < right) { // 右边找小, 放到左边的坑里面 while (left < right && a[right] >= key) { --right; } a[pivot] = a[right]; pivot = right; // 左边找大，放到右边的坑里面 while (left < right && a[left] <= key) { ++left; } a[pivot] = a[left]; pivot = left; } a[pivot] = key; return pivot; }
前后指针版本
思路：
设置最左值为key，再设置两个指针，一个在前为cur，一个在后为prev。
cur从第二个开始，prev从第一个开始，在前的cur开始往前寻找比key小的值。
找到就停下来和prev+1位置的值交换，因为cur位置的值肯定比key大，
而prev最初的位置是key，所以最后prev所在的位置的值必然是比key小的。
停止的条件是什么呢？是cur指针超出了数组范围。
就这样prev最后所在位置的值与key交换，这样就实现了key左边比key小，key右边比key大。
代码实现：
int Partion3(int* a, int left, int right) { int keyi = left; int prev = left; int cur = prev + 1; while (cur <= right) { if (a[cur] < a[keyi] && ++prev != cur)//这个地方就比较巧妙，把++prev放在这里 //为什么要判断++prev不等于cur呢？因为二者相同就没有交换的价值。 { Swap(&a[cur], &a[prev]); } ++cur; } Swap(&a[prev], &a[keyi]); return prev; }
快速排序优化
三数取中法选key
三数指的是：a[0],a[(n-1)/2],a[n-1],由于a[key]的值是无法预料它的相对大小的，
当想要排升序时，如果是倒序有序的话，就是最坏的情况，
这时如果取首尾中间值为key则变成了最好的情况
代码实现：
int GetMidIndex(int* a, int left, int right) { int middl=left+(right-left)/2; if(left>middl) { if(right>left) return left; else if(right<middl) return middl; else return right; } else//left<=middl { if(right>middl) return middl; else if(right<left) return left; else return right; } }
这个函数可以放在上述所说的三种方法中，只需向其中加以下代码
int mini = GetMidIndex(a, left, right); Swap(&a[mini], &a[left]);
递归到小的子区间时，可以考虑使用插入排序
递归可以想象成满二叉树的结构，越到后面需要递归的次数越多，这样
就使我们萌生一个想法，把后面几次的递归排序换成直接插入排序。
想法是好的，那么怎么实现呢？
这时候就要考虑最后是什么情况了，我们需要它数组递归到个数少的时
候就使用直接插入排序，代码如下：
void QuickSort(int* a, int left, int right) { if (left >= right) return; // 小区间优化，当分割到小区间时，不再用递归分割思路让这段子区间有序 // 对于递归快排，减少递归次数 if (right - left + 1 < 10) { InsertSort(a + left, right - left + 1); } //要注意这里插入排序的左值是数组开始的位置， //右值是需要排序的个数，参考上文讲述的插入排序函数的描述。 else { int keyi = Partion3(a, left, right); // [left, keyi-1] keyi [keyi+1, right] QuickSort(a, left, keyi - 1); QuickSort(a, keyi + 1, right); } }
就这样，我们实现了快速排序的递归实现方法，最主要的是怎么确定key值，
并且使key左边和右边比key小或者大，最后使用递归的方式，
一层层缩小数组使其有序，最后整个数组有序，那么非递归怎么写呢?
快速排序的非递归
在这里我们需要用到一个数据结构----栈
栈的实现我们之前在这里讲过，这里直接使用它的代码就好
栈的实现链接：http://t.csdn.cn/cZzJh
怎么使用？
思路是这样的：
首先将原数组的首末位置按照末先首后的顺序传入栈中
（栈的作用主要是记录边界），然后原数组按照上文讲过的让左边右边
比key大或者小的方法把key放到合适的位置，然后把栈内的已经找到
key合适位置的边界删掉，之后把key+1和end的值传入栈，
begin和key-1的值传入栈，把这个边界里key放到合适的位置就删掉边界，
继续传入key右边的边界和左边的边界，
到了最后第一次的key前面的都有序了，
这时开始key后面的边界开始按照前面所说的
开始把key放到合适的位置，最后栈空了就结束了。
代码实现：
这里我们就只把所用到栈的函数拿出来，如果需要复现的可以到http://t.csdn.cn/cZzJh里把Stack.c和Stack.h文件复制放到源文件下。
void QuickSortNonR(int* a, int left, int right) { ST st; StackInit(&st); StackPush(&st, left); StackPush(&st, right); while (!StackEmpty(&st)) { int end = StackTop(&st); StackPop(&st); int begin = StackTop(&st); StackPop(&st); int keyi = Partion3(a, begin, end); // [begin, keyi-1] keyi [keyi+1, end] if (keyi + 1 < end) { StackPush(&st, keyi+1); StackPush(&st, end); } if (begin < keyi-1) { StackPush(&st, begin); StackPush(&st, keyi-1); } } StackDestroy(&st); }
快速排序总结
在大部分场景下，快速排序的性能都是比较好的，所以才叫快速排序
时间复杂度：O(N*logN)
空间复杂度：O(logN)
稳定性：不稳定
归并排序
基本思想：
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,
该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序列；
即先使每个子序列有序，再使子序列段间有序。
若将两个有序表合并成一个有序表，称为二路归并。
归并排序核心步骤：
思路：
开辟一个新数组存重新排序的结果，原数组不断分半到最后只剩一个元素，
再开始归并，两数比较，小的放前面，大的放后面，这一块就有序了，
随着数组变大，数变多，依旧如此，大的放前面，小的放后面，
一个数组没有数了就把另一个数组没有放的值按顺序放在后面即可。
图示：
由于代码过长不方便图示，故中间比较大小的就省去了，仅示例部分，后面类似
代码实现：
void _MergeSort(int* a, int left, int right, int* tmp) { if (left >= right) { return; } int mid = (left + right) / 2; // [left, mid] [mid+1, right] 有序 _MergeSort(a, left, mid, tmp); _MergeSort(a, mid + 1, right, tmp); int begin1 = left, end1 = mid; int begin2 = mid+1, end2 = right; 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++]; } // tmp 数组拷贝回a for (int j = left; j <= right; ++j) { a[j] = tmp[j]; } } void MergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int)*n); if (tmp == NULL) { printf("malloc fail\n"); exit(-1); } _MergeSort(a, 0, n - 1, tmp); free(tmp); tmp = NULL; }
这就是归并排序的递归实现，其实还有一种非递归方法，
但是并不推荐使用，主要是使用时容易出错，
数组边界容易出问题，
但是还是在这里讲一下：
归并排序的非递归实现：
通过观察数组可以发现，我们递归方法中分割的最后一步，
把数组分成一个个单独的元素，
但是数组里面我们可以把它看作是单个的元素，
直接就是分的最后一步，开始归并就好了，
那么该怎么归并呢？
这里我们就要设置一个变量gap来控制，一次是几个元素进行归并，
这一步是最主要的难点，然后就是这几个数进行归并，
到了后面数不够了怎么办？比如说现在是八个数，
先一一归，然后两两归，最后四四归，这是理想情况，
但如果是九个数呢？最后还多了一个数怎么办？
多的数和后面的归就越界了，排序结果肯定就不对了，
这里所说的就是边界控制问题了，
基于我的代码循环情况，越界情况有两种：
前一个右边界就越界，或者后一个的左边界就越界，那就不用再继续了，说明数组比较完了
后一个右边界越界，那就把它右边界设置为原来整个数组的右边界即可
代码实现：
void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int)*n); if (tmp == NULL) { printf("malloc fail\n"); exit(-1); } int gap = 1; while (gap < n) { for (int i = 0; i < n; i += 2 * gap) { // [i,i+gap-1] [i+gap,i+2*gap-1] int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap - 1; // 核心思想：end1、begin2、end2都有可能越界 // end1越界 或者 begin2 越界都不需要归并 if (end1 >= n || begin2 >= n) { break; } // end2 越界，需要归并，修正end2 if (end2 >= n) { end2 = n- 1; } int index = i; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } // 把归并小区间拷贝回原数组 for (int j = i; j <= end2; ++j) { a[j] = tmp[j]; } } gap *= 2; } free(tmp); tmp = NULL; }
归并排序的特性总结：
归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
时间复杂度：O(N*logN)
空间复杂度：O(N)
稳定性：稳定
计数排序
计数排序，顾名思义使用计数的方式进行排序，它是哈希直接定址法的变形应用。
步骤：
统计相同元素出现次数
根据统计的结果将序列回收到原来的序列中
图示：
这里有一个问题，一定要从0开始吗？
如果有一组数是这样的[1000,1111,1022,1073,1288],给它排序难道要浪费前面一千个空间来记录吗？
当然不需要，像这种集中在一定区域的数，就把它最小的数放在0那，其他的数就映射到x-min上，与从0开始不同的是，这是相对的映射，而那是绝对映射。我们怎么确定要开辟多大的空间来存放数据呢？循环一遍找出最大最小值即可1.
代码实现：
void CountSort(int* a, int n) { int max = a[0], min = a[0]; for (int i = 1; i < n; ++i) { if (a[i] > max) { max = a[i]; } if (a[i] < min) { min = a[i]; } } int range = max - min + 1; int* count = (int*)malloc(sizeof(int)*range); memset(count, 0, sizeof(int)*range); if (count == NULL) { printf("malloc fail\n"); exit(-1); } // 统计次数 for (int i = 0; i < n; ++i) { count[a[i] - min]++; } // 根据次数，进行排序 int j = 0; for (int i = 0; i < range; ++i) { while (count[i]--) { a[j++] = i + min; } } }
计数排序总结：
因为计数排序的适用性不强，故不在后面总结中提及，此处仅作涉猎
在数据比较集中时效率很高，但是适用范围和场景有限，
如果范围较大或者是浮点数就不适用了。
时间复杂度：O(max(N,range))
空间复杂度：O(范围)
稳定性：稳定
排序算法复杂度及稳定性分析
算法复杂度分析前文已经讲述过了，总结参考上图。
稳定性是什么呢？
假定在待排序的记录序列中，存在多个相同的关键字的记录，
若经过排序，这些记录的相对次序保持不变，
就称这种算法是稳定的，否则是不稳定的。
那么前面讲过的排序方式哪些是稳定的、哪些是不稳定的呢.
插入排序：
直接插入排序（稳定）
希尔排序不稳定）
在相同的值预排时可能分到不同的组里导致相对位置改变
选择排序：
选择排序（不稳定）
如果有两个相同的数，一个在首位，这时如果最小的数在另一个的右边，那么相对位置将会改变
堆排序（不稳定）
排升序时，如果最小的数在末尾，而最大数在前，不止一个，那么将最大的数替换后， 最大数的相对1位置也会发生改变
交换排序：
冒泡排序（稳定）
快速排序（不稳定）
有相同元素时相对位置可能会发生变化
归并排序：
归并排序（稳定）
计数排序（不稳定）
归并时，如果相同会先归左边的数，这样会导致相对位置改变
总结
这一篇我们讲述了八大排序算法，包括直接插入排序、希尔排序、直接选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序，并且进行了算法复杂度和稳定性的分析。可是知道理论和死板的重现是远远不够的，还需要刷题来巩固，主要掌握的是这种思想。
respect !
下篇见！
