数据结构动画表示八大排序算法，一看就懂

我们平时玩扑克牌时，摸牌阶段的排序就用到了插入排序的思想

具体实现：

即一般情况下的插入，我们随机列举了一些数字，待插入的数字分为两种情况

（1）待插入的数字是在前面有序数字的中间数，直接比较将x赋值给end+1位置（2）x是最小的一个数，end就会到达-1的位置，最后直接将x赋值给end+1位置

我们一开始并不知道数组是不是有序的，所以我们控制下标，end从0开始，将end+1位置的值始终保存到x中，循环进行单趟排序即可，最后结束时end=n-2，n-1位置的数字保存到x中

总体代码：

直接插入排序总结：

最坏的情况下，每次插入一个数字，前面的数字都要挪动一下，一共需要挪动1+2+3+……+n=n(n+1)/2

③空间复杂度：O(1)

没有借助额外的空间，只用到常数个变量

例如：

①单组排序

和前面的直接插入相同，就是把原来的间隔为1，现在变为gap了，每组分别进行预排序

②多组进行排序

③整个数组进行排序（控制gap）

多次预排序（gap>1）+一次插入排序（gap==1）

（1）gap越大，预排越快，越不接近于有序

（2）gap越小，预排越慢，越接近有序

结果就是：

voidShellSort(int*a,intn){intgap=n;while(gap>1){gap/=2;for(inti=0;i=0){if(a[end]>x){a[end+gap]=a[end];end-=gap;}else{break;}}a[end+gap]=x;}}}希尔排序总结：

每次从数组中选出最大的或者最小的，存放在数组的最右边或者最左边，直到全部有序

我们这里进行了优化，一次排序中，直接同时选出最大的数（a[maxi]）和最小的数（a[mini]）放在最右边和最左边，这样排序效率是原来的2倍

找到最小的数字（a[mini]）和最大的数字（a[maxi]），将它们放在最左边和最右边

ps：其中的begin，end保存记录左右的下标，mini，maxi记录保存最小值和最大值的下标

begin++和end--这样下次就可以排剩下的n-2个数字，再次进行单趟，如此可构成循环，直到begin小于end

整体代码：

直接选择排序总结：

具体实现：、

我们将给定的数组序列，建成一个大堆，建堆从根节点开始就需要多次的向下调整算法

堆的向下调整算法（使用前提）：（1）若想将其调整为小堆，那么根结点的左右子树必须都为小堆。（2）若想将其调整为大堆，那么根结点的左右子树必须都为大堆。

向下调整算法的基本思想：

//向下调整算法//以建大堆为例voidAdJustDown(int*a,intn,intparent){intchild=parent*2+1;//默认左孩子较大while(childa[child])//如果这里右孩子存在，//且更大，那么默认较大的孩子就改为右孩子{child++;}if(a[child]>a[parent]){Swap(&a[child],&a[parent]);parent=child;child=parent*2+1;}else{break;}}}建堆思想：从倒数第一个非叶子节点开始，从后往前，依次将其作为父亲，依次向下调整，一直调整到根的位置

建堆图示：

堆排序的思想：1、建好堆之后，将堆顶的数字与最后一个数字交换2、将最后一个数字不看，剩下的n-1个数字再向下调整成堆再进行第1步3、直到最后只剩一个数停止，这样就排成有序的了

for(intend=n-1;end>0;--end){Swap(&a[end],&a[0]);AdJustDown(a,end,0);}整体代码如下：

一趟过程中，前后两个数依次比较，将较大的数字往后推，下一次只需要比较剩下的n-1个数，如此往复

//优化版本的冒泡排序voidBubbleSort(int*a,intn){intend=n-1;while(end>0){intexchange=0;for(inti=0;ia[i+1]){Swap(&a[i],&a[i+1]);exchange=1;}}if(exchange==0)//单趟过程中，若没有交换过，证明已经有序，没有必要再排序{break;}end--;}}冒泡排序总结：

递归版本

hoare的单趟思想：1、左边作key，右边先走找到比key小的值2、左边后走找到大于key的值3、然后交换left和right的值4、一直循环重复上述123步5、两者相遇时的位置，与最左边选定的key值交换这样就让key到达了正确的位置上

动图演示：

其实本质上是hoare的变形

挖坑法单趟思想：1、先将最左边第一个数据存放在临时变量key中，形成一个坑位2、右边先出发找到小于key的值，然后将该值丢到坑中去，此时形成一个新坑位3、左边后出发找到大于key的值，将该值丢入坑中去，此时又形成一个新的坑位4、一直循环重复123步5、直到两边相遇时，形成一个新的坑，最后将key值丢进去这样key就到达了正确的位置上了

//挖坑法intpartion2(int*a,intleft,intright){intkey=a[left];intpit=left;while(left=key){right--;}a[pit]=a[right];//填坑pit=right;while(left=right)return;intkeyi=partion2(a,left,right);//[left,keyi-1]keyi[keyi+1,right]QuickSort(a,left,keyi-1);QuickSort(a,keyi+1,right);}3、前后指针法（推荐这种写法）前后指针的思想：

1、初始时选定prev为序列的开始，cur指针指向prev的后一个位置，同样选择最左边的第一个数字作为key2、cur先走，找到小于key的值，找到就停下来3、++prev4、交换prev和cur为下标的值5、一直循环重复234步，停下来后，最后交换key和prev为下标的值

intpartion3(int*a,intleft,intright){intprev=left;intcur=left+1;intkeyi=left;while(cur<=right){if(a[cur]=right)return;intkeyi=partion3(a,left,right);//[left,keyi-1]keyi[keyi+1,right]QuickSort(a,left,keyi-1);QuickSort(a,keyi+1,right);}

递归展开图

1、三数取中法

但是这是理想情况，当我们面对一组极端情况下的序列，就是有序的数组，选择左边作为key值的话，那么就会退化为O(N^2)的复杂度，所以此时我们选择首位置，尾位置，中间位置的数分别作为三数，选出中间位置的数，放到最左边，这样选key还是从左边开始，这样优化后，全部都变成了理想情况

//快排的优化//三数取中法intGetMidIndex(int*a,intleft,intright){intmid=(left+right)/2;if(a[left]a[right]){returnright;}else{returnleft;}}else{if(a[mid]>a[left]){returnleft;}elseif(a[mid]

我们可以当划分区间长度小于10的时候，用插入排序对剩下的数进行排序

递归的算法主要是在划分子区间，如果要非递归实现快排，只要使用一个栈来保存区间就可以了。一般将递归程序改成非递归首先想到的就是使用栈，因为递归本身就是一个压栈的过程。

非递归的基本思想：1.申请一个栈，存放排序数组的起始位置和终点位置。2.将整个数组的起始位置和终点位置入栈。3.由于栈的特性是：后进先出，right后进栈，所以right先出栈。定义一个end接收栈顶元素，出栈操作、定义一个begin接收栈顶元素，出栈操作。4.对数组进行一次单趟排序，返回key关键值的下标。5.这时候需要排基准值key左边的序列。如果只将基准值key左边序列的起始位置和终点位置存入栈中，等左边排序完将找不到后边的区间。所以先将右边序列的起始位置和终点位置存入栈中，再将左边的起始位置和终点位置后存入栈中。6.判断栈是否为空，若不为空重复4、5步、若为空则排序完成。

voidQuickSortNonR(int*a,intleft,intright){Stackst;StackInit(&st);StackPush(&st,left);StackPush(&st,right);while(!StackEmpty(&st)){intend=StackTop(&st);StackPop(&st);intbegin=StackTop(&st);StackPop(&st);intkeyi=partion5(a,begin,end);//区间被成两部分了[begin,keyi-1]keyi[keyi+1,end]if(keyi+1begin){StackPush(&st,begin);StackPush(&st,keyi-1);}}StackDestroy(&st);}快速排序的总结：

归并排序的基本思想（分治思想）：

从思想上来说和二叉树很相似，所以我们可以用递归的方法来实现归并排序

代码如下：

我们知道，递归实现的缺点就是会一直调用栈，而栈内存往往是很小的。所以，我们尝试着用循环的办法去实现

由于我们操纵的是数组的下标，所以我们需要借助数组，来帮我们存储上面递归得到的数组下标，和递归的区别就是，递归要将区间一直细分，要将左区间一直递归划分完了，再递归划分右区间，而借助数组的非递归是一次性就将数据处理完毕，并且每次都将下标拷贝回原数组

归并排序的基本思路是将待排序序列a[0…n-1]看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。

但是我们这是理想情况下（偶数个），还有特殊的边界控制，当数据个数不是偶数个时，我们所分的gap组，势必会有越界的地方

第一种情况：

第二种情况：

voidMergeSortNonR(int*a,intn){int*tmp=(int*)malloc(sizeof(int)*n);if(tmp==NULL){printf('mallocfail\n');exit(-1);}intgap=1;while(gap=n||begin2>=n){break;}//end2越界，需要归并，修正end2if(end2>=n){end2=n-1;}intindex=i;while(begin1<=end1&&begin2<=end2){if(a[begin1]

又叫非比较排序，又称为鸽巢原理，是对哈希直接定址法的变形应用

基本思想：

对于给定的任意数组a，我们需要开辟一个计数数组count，a[i]是几，就对count数组下标是几++

这里我们用到了绝对映射，即a[i]中的数组元素是几，我们就在count数组下标是几的位置++，但是对于数据比较聚集，不是从较小的数字开始，例如1001,1002,1003,1004这样的数据，我们就可以用到相对映射的方法，以免开辟数组空间的浪费，count数组的空间大小我们可以用a数组中最大值减去最小值+1来确定（即：range=max-min+1）,我们可以得到count数组下标j=a[i]-min

count[j]中数据是几，说明该数出现了几次，是0就不用拷贝

计数排序总结：

稳定的排序有：直接插入排序、冒泡排序、归并排序

不稳定的排序有：希尔排序、选择排序、堆排序、快速排序、计数排序