面试前必看的十大排序算法

时间：2022-12-01 12:29:15

 面试前必看的十大排序算法

绪论

身为程序员，十大排序是是所有合格程序员所必备和掌握的，并且热门的算法比如快排、归并排序还可能问的比较细致，对算法性能和复杂度的掌握有要求。bigsai作为一个负责任的Java和数据结构与算法方向的小博主，在这方面肯定不能让读者们有所漏洞。跟着本篇走，带你捋一捋常见的十大排序算法，轻轻松松掌握！

首先对于排序来说大多数人对排序的概念停留在冒泡排序或者JDK中的Arrays.sort()，手写各种排序对很多人来说都是一种奢望，更别说十大排序算法了，不过还好你遇到了本篇文章！

对于排序的分类，主要不同的维度比如复杂度来分、内外部、比较非比较等维度来分类。我们正常讲的十大排序算法是内部排序，我们更多将他们分为两大类：基于 「比较和非比较」 这个维度去分排序种类。

  • 「非比较类的有桶排序、基数排序、计数排序」。也有很多人将排序归纳为8大排序，那就是因为基数排序、计数排序是建立在桶排序之上或者是一种特殊的桶排序，但是基数排序和计数排序有它特有的特征，所以在这里就将他们归纳为10种经典排序算法。而比较类排序也可分为

  • 比较类排序也有更细致的分法，有基于交换的、基于插入的、基于选择的、基于归并的，更细致的可以看下面的脑图。 

面试前必看的十大排序算法

冒泡排序

冒泡排序，又称起泡排序，它是一种基于交换的排序典型，也是快排思想的基础，冒泡排序是一种稳定排序算法，时间复杂度为O(n^2).基本思想是： 「循环遍历多次每次从前往后把大元素往后调，每次确定一个最大(最小)元素，多次后达到排序序列。」 (或者从后向前把小元素往前调)。

具体思想为(把大元素往后调)：

  • 从第一个元素开始往后遍历，每到一个位置判断是否比后面的元素大，如果比后面元素大，那么就交换两者大小，然后继续向后，这样的话进行一轮之后就可以保证 「最大的那个数被交换交换到最末的位置可以确定」 。

  • 第二次同样从开始起向后判断着前进，如果当前位置比后面一个位置更大的那么就和他后面的那个数交换。但是有点注意的是，这次并不需要判断到最后，只需要判断到倒数第二个位置就行(因为第一次我们已经确定最大的在倒数第一，这次的目的是确定倒数第二)

  • 同理，后面的遍历长度每次减一，直到第一个元素使得整个元素有序。

例如 2 5 3 1 4 排序过程如下：

面试前必看的十大排序算法

实现代码为：

  1. public void  maopaosort(int[] a) { 
  2.   // TODO Auto-generated method stub
  3.   for(int i=a.length-1;i>=0;i--) 
  4.   { 
  5.     for(int j=0;j<i;j++) 
  6.     { 
  7.       if(a[j]>a[j+1]) 
  8.       { 
  9.         int team=a[j]; 
  10.         a[j]=a[j+1]; 
  11.         a[j+1]=team; 
  12.       } 
  13.     } 
  14.   } 
  15. } 

快速排序

快速排序是对冒泡排序的一种改进，采用递归分治的方法进行求解。而快排相比冒泡是一种不稳定排序,时间复杂度最坏是O(n^2),平均时间复杂度为O(nlogn),最好情况的时间复杂度为O(nlogn)。

对于快排来说， 「基本思想」 是这样的

  • 快排需要将序列变成两个部分，就是 「序列左边全部小于一个数」 ， 「序列右面全部大于一个数」 ，然后利用递归的思想再将左序列当成一个完整的序列再进行排序，同样把序列的右侧也当成一个完整的序列进行排序。

  • 其中这个数在这个序列中是可以随机取的，可以取最左边，可以取最右边，当然也可以取随机数。但是 「通常」 不优化情况我们取最左边的那个数。 

面试前必看的十大排序算法

实现代码为：

  1. public void quicksort(int [] a,int left,int right) 
  2. { 
  3.   int low=left; 
  4.   int high=right; 
  5.   //下面两句的顺序一定不能混，否则会产生数组越界！！！very important！！！
  6.   if(low>high)//作为判断是否截止条件
  7.     return; 
  8.   int k=a[low];//额外空间k，取最左侧的一个作为衡量，最后要求左侧都比它小，右侧都比它大。
  9.   while(low<high)//这一轮要求把左侧小于a[low],右侧大于a[low]。
  10.   { 
  11.     while(low<high&&a[high]>=k)//右侧找到第一个小于k的停止
  12.     { 
  13.       high--; 
  14.     } 
  15.     //这样就找到第一个比它小的了
  16.     a[low]=a[high];//放到low位置
  17.     while(low<high&&a[low]<=k)//在low往右找到第一个大于k的，放到右侧a[high]位置
  18.     { 
  19.       low++; 
  20.     } 
  21.     a[high]=a[low];    
  22.   } 
  23.   a[low]=k;//赋值然后左右递归分治求之
  24.   quicksort(a, left, low-1); 
  25.   quicksort(a, low+1, right);   
  26. } 

插入类排序

直接插入排序

直接插入排序在所有排序算法中的是最简单排序方式之一。和我们上学时候 从前往后、按高矮顺序排序，那么一堆高低无序的人群中，从第一个开始，如果前面有比自己高的，就直接插入到合适的位置。 「一直到队伍的最后一个完成插入」 整个队列才能满足有序。

直接插入排序遍历比较时间复杂度是每次O(n),交换的时间复杂度每次也是O(n),那么n次总共的时间复杂度就是O(n^2)。有人会问折半(二分)插入能否优化成O(nlogn),答案是不能的。因为二分只能减少查找复杂度每次为O(logn),而插入的时间复杂度每次为O(n)级别，这样总的时间复杂度级别还是O(n^2).

插入排序的具体步骤：

  • 选取当前位置(当前位置前面已经有序) 目标就是将当前位置数据插入到前面合适位置。

  • 向前枚举或者二分查找，找到待插入的位置。

  • 移动数组，赋值交换，达到插入效果。 

面试前必看的十大排序算法

实现代码为：

  1. public void insertsort (int a[]) 
  2. { 
  3.   int team=0; 
  4.   for(int i=1;i<a.length;i++) 
  5.   { 
  6.     System.out.println(Arrays.toString(a)); 
  7.     team=a[i]; 
  8.     for(int j=i-1;j>=0;j--) 
  9.     { 
  10.  
  11.       if(a[j]>team) 
  12.       { 
  13.         a[j+1]=a[j]; 
  14.         a[j]=team;  
  15.       }  
  16.       else { 
  17.         break; 
  18.       } 
  19.     } 
  20.   }  
  21. } 

希尔排序

直接插入排序因为是O(n^2),在数据量很大或者数据移动位次太多会导致效率太低。很多排序都会想办法拆分序列，然后组合，希尔排序就是以一种特殊的方式进行预处理，考虑到了 「数据量和有序性」 两个方面纬度来设计算法。使得序列前后之间小的尽量在前面，大的尽量在后面，进行若干次的分组别计算，最后一组即是一趟完整的直接插入排序。

对于一个 长串 ，希尔首先将序列分割(非线性分割)而是 「按照某个数模」 ( 取余 这个类似报数1、2、3、4。1、2、3、4)这样形式上在一组的分割先 「各组分别进行直接插入排序」 ,这样 「很小的数在后面」 可以通过 「较少的次数移动到相对靠前」 的位置。然后慢慢合并变长，再稍稍移动。

因为每次这样插入都会使得序列变得更加有序，稍微有序序列执行直接插入排序成本并不高。所以这样能够在合并到最终的时候基本小的在前，大的在后，代价越来越小。这样希尔排序相比插入排序还是能节省不少时间的。

面试前必看的十大排序算法

实现代码为：

  1. public void shellsort (int a[]) 
  2. { 
  3.   int d=a.length; 
  4.   int team=0;//临时变量
  5.   for(;d>=1;d/=2)//共分成d组
  6.     for(int i=d;i<a.length;i++)//到那个元素就看这个元素在的那个组即可
  7.     { 
  8.       team=a[i]; 
  9.       for(int j=i-d;j>=0;j-=d) 
  10.       {     
  11.         if(a[j]>team) 
  12.         { 
  13.           a[j+d]=a[j]; 
  14.           a[j]=team;  
  15.         } 
  16.         else { 
  17.           break; 
  18.         } 
  19.       } 
  20.     }  
  21. } 

选择类排序

简单选择排序

简单选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到 「已排序序列的末尾」 。以此类推，直到所有元素均排序完毕。 

面试前必看的十大排序算法

实现代码为：

  1. public void selectSort(int[] arr) { 
  2.   for (int i = 0; i < arr.length - 1; i++) { 
  3.     int min = i; // 最小位置
  4.     for (int j = i + 1; j < arr.length; j++) { 
  5.       if (arr[j] < arr[min]) { 
  6.         min = j; // 更换最小位置
  7.       } 
  8.     } 
  9.     if (min != i) { 
  10.       swap(arr, i, min); // 与第i个位置进行交换
  11.     } 
  12.   } 
  13. } 
  14. private void swap(int[] arr, int i, int j) { 
  15.   int temp = arr[i]; 
  16.   arr[i] = arr[j]; 
  17.   arr[j] = temp; 
  18. } 

对于堆排序，首先是建立在堆的基础上，堆是一棵完全二叉树，还要先认识下大根堆和小根堆，完全二叉树中所有节点均大于(或小于)它的孩子节点，所以这里就分为两种情况

  • 如果所有节点 「大于」 孩子节点值，那么这个堆叫做 「大根堆」 ，堆的最大值在根节点。

  • 如果所有节点 「小于」 孩子节点值，那么这个堆叫做 「小根堆」 ，堆的最小值在根节点。 

面试前必看的十大排序算法

堆排序首先就是 「建堆」 ，然后再是调整。对于二叉树(数组表示)，我们从下往上进行调整，从 「第一个非叶子节点」 开始向前调整，对于调整的规则如下：

建堆是一个O(n)的时间复杂度过程，建堆完成后就需要进行删除头排序。给定数组建堆(creatHeap)

①从第一个非叶子节点开始判断交换下移(shiftDown)，使得当前节点和子孩子能够保持堆的性质

②但是普通节点替换可能没问题，对如果交换打破子孩子堆结构性质，那么就要重新下移(shiftDown)被交换的节点一直到停止。 

面试前必看的十大排序算法

堆构造完成，取第一个堆顶元素为最小(最大)，剩下左右孩子依然满足堆的性值，但是缺个堆顶元素，如果给孩子调上来，可能会调动太多并且可能破坏堆结构。

①所以索性把最后一个元素放到第一位。这样只需要判断交换下移(shiftDown）,不过需要注意此时整个堆的大小已经发生了变化，我们在逻辑上不会使用被抛弃的位置，所以在设计函数的时候需要附带一个堆大小的参数。

②重复以上操作，一直堆中所有元素都被取得停止。

面试前必看的十大排序算法

而堆算法复杂度的分析上，之前建堆时间复杂度是O(n)。而每次删除堆顶然后需要向下交换，每个个数最坏为logn个。这样复杂度就为O(nlogn).总的时间复杂度为O(n)+O(nlogn)=O(nlogn).

实现代码为：

  1. static void swap(int arr[],int m,int n) 
  2. { 
  3.   int team=arr[m]; 
  4.   arr[m]=arr[n]; 
  5.   arr[n]=team; 
  6. } 
  7. //下移交换 把当前节点有效变换成一个堆(小根)
  8. static void shiftDown(int arr[],int index,int len)//0 号位置不用
  9. { 
  10.   int leftchild=index*2+1;//左孩子
  11.   int rightchild=index*2+2;//右孩子
  12.   if(leftchild>=len) 
  13.     return; 
  14.   else if(rightchild<len&&arr[rightchild]<arr[index]&&arr[rightchild]<arr[leftchild])//右孩子在范围内并且应该交换
  15.   { 
  16.     swap(arr, index, rightchild);//交换节点值
  17.     shiftDown(arr, rightchild, len);//可能会对孩子节点的堆有影响，向下重构
  18.   } 
  19.   else if(arr[leftchild]<arr[index])//交换左孩子
  20.   { 
  21.     swap(arr, index, leftchild); 
  22.     shiftDown(arr, leftchild, len); 
  23.   } 
  24. } 
  25. //将数组创建成堆
  26. static void creatHeap(int arr[]) 
  27. { 
  28.   for(int i=arr.length/2;i>=0;i--) 
  29.   { 
  30.     shiftDown(arr, i,arr.length); 
  31.   } 
  32. } 
  33. static void heapSort(int arr[]) 
  34. { 
  35.   System.out.println("原始数组为         ："+Arrays.toString(arr)); 
  36.   int val[]=new int[arr.length]; //临时储存结果
  37.   //step1建堆
  38.   creatHeap(arr); 
  39.   System.out.println("建堆后的序列为  ："+Arrays.toString(arr)); 
  40.   //step2 进行n次取值建堆，每次取堆顶元素放到val数组中，最终结果即为一个递增排序的序列
  41.   for(int i=0;i<arr.length;i++) 
  42.   { 
  43.     val[i]=arr[0];//将堆顶放入结果中
  44.     arr[0]=arr[arr.length-1-i];//删除堆顶元素，将末尾元素放到堆顶
  45.     shiftDown(arr, 0, arr.length-i);//将这个堆调整为合法的小根堆，注意(逻辑上的)长度有变化
  46.   } 
  47.   //数值克隆复制
  48.   for(int i=0;i<arr.length;i++) 
  49.   { 
  50.     arr[i]=val[i]; 
  51.   } 
  52.   System.out.println("堆排序后的序列为:"+Arrays.toString(arr)); 
  53.  
  54. } 

归并类排序

在归并类排序一般只讲归并排序，但是归并排序也分二路归并、多路归并，这里就讲较多的二路归并排序，且用递归方式实现。

归并排序

归并和快排都是 「基于分治算法」 的，分治算法其实应用挺多的，很多分治会用到递归，但事实上 「分治和递归是两把事」 。分治就是分而治之，可以采用递归实现，也可以自己遍历实现非递归方式。而归并排序就是先将问题分解成代价较小的子问题，子问题再采取代价较小的合并方式完成一个排序。

至于归并的思想是这样的：

  • 第一次：整串先进行划分成一个一个单独，第一次是将序列中( 1 2 3 4 5 6--- )两两归并成有序，归并完( xx xx xx xx---- )这样局部有序的序列。
  • 第二次就是两两归并成若干四个( 1 2 3 4 5 6 7 8 ---- ) 「每个小局部是有序的」 。
  • 就这样一直到最后这个串串只剩一个，然而这个耗费的总次数logn。每次操作的时间复杂的又是 O(n) 。所以总共的时间复杂度为 O(nlogn) 。 

面试前必看的十大排序算法

合并为一个O(n)的过程： 

面试前必看的十大排序算法

实现代码为：

  1. private static void mergesort(int[] array, int left, int right) { 
  2.   int mid=(left+right)/2; 
  3.   if(left<right) 
  4.   { 
  5.     mergesort(array, left, mid); 
  6.     mergesort(array, mid+1, right); 
  7.     merge(array, left,mid, right); 
  8.   } 
  9. } 
  10.  
  11. private static void merge(int[] array, int l, int mid, int r) { 
  12.   int lindex=l;int rindex=mid+1; 
  13.   int team[]=new int[r-l+1]; 
  14.   int teamindex=0; 
  15.   while (lindex<=mid&&rindex<=r) {//先左右比较合并
  16.     if(array[lindex]<=array[rindex]) 
  17.     { 
  18.       team[teamindex++]=array[lindex++]; 
  19.     } 
  20.     else {     
  21.       team[teamindex++]=array[rindex++]; 
  22.     } 
  23.   } 
  24.   while(lindex<=mid)//当一个越界后剩余按序列添加即可
  25.   { 
  26.     team[teamindex++]=array[lindex++]; 
  27.  
  28.   } 
  29.   while(rindex<=r) 
  30.   { 
  31.     team[teamindex++]=array[rindex++]; 
  32.   }  
  33.   for(int i=0;i<teamindex;i++) 
  34.   { 
  35.     array[l+i]=team[i]; 
  36.   } 
  37.  
  38. } 

桶类排序

桶排序是一种用空间换取时间的排序，桶排序重要的是它的思想，而不是具体实现，时间复杂度最好可能是线性O(n)，桶排序不是基于比较的排序而是一种分配式的。桶排序从字面的意思上看：

  • 桶：若干个桶，说明此类排序将数据放入若干个桶中。

  • 桶：每个桶有容量，桶是有一定容积的容器，所以每个桶中可能有多个元素。

  • 桶：从整体来看，整个排序更希望桶能够更匀称，即既不溢出(太多)又不太少。

桶排序的思想为： 「将待排序的序列分到若干个桶中，每个桶内的元素再进行个别排序。」 当然桶排序选择的方案跟具体的数据有关系，桶排序是一个比较广泛的概念，并且计数排序是一种特殊的桶排序，基数排序也是建立在桶排序的基础上。在数据分布均匀且每个桶元素趋近一个时间复杂度能达到O(n),但是如果数据范围较大且相对集中就不太适合使用桶排序。 

面试前必看的十大排序算法

实现一个简单桶排序：

  1. import java.util.ArrayList; 
  2. import java.util.List; 
  3. //微信公众号：bigsai
  4. public class bucketSort { 
  5.  public static void main(String[] args) { 
  6.   int a[]= {1,8,7,44,42,46,38,34,33,17,15,16,27,28,24}; 
  7.   List[] buckets=new ArrayList[5]; 
  8.   for(int i=0;i<buckets.length;i++)//初始化
  9.   { 
  10.    buckets[i]=new ArrayList<Integer>(); 
  11.   } 
  12.   for(int i=0;i<a.length;i++)//将待排序序列放入对应桶中
  13.   { 
  14.    int index=a[i]/10;//对应的桶号
  15.    buckets[index].add(a[i]); 
  16.   } 
  17.   for(int i=0;i<buckets.length;i++)//每个桶内进行排序(使用系统自带快排)
  18.   { 
  19.    buckets[i].sort(null); 
  20.    for(int j=0;j<buckets[i].size();j++)//顺便打印输出
  21.    { 
  22.     System.out.print(buckets[i].get(j)+" "); 
  23.    } 
  24.   }  
  25.  } 
  26. } 

计数排序

计数排序是一种特殊的桶排序，每个桶的大小为1，每个桶不在用List表示，而通常用一个值用来计数。

在 「设计具体算法的时候」 ，先找到最小值min，再找最大值max。然后创建这个区间大小的数组,从min的位置开始计数，这样就可以最大程度的压缩空间，提高空间的使用效率。 

面试前必看的十大排序算法

  1. public static void countSort(int a[]) 
  2. { 
  3.   int min=Integer.MAX_VALUE;int max=Integer.MIN_VALUE; 
  4.   for(int i=0;i<a.length;i++)//找到max和min
  5.   { 
  6.     if(a[i]<min)  
  7.       min=a[i]; 
  8.     if(a[i]>max) 
  9.       max=a[i]; 
  10.   } 
  11.   int count[]=new int[max-min+1];//对元素进行计数
  12.   for(int i=0;i<a.length;i++) 
  13.   { 
  14.     count[a[i]-min]++; 
  15.   } 
  16.   //排序取值
  17.   int index=0; 
  18.   for(int i=0;i<count.length;i++) 
  19.   { 
  20.     while (count[i]-->0) { 
  21.       a[index++]=i+min;//有min才是真正值
  22.     } 
  23.   } 
  24. } 

基数排序

基数排序是一种很容易理解但是比较难实现(优化)的算法。基数排序也称为卡片排序，基数排序的原理就是多次利用计数排序(计数排序是一种特殊的桶排序)，但是和前面的普通桶排序和计数排序有所区别的是， 「基数排序并不是将一个整体分配到一个桶中」 ，而是将自身拆分成一个个组成的元素，每个元素分别顺序分配放入桶中、顺序收集，当从前往后或者从后往前每个位置都进行过这样顺序的分配、收集后，就获得了一个有序的数列。 

面试前必看的十大排序算法

如果是数字类型排序，那么这个桶只需要装0-9大小的数字，但是如果是字符类型，那么就需要注意ASCII的范围。

所以遇到这种情况我们基数排序思想很简单，就拿 934，241，3366，4399这几个数字进行基数排序的一趟过程来看，第一次会根据各位进行分配、收集： 

面试前必看的十大排序算法

分配和收集都是有序的，第二次会根据十位进行分配、收集，此次是在第一次个位分配、收集基础上进行的，所以所有数字单看个位十位是有序的。 

面试前必看的十大排序算法

而第三次就是对百位进行分配收集，此次完成之后百位及其以下是有序的。 

面试前必看的十大排序算法

而最后一次的时候进行处理的时候，千位有的数字需要补零，这次完毕后后千位及以后都有序，即整个序列排序完成。 

面试前必看的十大排序算法

简单实现代码为：

  1. static void radixSort(int[] arr)//int 类型 从右往左
  2. { 
  3.   List<Integer>bucket[]=new ArrayList[10]; 
  4.   for(int i=0;i<10;i++) 
  5.   { 
  6.     bucket[i]=new ArrayList<Integer>(); 
  7.   } 
  8.   //找到最大值
  9.   int max=0;//假设都是正数
  10.   for(int i=0;i<arr.length;i++) 
  11.   { 
  12.     if(arr[i]>max) 
  13.       max=arr[i]; 
  14.   } 
  15.   int divideNum=1;//1 10 100 100……用来求对应位的数字
  16.   while (max>0) {//max 和num 控制
  17.     for(int num:arr) 
  18.     { 
  19.       bucket[(num/divideNum)%10].add(num);//分配 将对应位置的数字放到对应bucket中
  20.     } 
  21.     divideNum*=10; 
  22.     max/=10; 
  23.     int idx=0; 
  24.     //收集 重新捡起数据
  25.     for(List<Integer>list:bucket) 
  26.     { 
  27.       for(int num:list) 
  28.       { 
  29.         arr[idx++]=num; 
  30.       } 
  31.       list.clear();//收集完需要清空留下次继续使用
  32.     } 
  33.   } 
  34. } 

当然，基数排序还有字符串等长、不等长、一维数组优化等各种实现需要需学习，具体可以参考公众号内其他文章。

本次十大排序就这么潇洒的过了一遍，我想大家都应该有所领悟了吧！对于算法总结，避免不必要的劳动力，我分享这个表格给大家：

排序算法 平均时间复杂度 最好 最坏 空间复杂度 稳定性
冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定
快速排序 O(nlogn) O(nlogn) O(n^2) O(logn) 不稳定
插入排序 O(n^2) O(n) O(n^2) O(1) 稳定
希尔排序 O(n^1.3) O(n) O(nlog2n) O(1) 不稳定
选择排序 O(n^2) O(n^2) O(n^2) O(1) 不稳定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定
桶排序 O(n+k) O(n+k) O(n+k) O(n+k) 稳定
计数排序 O(n+k) O(n+k) O(n+k) O(k) 稳定
基数排序 O(n*k) O(n*k) O(n*k) O(n+k) 稳定

 原文链接：https://mp.weixin.qq.com/s?__biz=MzUxODkzNTQ3Nw==&mid=2247488794&idx=1&sn=0db7303c81a4973309fffab94dacb4c5&utm_source=tuicool&utm_medium=referral

标签：

相关文章