作者：一个喜欢猫咪的的程序员
专栏：《数据结构》
喜欢的话：世间因为少年的挺身而出，而更加瑰丽。 ——《人民日报》
目录
1.排序的概念：
排序就是把集合中的元素按照一定的次序排序在一起。一般来说有升序排列和降序排列2种排序，在算法中有八大基本排序：
算法的优良主要从4个方面进行评测：
- 1.时间复杂度
- 2.空间复杂度
- 3.适用场景
- 4.稳定性
2.八大排序的思路及其细节
2.1直接插入排序
动图演示：
当前n-1个已是有序的情况下，将第n个元素插入进去排序，插入到顺序正确的位置。
将此过程一直重复的话可以可以完成上图的情况。（以数组a为例，来观察一下各个过程）
int a[] = {9,1,2,5,7,4,8,6,3,5};
思路：
用一个变量end=i，利用tmp记录下end位置的下一个位置a[end+1]的值，如果
a[end]>tmp,a[end]=tmp然后end--。最后将tmp的值赋给end+1的位置。
考虑极端情况：
当数组有n个数时，下标最大值为n-1
当end=n-1时，end+1=n（此时造成了越界）
void InsertSort(int* a, int n) {//插入排序 for (int i = 0; i < n - 1; i++) { int end = i; int tmp = a[end + 1]; while (end >= 0) { if (a[end] > tmp) { a[end + 1] = a[end]; end--; } else { break; } } a[end+1] = tmp;//防止end=-1 } }
时间复杂度： O(N^2) 空间复杂度：O ( 1 )
2.2希尔排序
对插入排序的时间复杂度进行分析，得出了以下结论：
- 普通插入排序的时间复杂度最坏情况下为O(N2)，此时待排序列为逆序，或者说接近逆序。
- 普通插入排序的时间复杂度最好情况下为O(N)，此时待排序列为升序，或者说接近升序。
动图演示：
待排序列先进行一次预排序，让待排序列变为接近有序的（接近需要的顺序）,然后再进行一次直接插入排序。
因为直接插入排序前的待排序列已是接近有序的情况了，因此时间复杂度为O（N），只要控制预排序阶段的时间复杂度不超过O(N^2)，那么整体的时间复杂度就比直接插入排序的时间复杂度低了。
希尔排序法又称缩小增量法。希尔排序法的基本思想是：
设定一个gap=n/2，将相距gap位置的两个数作比较，如果前面的小于后面交换以此循环
问题：为什么gap=n/2？
answer：gap越大，数据挪动得越快；gap越小，数据挪动得越慢。前期让gap较大，可以让数据更快得移动到自己对应的位置附近，减少挪动次数。
注：一般情况下，取序列的一半作为增量，然后依次减半，直到增量为1（也可自己设置）。
思路：
单趟排序：当a[end]>a[end+gap]时，将end的值赋给end+gap后end-=gap，在end<0时退出循环
当有n个数时，因为比较是相距gap距离的两个数比较，因此循环次数要小于n-gap次
gap=n每次取半直到最终取到gap=1时，每次取半都是一次一次单趟排序
void ShellSort(int* a, int n) { int gap = n; while (gap > 1) { gap = gap/ 2; for (int i = 0; i < n - gap; i++)//i++并排运算 { int end = i; int tmp = a[end + gap]; while (end >= 0) { if (a[end] > tmp) { //Swap(&a[end], &a[end + gap]); a[end + gap] = a[end]; end -= gap; } else break; } a[end + gap] = tmp;//防止end<0 } } }
希尔排序详细的时间复杂度和空间复杂度：
《数据结构(C语言版)》--- 严蔚敏
《数据结构-用面相对象方法与C++描述》--- 殷人昆
时间复杂度：O ( NlogN ) 空间复杂度：O ( 1 )
平均时间复杂度：O ( N^ 1.3 )
2.3选择排序：
动图演示：
思路：
设两个下标begin和end，begin初始化为0，end初始化为n-1
设置最大值和最小值的下标让他们指向begin
当a[i]的值比a[begin]小，更新min的值，当a[i]的值比a[begin]大，更新max的值
循环走完后确认了最小值的下标，将a[begin]和a[min]进行交换，以及a[end]和a[max交换]
极端情况：
当最大值为数组的第一个时，max=min
时间复杂度：O(N^2) 空间复杂度：O(1)
void SelectSort(int* a, int n) { int begin = 0; int end = n - 1; while (begin < end) { int mini = begin; int maxi = begin; for (int i = begin+1; i <=end; i++) { if (a[i] < a[mini]) { mini = i; } if (a[i] > a[maxi]) { maxi = i; } } Swap(&a[mini], &a[begin]); if (maxi == begin) { maxi = mini; } Swap(&a[maxi], &a[end]); begin++; end--; } }
2.4堆排序
堆排序：（以小堆为例）
堆的分类：
1.升序or降序
2.大堆or小堆
void test2() {//堆排序 int array[] = { 27,15,19,18,28,34,65,49,25,37 }; Heapsort(array, sizeof(array) / sizeof(array[0])); for (int i = 0; i < sizeof(array) / sizeof(array[0]); i++) { printf("%d ", array[i]); } printf("\n"); }
Heapsort函数（堆排序）：
int array[] = { 27,15,19,18,28,34,65,49,25,37 };
需将这个数组进行大堆排列，分为两种调整形式：向上调整和向下调整。、
向上调整和向下调整的思想可以参考我的例外一篇博客：http://t.csdn.cn/UD52X
void Ajustup(HPDataType*a, int child) {//N*logN assert(a); //int child = n - 1; while (child > 0) { int parent = (child - 1) / 2; if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); child = parent; } else { break; } } } void Ajustdown(HPDataType* a, int n,int parent) {//O(N) assert(a); int child = 2 * parent+1; while (child<n) { if (child + 1 < n && a[child] < a[child + 1])// <假设左子树大 { child++; } if (a[child] > a[parent])//>大堆，<为小堆 { Swap(&a[child], &a[parent]); parent = child; child = child * 2 + 1; } else { break; } } }
向上调整和向下调整具体的时间复杂度是多少呢？
向下调整具体的时间复杂度：
假设树高为h
第h层，有2^(h-1）个节点，需要向下调整0次（直接不算，从第h-1层开始算）。
第h-1层，有2^（h-2）个节点，需要向下调整1层。
第h-2层，有2^（h-3）个节点，需要向下调整2层。
......
第4层，有2^3个节点，需要向下调整h-4层。
第3层，有2^2个节点，需要向下调整h-3层。
第2层，有2^1个节点，需要向下调整h-2层。
第1层，有2^0个节点，需要向下调整h-1层。
当h高的次数，最多调整层数为：
F（h）=2^0*（h-1）+2^1*(h-2)+2^2*(h-3)+...+2^(h-3)*2+2^(h-2)*1+2^(h-1)*0 ——①
2*F（h）=2^1*（h-1）+2^2*(h-2)+2^3*(h-3)+...+2^(h-2)*2+2^(h-1)*1+2^(h)*0 ——②
有错位相减②-①可得：
F（h）=-2^0*（h-1）+2^1+2^2+....+2^(h-2)+2^(h-1)
F（h）=2^h-1-h ——③
当树高为h时，节点总个数N为：
N=2^0+2^1+...+2^（h-2）+2^（h-1）
N=2^h-1 ——④
有④可得：h=log（N+1） ——⑤
综合③④⑤可得：
F（N）=N-log（N+1）
- 因此时间复杂度为O（N）
向上调整具体的时间复杂度：
在一层，需要向上调整0次
第二层，向上调整1次
第三层，向上调整2次
...
第h-1层，向上调整h-2次
第h层，向上调整h-1次
F（h）=2^1*1+2^2*2+....+2^(h-1)*(h-1)。
由错位相减可得：
F(N)=2N(1-log(N+1))。
时间复杂度为O（N*logN）
如何实现堆排序
显然向下调整优于向上调整。
先利用Ajustdown排序好数组，然后再用交换Ajustdown实现小堆。
void Heapsort(int*a,int n)//堆排序 {//向上调整 for (int i = 1; i <n; i++) { Ajustup(a, i); } //向下调整 for (int i = (n - 1 - 1) / 2; i >= 0; i--) { Ajustdown(a, n, i); } int end = n - 1; while (end>0) { Swap(&a[0], &a[end]); Ajustdown(a, end, 0); end--; } //N*logN } void test2() {//堆排序 int array[] = { 27,15,19,18,28,34,65,49,25,37 }; Heapsort(array, sizeof(array) / sizeof(array[0])); for (int i = 0; i < sizeof(array) / sizeof(array[0]); i++) { printf("%d ", array[i]); } printf("\n"); }
2.5冒泡排序
动图演示：
代码：
void BubbleSort(int* a, int n) { for (int j = 0; j < n; j++) { for (int i = 1; i < n - j; i++) { if (a[i] < a[i - 1]) { Swap(&a[i],& a[i - 1]); } } } }
