那些年，让我面试头大的几个排序算法，今天终于搞懂了！

作者 |?逆流的鱼yuiop

转载自何俊林（ID:smartyuge）

算法上，最基础的就是排序算法，几乎在面试中，或多或少会要求你手写一些基础算法。今天鱼哥带大家这些基础算法回顾下。

快速排序

介绍：

快速排序（Quicksort）是对冒泡排序的一种改进。
快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

步骤：

1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]的值交换；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]的值交换；
5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。

代码：

//快速排序??
????private?void?quickSort(int[]??a?,int?left,int?right)?{??
????????if(left?< ?right){??
????????????int?i,j,t,temp;??
????????????temp=a[left];?//temp中存的就是基准数??
????????????i=left;??
????????????j=right;??
????????????while(i!=j)??
????????????{??
????????????????//顺序很重要，要先从右边开始找??
????????????????while(a[j]>=temp?&&?i????????????????????j--;??
????????????????//再找右边的??
????????????????while(a[i]< =temp?&&?i????????????????????i++;??
????????????????//交换两个数在数组中的位置??
????????????????if(i????????????????{??
????????????????????t=a[i];??
????????????????????a[i]=a[j];??
????????????????????a[j]=t;??
????????????????}??
????????????}??
????????????//最终将基准数归位??
????????????a[left]=a[i];??
????????????a[i]=temp;??
????????????quickSort(a,left,i-1);//继续处理左边的，这里是一个递归的过程??
????????????quickSort(a,i+1,right);//继续处理右边的?，这里是一个递归的过程??
????????}??
????}??
//?调用
quickSort(a,0,a.length-1);??

归并排序

介绍：

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

步骤：

1、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
2、设定两个指针，最初位置分别为两个已经排序序列的起始位置；
3、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
4、重复步骤3直到某一指针达到序列尾；
5、将另一序列剩下的所有元素直接复制到合并序列尾。

代码:

public?class?MergeSort?{
????//　private　static　long　sum　=　0;

????/**
?????*?　*　< pre>
?????*?　*　二路归并
?????*?　*　原理：将两个有序表合并和一个有序表
?????*?　*　pre>
?????*?　*
?????*?　*　@param　a
?????*?　*　@param　s
?????*?　*　第一个有序表的起始下标
?????*?　*　@param　m
?????*?　*　第二个有序表的起始下标
?????*?　*　@param　t
?????*?　*　第二个有序表的结束下标
?????*?　*
?????*/
????private?static?void?merge(int[]?a,?int?s,?int?m,?int?t)?{
????????int[]?tmp?=?new?int[t?-?s?+?1];
????????int?i?=?s,?j?=?m,?k?=?0;
????????while?(i?< ?m?&&?j?<=?t)?{
????????????if?(a[i]?< =?a[j])?{
????????????????tmp[k]?=?a[i];
????????????????k++;
????????????????i++;
????????????}?else?{
????????????????tmp[k]?=?a[j];
????????????????j++;
????????????????k++;
????????????}
????????}
????????while?(i?< ?m)?{
????????????tmp[k]?=?a[i];
????????????i++;
????????????k++;
????????}
????????while?(j?< =?t)?{
????????????tmp[k]?=?a[j];
????????????j++;
????????????k++;
????????}
????????System.arraycopy(tmp,?0,?a,?s,?tmp.length);
????}

????/**
?????*?*
?????*?*?每次归并的有序集合的长度
?????*/
????public?static?void?mergeSort(int[]?a,?int?s,?int?len)?{
????????int?size?=?a.length;
????????int?mid?=?size?/?(len?< 1);
????????int?c?=?size?&?((len?< 1)?-?1);
????????//　-------归并到只剩一个有序集合的时候结束算法-------//
????????if?(mid?==?0)
????????????return;
????????//　------进行一趟归并排序-------//
????????for?(int?i?=?0;?i?< ?mid;?++i)?{
????????????s?=?i?*?2?*?len;
????????????merge(a,?s,?s?+?len,?(len?< 1)?+?s?-?1);
????????}
????????//　-------将剩下的数和倒数一个有序集合归并-------//
????????if?(c?!=?0)
????????????merge(a,?size?-?c?-?2?*?len,?size?-?c,?size?-?1);
????????//　-------递归执行下一趟归并排序------//
????????mergeSort(a,?0,?2?*?len);
????}

????public?static?void?main(String[]?args)?{
????????int[]?a?=?new?int[]{4,?3,?6,?1,?2,?5};
????????mergeSort(a,?0,?1);
????????for?(int?i?=?0;?i?< ?a.length;?++i)?{
????????????System.out.print(a[i]?+?"　");
????????}
????}
}

堆排序

介绍：

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

步骤：

推荐看这篇文：https://www.cnblogs.com/chengxiao/p/6129630.html

代码：

建立大根堆的方法：

??????//构建大根堆：将array看成完全二叉树的顺序存储结构
??????private?int[]?buildMaxHeap(int[]?array){
??????????//从最后一个节点array.length-1的父节点（array.length-1-1）/2开始，直到根节点0，反复调整堆
??????????for(int?i=(array.length-2)/2;i>=0;i--){?
??????????????adjustDownToUp(array,?i,array.length);
??????????}
??????????return?array;
??????}

?????//将元素array[k]自下往上逐步调整树形结构
?????private?void?adjustDownToUp(int[]?array,int?k,int?length){
?????????int?temp?=?array[k];???
?????????for(int?i=2*k+1;?i-1;?i=2*i+1){????//i为初始化为节点k的左孩子，沿节点较大的子节点向下调整
?????????????if(iarray[i]< array[i+1]){??//取节点较大的子节点的下标
?????????????????i++;???//如果节点的右孩子>左孩子，则取右孩子节点的下标
?????????????}
?????????????if(temp>=array[i]){??//根节点?>=左右子女中关键字较大者，调整结束
?????????????????break;
?????????????}else{???//根节点?< 左右子女中关键字较大者
?????????????????array[k]?=?array[i];??//将左右子结点中较大值array[i]调整到双亲节点上
?????????????????k?=?i;?//【关键】修改k值，以便继续向下调整
?????????????}
?????????}
?????????array[k]?=?temp;??//被调整的结点的值放人最终位置
?????}????

排序

??????//堆排序
??????public?int[]?heapSort(int[]?array){
??????????array?=?buildMaxHeap(array);?//初始建堆，array[0]为第一趟值最大的元素
??????????for(int?i=array.length-1;i>1;i--){??
??????????????int?temp?=?array[0];??//将堆顶元素和堆低元素交换，即得到当前最大元素正确的排序位置
??????????????array[0]?=?array[i];
??????????????array[i]?=?temp;
??????????????adjustDownToUp(array,?0,i);??//整理，将剩余的元素整理成堆
??????????}
?????????return?array;
?????}

删除堆顶元素（即序列中的最大值）：先将堆的最后一个元素与堆顶元素交换，由于此时堆的性质被破坏，需对此时的根节点进行向下调整操作。

?????//删除堆顶元素操作
?????public?int[]?deleteMax(int[]?array){
?????????//将堆的最后一个元素与堆顶元素交换，堆底元素值设为-99999
?????????array[0]?=?array[array.length-1];
?????????array[array.length-1]?=?-99999;
?????????//对此时的根节点进行向下调整
?????????adjustDownToUp(array,?0,?array.length);
?????????return?array;
?????}

对堆的插入操作：先将新节点放在堆的末端，再对这个新节点执行向上调整操作。

假设数组的最后一个元素array[array.length-1]为空，新插入的结点初始时放置在此处。

??????//插入操作:向大根堆array中插入数据data
??????public?int[]?insertData(int[]?array,?int?data){
??????????array[array.length-1]?=?data;?//将新节点放在堆的末端
??????????int?k?=?array.length-1;??//需要调整的节点
??????????int?parent?=?(k-1)/2;????//双亲节点
??????????while(parent?>=0?&&?data>array[parent]){
??????????????array[k]?=?array[parent];??//双亲节点下调
??????????????k?=?parent;
??????????????if(parent?!=?0){
?????????????????parent?=?(parent-1)/2;??//继续向上比较
?????????????}else{??//根节点已调整完毕，跳出循环
?????????????????break;
?????????????}
?????????}
?????????array[k]?=?data;??//将插入的结点放到正确的位置
?????????return?array;
?????}

选择排序

介绍：

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方式样。

排序效果：

代码：

public?static?void?selectSort(int[]?a)?{???
????if((a?==?null)?||?(a.length?==?0))??????
????????return?;???
????for(int?i?=?0;i?< ?a.length?-?1;i?++){??????
????????int?minIndex?=?i;?//?无序区的最小数据数组下标??????
????????for(int?j?=?i?+?1;j?< ?a.length;j?++){?????????
????????????//?在无序区中找到最小数据并保存其数组下标?????????
????????????if(a[j]?< ?a[minIndex]){????????????
????????????????minIndex?=?j;?????????
????????????}??????
????????}??????
????????//?将最小元素放到本次循环的前端??????
????????int?temp?=?a[i];??????
????????a[i]?=?a[minIndex];??????
????????a[minIndex]?=?temp;???
????}
}

冒泡排序

介绍：

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

步骤：

1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2、对每一对相邻元素作同样操作，从开始第一对到结尾的最后一对。在这一点，最后的元素会是最大的数。
3、针对所有的元素重复以上的步骤，除了最后一个。
4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

代码：

??public?static?void?bubbleSort(int?[]arr)?{
???????????????int[]?arr?=?{12,23,34,56,56,56,78};
????????for(int?i?=0;i-1;i++)?{?
????????????for(int?j=0;j-1;j++)?{//-1为了防止溢出
????????????????if(arr[j]>arr[j+1])?{
????????????????????int?temp?=?arr[j];
????????????????????arr[j]=arr[j+1];?
????????????????????arr[j+1]=temp;
????????????}
????????}????
}

排序效果：

插入排序

介绍：

插入排序（Insertion sort）是一种简单直观且稳定的排序算法。如果有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中.

步骤：

1、从第一个元素开始，该元素可以认为已经被排序；
2、取出下一个元素，在已经排序的元素序列中从后向前扫描；
3、如果该元素(已排序)大于新元素，将该元素移到下一位置；
4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5、将新元素插入到该位置中，重复步骤2。

排序代码：

//直接插入??
????private?void?InsertSort(int[]?a)?{??
????????//直接插入排序??
????????for?(int?i?=?1;?i?< ?a.length;?i++)?{??
????????????//待插入元素??
????????????int?temp?=?a[i];??
????????????int?j;??
????????????for?(j?=?i?-?1;?j?>=?0;?j--)?{??
????????????????//将大于temp的往后移动一位??
????????????????if?(a[j]?>?temp)?{??
????????????????????a[j?+?1]?=?a[j];??
????????????????}?else?{??
????????????????????break;??
????????????????}??
????????????}??
????????????a[j?+?1]?=?temp;//插入进来??
????????}??
????}??

希尔排序

介绍：

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。 [1]

步骤：

可以这篇博客，图解版，非常详细：

http://www.cnblogs.com/chengxiao/p/6104371.html

代码：

public?static?void?main(String?[]?args)
{
????int[]?a?=?{49,38,65,97,76,13,27,49,78,34,12,64,1};
????????//希尔排序
????????int?d=a.length;
????????????while(true)
????????????{
????????????????d=d/2;
????????????????for(int?x=0;x????????????????{
????????????????????for(int?i=x+d;i????????????????????{
????????????????????????int?temp=a[i];
????????????????????????int?j;
????????????????????????for(j=i-d;j>=0&&a[j]>temp;j=j-d)
????????????????????????{
????????????????????????????a[j+d]=a[j];
????????????????????????}
????????????????????????a[j+d]=temp;
????????????????????}
????????????????}
????????????????if(d==1)
????????????????{
????????????????????break;
????????????????}
????????????}
????????????System.out.println("排序之后：");
????????????for(int?i=0;i????????????{
????????????????System.out.print(a[i]+"?");
????????????}
????}

◆

CTA核心技术及应用峰会

◆