目录
前言
常见排序算法的实现
.插入排序
.希尔排序
.选择排序
4.堆排序
5.冒泡排序
6.快速排序
6.hoa版本
6.挖坑法
6.前后指针法
6.4快速排序优化
6.5快速排序非递归实现
7.归并排序
7.递归实现
7.非递归实现
8.计数排序(了解)
排序算法复杂度及稳定性分析
前言
所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
生活中各种地方都需要用到排序，所以学好排序算法是非常重要的。
排序分为内部排序和外部排序。
内部排序：数据元素全部放在内存中的排序。外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
这部分主要是内部排序。排序讲解都以升序为例。
常见的排序算法：
//排序实现的接口//插入排序voidInsrtSort(int*a,intn);//希尔排序voidShllSort(int*a,intn);//选择排序voidSlctSort(int*a,intn);//堆排序voidAdjustDwon(int*a,intn,introot);voidHapSort(int*a,intn);//冒泡排序voidBubblSort(int*a,intn);//快速排序递归实现//快速排序hoa版本intPartSort(int*a,intlft,intright);//快速排序挖坑法intPartSort(int*a,intlft,intright);//快速排序前后指针法intPartSort(int*a,intlft,intright);voidQuickSort(int*a,intlft,intright);//快速排序非递归实现voidQuickSortNonR(int*a,intlft,intright);//归并排序递归实现voidMrgSort(int*a,intn);//归并排序非递归实现voidMrgSortNonR(int*a,intn);//计数排序voidCountSort(int*a,intn);
常见排序算法的实现
.插入排序
思想：
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
实际中我们玩扑克牌时，就用了插入排序的思想：
演示过程动图：
单趟：若数组(arr)除最后一个元素外其余全部有序，设最后一个元素的下标为i，将arr[i]与前面的元素比较，比他小则前面的元素向右移动，比他小则在该元素的后面插入。
复合：因为不知道数组中得到前几个元素是已经有序的，所以直接从第二个元素开始执行插入排序，单个过程与上述相同，将每个元素都进行一次插入排序。
代码如下：
//插入排序voidInsrtSort(int*a,intn){ assrt(a); inti=0; for(i=0;in-;i++)//因为x元素位置是i的下一个位置，为防止x越界，需要使in- { intnd=i;//已经有序的最后一个元素(一个元素不需要排序，所以默认从0开始) intx=a[nd+];//需要排序的元素//单趟 whil(nd=0) {//若前一个数字小于x，则需将他向右移动 if(a[nd]x) { a[nd+]=a[nd];//继续判断前面的元素 --nd; }//前面元素小于x ls { bak; } }//将x插入正确位置(两种情况)//.前面的数字小于x//.前面的数字都大于x，x放在下标为0处 a[nd+]=x; }}
直接插入排序的特性总结：
元素集合越接近有序，直接插入排序算法的时间效率越高时间复杂度：O(N^)空间复杂度：O()，它是一种稳定的排序算法稳定性：稳定.希尔排序
希尔排序法又称缩小增量法。
基本思想：
先选定一个整数gap，把待排序文件中所有记录分成gap个组，所有距离为gap的记录分在同一组内，并对每一组内的元素进行排序。
然后将gap逐渐减小重复上述分组和排序的工作。
当到达gap=时，所有元素在统一组内排好序。
静态图演示：
动图演示：
这里重要的是理解分组思想，每一个组其实就是一个插入排序，相当于进行多次插入排序。
代码如下：
//希尔排序voidShllSort(int*a,intn){ assrt(a); intgap=n; whil(gap) { //gap/=; gap=gap/+; for(inti=0;in-gap;i++) { intnd=i; intx=a[nd+gap]; whil(nd=0) { if(a[nd]x) { a[nd+gap]=a[nd]; nd-=gap; } ls { bak; } } a[nd+gap]=x; } }}
希尔排序的特性总结：
希尔排序是对直接插入排序的优化。当gap时都是预排序，目的是让数组更接近于有序。当gap==时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，这里不深究。时间复杂度O(N^.5)空间复杂度O()稳定性：不稳定。.选择排序
基本思想：
第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始(末尾)位置，
然后选出次小(或次大)的一个元素，存放在最大(最小)元素的下一个位置，
重复这样的步骤直到全部待排序的数据元素排完。
动图演示：
代码入下：
这里我们可以进行一个优化，最小值和最大值同时选，然后将最小值与起始位置交换，将最大值与末尾位置交换。
//选择排序voidSlctSort(int*a,intn){ assrt(a); intbgin=0;//保存数组的起始位置 intnd=n-;//保存换数组的末尾位置 whil(bginnd) { intmaxi=bgin;//保存最大元素下标 intmini=bgin;//保存最小元素下标//遍历数组寻找最小和最大元素 for(inti=bgin;i=nd;i++) { if(a[i]a[mini]) { mini=i; } if(a[i]a[maxi]) { maxi=i; } }//将最小元素交换到起始位置 Swap(a+bgin,a+mini);//判断最大值的位置是否在起始位置 if(maxi==bgin) { maxi=mini; }//将最大元素交换到末尾位置 Swap(a+nd,a+maxi);//移动数组起始和末尾位置 bgin++; nd--; }}
注意：
在进行最小值和最大值同时交换时也会出现一个问题，
如果最大值在起始位置的时候，交换了最小值之后，最大值就被交换到了min的位置，
如果继续交换max，就会将最小值交换到末尾位置。
所以，在每次交换了最小值之后应该判断一下最大值是否在起始位置，如果在需要将max赋值为min。
直接选择排序的特性总结：
直接选择排序思考非常好理解，但是效率不是很好(不论数组是否有序都会执行原步骤)。实际中很少使用时间复杂度：O(N^)空间复杂度：O()稳定性：不稳定4.堆排序
堆排序即利用堆的思想来进行排序，总共分为两个步骤：
.建堆
升序：建大堆降序：建小堆
.利用堆删除思想来进行排序建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。
这里以升序为例：
首先应该建一个大堆，不能直接使用堆来实现。可以将需要排序的数组看作是一个堆，但需要将数组结构变成堆。我们可以从堆从下往上的第二行最右边开始依次向下调整直到调整到堆顶，这样就可以将数组调整成一个堆，且如果建立的是大堆，堆顶元素为最大值。然后按照堆删的思想将堆顶和堆底的数据交换，但不同的是这里不删除最后一个元素。这样最大元素就在最后一个位置，然后从堆顶向下调整到倒数第二个元素，这样次大的元素就在堆顶，重复上述步骤直到只剩堆顶时停止。
动图演示：
注意：实际中并没有删除堆中元素，图中为了方便表示，将交换后的位置画成了空。
代码如下：
//堆排序voidAdjustDown(int*a,intn,introot)//向下调整{ assrt(a); intpant=root; intchild=pant*+; whil(childn) { if(child+na[child+]a[child]) { child++; } if(a[child]a[pant]) { Swap(a[child],a[pant]); pant=child; child=pant*+; } ls { bak; } }}voidHapSort(int*a,intn){ assrt(a);//建堆 for(inti=(n--)/;i=0;i--) { AdjustDown(a,n,i); }//交换 for(inti=n-;i0;i--) { Swap(a[i],a[0]); AdjustDown(a,i,0); }}
直接选择排序的特性总结：
堆排序使用堆来选数，效率就高了很多。时间复杂度：O(N*logN)空间复杂度：O()稳定性：不稳定5.冒泡排序
冒泡排序应该是我们最熟悉的排序了，在C语言阶段我们就学习了冒泡排序。
他的思想也非常简单：
两两元素相比，前一个比后一个大就交换，直到将最大的元素交换到末尾位置。这是第一趟
一共进行n-趟这样的交换将可以把所有的元素排好。
(n-趟是因为只剩两个元素时只需要一趟就可以完成)
动图演示：
代码如下：
//冒泡排序voidBubblSort(int*a,intn){ inti=0; intflag=0;//n-趟排序 for(i=0;in-;i++) { intj=0;//一趟冒泡排序 for(j=0;jn-i-;j++) { if(a[j]a[j+]) { Swap(a[j],a[j+]); flag=; } }//若某一趟排序中没有元素交换则说明所有元素已经有序，不需要再排序 if(flag==0) { bak; } }}
冒泡排序的特性总结：
冒泡排序是一种非常容易理解的排序时间复杂度：O(N^)空间复杂度：O()稳定性：稳定6.快速排序
这里是排序算法的重点了，非常重要！
快速排序是Hoa于96年提出的一种二叉树结构的交换排序方法，
其基本思想为：
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
6.hoa版本
具体思路是：
选定一个基准值，最好选定最左边或者最右边，选中间会给自己找麻烦。确定两个指针lft和right分别从左边和右边向中间遍历数组。如果选最右边为基准值，那么lft指针先走，如果遇到大于基准值的数就停下来。然后右边的指针再走，遇到小于基准值的数就停下来。交换lft和right指针对应位置的值。重复以上步骤，直到lft=right，最后将基准值与lft(right)位置的值交换。这样基准值左边的所有数都比他小，而他右边的数都比他大，从而他所在的位置就是排序后的正确位置。
之后再递归排以基准值为界限的左右两个区间中的数，当区间中没有元素时，排序完成。
动图演示：
这里选定基准值为最右边的元素。
单趟图解：
继续按照上述步骤进行。。。
代码如下：
//快速排序hoa版本intPartSort(int*a,intlft,intright){ intky=right;//选定基准值 whil(lftright) { //选右边为基准值，左指针先走whil(lftrighta[lft]=a[ky]) { lft++; }//右指针再走whil(lftrighta[right]=a[ky]) { right--; } Swap(a[lft],a[right]); } Swap(a[lft],a[ky]); turnlft;}voidQuickSort(int*a,intlft,intright){ if(lft=right) { turn; } intkyi=PartSort(a,lft,right); QuickSort(a,lft,kyi-); QuickSort(a,kyi+,right); }
6.挖坑法
挖坑法与上面的方法类似。
具体思路是：
先将选定的基准值(最左边)直接取出，然后留下一个坑，当右指针遇到小于基准值的数时，直接将该值放入坑中，而右指针指向的位置形成新的坑位，然后左指针遇到大于基准值的数时，将该值放入坑中，左指针指向的位置形成坑位，重复该步骤，直到左右指针相等。最后将基准值放入坑位之中。之后也是以基准值为界限，递归排序基准值左右区间。
动图演示：
这里不再单趟演示该过程。。。
代码如下：
//快速排序挖坑法intPartSort(int*a,intlft,intright){ intky=a[lft];//取出基准值 inthol=lft;//保存坑的位置 whil(lftright) { whil(lftrighta[right]=ky) { right--; } a[hol]=a[right]; hol=right; whil(lftrighta[lft]=ky) { lft++; } a[hol]=a[lft]; hol=lft; } a[hol]=ky; turnhol;}voidQuickSort(int*a,intlft,intright){ if(lft=right) { turn; } intkyi=PartSort(a,lft,right); QuickSort(a,lft,kyi-); QuickSort(a,kyi+,right); }
6.前后指针法
前后指针法是一个新思路，不太好理解，但是代码比较简单。
具体思路是：
选定基准值，定义pv和cur指针(cur=pv+)cur先走，遇到小于基准值的数停下，然后将pv向后移动一个位置将pv对应值与cur对应值交换重复上面的步骤，直到cur走出数组范围最后将基准值与pv对应位置交换递归排序以基准值为界限的左右区间动图演示：
单趟演示：
代码如下：
//快速排序前后指针法intPartSort(int*a,intlft,intright){ //.将基准值定在lft intkyi=lft; intpv=lft; intcur=lft+; whil(cur=right) { if(a[cur]a[kyi]++pv!=cur) { Swap(a[pv],a[cur]); } cur++; } Swap(a[pv],a[kyi]); //.将基准值定在right /*intkyi=right; intpv=lft-; intcur=pv+; whil(cur=right) { if(a[cur]a[kyi]++pv!=cur) { Swap(a[cur],a[pv]); } cur++; } Swap(a[kyi],a[++pv]); turnpv;*/}voidQuickSort(int*a,intlft,intright){ if(lft=right) { turn; } intkyi=PartSort(a,lft,right); QuickSort(a,lft,kyi-); QuickSort(a,kyi+,right);}
6.4快速排序优化
上面就是快速排序递归的三种方法。
但是上面的程序还有一些缺陷：
在基准值的选择上，如果选择的基准值为恰好为最小值，会进行不必要的递归。
在排序大量有序数据或者接近有序数据时，效率会比较低，甚至可能会出现程序崩溃的情况。
这是因为在排序有序数据时，快速排序的递归调用次数过多，会导致栈溢出的情况。
为了解决这些问题，这里有两种优化方法：
三数取中法选基准值递归到小的子区间时，可以考虑使用插入排序
.即在在起始位置，中间位置，末尾位置中选出中间值，作为基准值。
//三数取中intMidIndx(int*a,intlft,intright){ intmid=(lft+right)/; //防止mid越界 //intmid=lft+(right-lft)/; if(a[lft]a[right]) { if(a[mid]a[lft]) { turnlft; } lsif(a[mid]a[right]) { turnright; } ls { turnmid; } } ls { if(a[mid]a[lft]) { turnlft; } lsif(a[mid]a[right]) { turnright; } ls { turnmid; } }}
.类似于二叉树，每个子树都会进行一次递归调用，越到下面递归调用会越多。为了减少递归调用，当到递归到下层时，我们可以使用其他的排序来替代。这里我们使用插入排序。
以前后指针法为例，完整代码为：
//快速排序前后指针法intPartSort(int*a,intlft,intright){ intmid=MidIndx(a,lft,right); //将基准位置调整至最左边 Swap(a[mid],a[lft]); //.将基准值定在lft intkyi=lft; intpv=lft; intcur=lft+; whil(cur=right) { if(a[cur]a[kyi]++pv!=cur) { Swap(a[pv],a[cur]); } cur++; } Swap(a[pv],a[kyi]); //.将基准值定在right /*intkyi=right; intpv=lft-; intcur=pv+; whil(cur=right) { if(a[cur]a[kyi]++pv!=cur) { Swap(a[cur],a[pv]); } cur++; } Swap(a[kyi],a[++pv]); turnpv;*/}voidQuickSort(int*a,intlft,intright){ if(lft=right) { turn; } //小区间优化，，减少递归次数 if(right-lft+0) { InsrtSort(a+lft,right-lft+); } ls { intkyi=PartSort(a,lft,right); QuickSort(a,lft,kyi-); QuickSort(a,kyi+,right); }}
6.5快速排序非递归实现
快速排序非递归实现，需要借助栈，栈中存放的是需要排序的左右区间。
而且非递归可以彻底解决栈溢出的问题。
其实他的思想与递归是类似的：
具体思想：
将数组左右下标入栈，若栈不为空，两次取出栈顶元素，分别为闭区间的左右界限将区间中的元素按照前后指针法排序(其余两种也可)得到基准值的位置再以基准值为界限，若基准值左右区间中有元素，则将区间入栈重复上述步骤直到栈为空代码如下：
//快速排序非递归实现voidQuickSortNonR(int*a,intlft,intright){//创建栈 Stackst; StackInit(st);//原始数组区间入栈 StackPush(st,right); StackPush(st,lft);//将栈中区间排序 whil(!StackEmpty(st)) {//注意：如果right先入栈，栈顶为lft lft=StackTop(st); StackPop(st); right=StackTop(st); StackPop(st);//得到基准值 intmid=PartSort(a,lft,right);//以基准值为分割点，形成左右两部分 if(rightmid+) { StackPush(st,right); StackPush(st,mid+); } if(lftmid-) { StackPush(st,mid-); StackPush(st,lft); } } StackDstroy(st);}
快速排序的特性总结：
快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序时间复杂度：O(N*logN)空间复杂度：O(logN)稳定性：不稳定7.归并排序
7.递归实现
基本思想：
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（DividandConqur）的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
若将两个有序表合并成一个有序表，称为二路归并。
归并排序核心步骤：
按照其算法思想：
首先应在数组中找出有序的序列，但数组是否有序编译器可不知道。
所以可以将数组划分，一分二，二分四......直到每个序列中只有一个数字。
一个数字总可以认为他是有序的吧。
最后将同时划分的序列合并。
动图演示：
代码如下：
void_MrgSort(int*a,intlft,intright,int*tmp){//区间中没有元素时不再合并 if(lft=right) { turn; }//划分数组，每次一分为二 intmid=(lft+right)/; _MrgSort(a,lft,mid,tmp);//划分左区间 _MrgSort(a,mid+,right,tmp);//划分右区间//合并有序序列 intbgin=lft,nd=mid;//有序序列 intbgin=mid+,nd=right;//有序序列 inti=lft; whil(bgin=ndbgin=nd)//注意结束条件为一个序列为空时就停止 { if(a[bgin]a[bgin]) { tmp[i++]=a[bgin++]; } ls { tmp[i++]=a[bgin++]; } }//两序列不可能同时为空，将剩余元素合并 whil(bgin=nd) { tmp[i++]=a[bgin++]; } whil(bgin=nd) { tmp[i++]=a[bgin++]; }//将合并后的序列拷贝到原数组中//在这里拷贝的原因是保证返回到上一层递归后两个子序列中的元素是有序的 intj=0; for(j=lft;j=right;j++) { a[j]=tmp[j]; }}//归并排序递归实现voidMrgSort(int*a,intn){//因为需要将两个有序序列合并，需借助额外数组 int*tmp=(int*)malloc(sizof(int)*n); if(tmp==NULL) { prror("malloc"); xit(-); } _MrgSort(a,0,n-,tmp); f(tmp); tmp=NULL;}
7.非递归实现
非递归实现的思想与递归实现的思想是类似的。
不同的是，这里的序列划分过程和递归是相反的，不是一次一分为二，而是先个元素一组，再个元素一组，4个元素一组....直到将所有的元素归并完。
静态图示：
代码如下：
//归并排序非递归实现voidMrgSortNonR(int*a,intn){ int*tmp=(int*)malloc(sizof(int)*n); if(tmp==NULL) { prror("malloc"); xit(-); }//初始化每组的元素个数为 intgap=; whil(gapn)//gap为n时就只有一个序列了，所以gapn {//归并每两组归并一次 inti=0; for(i=0;in;i+=*gap)//两组中的元素个数为*gap {//控制两组边界 intbgin=i,nd=i+gap-; intbgin=i+gap,nd=i+*gap-; //当原数组中元素个数不是^n时，最后两组组会出现元素不匹配的情况//情况：nd=n或bgin=n,即最后两组中只有一组有元素，则不需归并 if(nd=n
bgin=n) { bak; }//情况：nd=n，即最后两组中，第二组元素个数小于第一组，则需要调整第二组边界 if(nd=n) { nd=n-; }//归并intj=i; whil(bgin=ndbgin=nd) { if(a[bgin]a[bgin]) { tmp[j++]=a[bgin++]; } ls { tmp[j++]=a[bgin++]; } } whil(bgin=nd) { tmp[j++]=a[bgin++]; } whil(bgin=nd) { tmp[j++]=a[bgin++]; } //将归并后的有序序列拷贝到原数组中 for(j=i;j=nd;j++) { a[j]=tmp[j]; } }//每次循环每组元素个数增大倍 gap*=; } f(tmp); tmp=NULL;}
归并排序的特性总结：
归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。时间复杂度：O(N*logN)空间复杂度：O(N)稳定性：稳定8.计数排序(了解)
思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。操作步骤.统计相同元素出现次数.根据统计的结果将序列回收到原来的序列中
动图演示：
代码如下：
//计数排序voidCountSort(int*a,intn){//创建计数数组，数组大小为原数组中最大值-最小值+ intmax=a[0],min=a[0]; inti=0; for(i=0;in;i++) { if(a[i]max) { max=a[i]; } if(a[i]min) { min=a[i]; } } intrang=max-min+; int*count=(int*)malloc(sizof(int)*rang);//初始化计数数组为0 mmst(count,0,rang*4); //统计次数 for(i=0;in;i++) { count[a[i]-min]++; }//根据次数，进行排序 intj=0; for(i=0;irang;i++) { whil(count[i]--) { a[j++]=i+min; } }}
注意：计数排序在排负数时，可将负数的类型转化成unsigndint。
数组中元素有正有负的情况时不适用计数排序。
计数排序的特性总结：
计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。时间复杂度：O(MAX(N,范围))空间复杂度：O(范围)稳定性：稳定排序算法复杂度及稳定性分析
注：在特殊情况下，排序的时间复杂度会发生变化，不能作为判断该排序是否稳定的依据。
稳定性：指数组中相同元素在排序后相对位置不发生变化。
例如：在冒泡排序中，相同元素比较时不会交换顺序，从而排序后相同元素的相对位置不会发生变化，所以冒泡排序是稳定的。
最后我们对各种排序算法进行一个简单的测试：随机测试个数据
voidTstOP(){srand(tim(0));constintN=0;int*a=(int*)malloc(sizof(int)*N);int*a=(int*)malloc(sizof(int)*N);int*a=(int*)malloc(sizof(int)*N);int*a4=(int*)malloc(sizof(int)*N);int*a5=(int*)malloc(sizof(int)*N);int*a6=(int*)malloc(sizof(int)*N);for(inti=0;iN;++i){a[i]=rand();a[i]=a[i];a[i]=a[i];a4[i]=a[i];a5[i]=a[i];a6[i]=a[i];}intbgin=clock();InsrtSort(a,N);intnd=clock();intbgin=clock();ShllSort(a,N);intnd=clock();intbgin=clock();SlctSort(a,N);intnd=clock();intbgin4=clock();HapSort(a4,N);intnd4=clock();intbgin5=clock();QuickSort(a5,0,N-);intnd5=clock();intbgin6=clock();MrgSort(a6,N);intnd6=clock();printf("InsrtSort:%d\n",nd-bgin);printf("ShllSort:%d\n",nd-bgin);printf("SlctSort:%d\n",nd-bgin);printf("HapSort:%d\n",nd4-bgin4);printf("QuickSort:%d\n",nd5-bgin5);printf("MrgSort:%d\n",nd6-bgin6);f(a);f(a);f(a);f(a4);f(a5);f(a6);}
如有错误，感谢指正~
来都来了，点个赞再走吧~~
,