前言
排序算法的重要性无需多言，无论是面试还是工作中，它占据的位置都是很重的。一般，我们学习的都是十大排序等基础排序，而在面试中，堆排，归并，快排几个排序又非常高频。此外，部分排序如 topk 问题等在面试中都非常出现，解决办法如堆的使用，快速选择，快排的 partition 操作等都很常见。而除此外排序单独出现的题型一般都比较少，更多的是与其它题型结合起来。

分析
对于基础排序，即基于比较的冒泡，选择，插入等，优化的希尔，归并，快排，还有基于非比较的桶排，计数排序等。都是需要掌握的。

除了常见的十大排序，在工业上，有两个结合的排序也可以掌握，分别是内审排序（快排+插入+堆的组合），tim 排序（二分插入、归并），很多语言的 sort 实现基本都是这两个，如 go 使用的就是内审排序，而 python，java 就使用了 tim 排序。前者不稳定，否则稳定。

重点需要掌握该排序的原理，复杂度，使用场景等几个要点。而具体的细节这里就不展开，有非常多优秀的文章进行讲解。

题型
排序算法的题型我总结了几个方面，主要有 十大算法的实现、topk 问题、归并、摩尔投票等。


十大排序的实现

912.排序数组


冒泡排序

  1.  public int[] sortArray(int[] nums) {
  2.         for(int i = 0;i < nums.length; i++){
  3.             for(int j = 0; j < nums.length-1; j++){
  4.                 if(nums[j] > nums[j+1]){
  5.                     int temp = nums[j];
  6.                     nums[j] = nums[j+1];
  7.                     nums[j+1] = temp;
  8.                 }
  9.             }
  10.         }
  11.         return nums;
  12.     }

选择排序

  1. public int[] sortArray(int[] nums) {
  2.         for(int i = 0; i < nums.length; i++){
  3.             int min = i;
  4.             for(int j = i+1; j < nums.length; j++){
  5.                 if(nums[j] < nums[min]){
  6.                     min = j;
  7.                 }
  8.             }
  9.             if(i != min){
  10.                 int temp = nums[i];
  11.                 nums[i] = nums[min];
  12.                 nums[min] = temp;
  13.             }
  14.         }
  15.         return nums;
  16.     }

插入排序

  1. public int[] sortArray(int[] nums) {
  2.         //从下标为1的元素开始选择合适的位置插入
  3.         //因为下标为0的只有一个元素，默认是有序的
  4.         for(int i = 1;i < nums.length; i++){
  5.             // 记录要插入的数据
  6.             int temp = nums[i];
  7.             // 从已经排序的序列最右边的开始比较，找到比其小的数
  8.             int j = i;
  9.             while(j > 0 && temp < nums[j-1]){
  10.                 nums[j] = nums[j-1];
  11.                 j--;
  12.             }
  13.             // 存在比其小的数，插入
  14.             if(j != i){
  15.                 nums[j] = temp;
  16.             }
  17.         }
  18.         return nums;
  19.     }

希尔排序

  1.  public int[] sortArray(int[] nums) {
  2.         for(int gap = nums.length/2; gap > 0; gap /= 2){
  3.             for(int i = gap; i < nums.length; i++){
  4.                int temp = nums[i];
  5.                int j = i - gap;
  6.                while(j >= 0 && nums[j] > temp){
  7.                    nums[j + gap] = nums[j];
  8.                    j -= gap;
  9.                }
  10.                 nums[j + gap] = temp;
  11.             }
  12.         }
  13.         return nums;
  14.     }

归并排序

快速排序

  1. public int[] sortArray(int[] nums) {
  2.         return quickSort(nums,0,nums.length-1);
  3.     }
  4.     public int[] quickSort(int[] nums,int left,int right){
  5.         if(left < right){
  6.             int partitionIndex = partition(nums,left,right);
  7.             quickSort(nums,left,partitionIndex-1);
  8.             quickSort(nums,partitionIndex+1,right);
  9.         }
  10.         return nums;
  11.     }
  12.     public int partition(int[] nums,int left,int right){
  13.         int pivot = left;
  14.         int index = pivot + 1;
  15.         for(int i = index;i < nums.length;i++){
  16.             if(nums[i] < nums[pivot]){
  17.                 swap(nums,i,index);
  18.                 index++;
  19.             }
  20.         }
  21.         swap(nums,pivot,index-1);
  22.         return index-1;
  23.     }
  24.     public void swap(int[] nums,int i,int j){
  25.         int temp = nums[i];
  26.         nums[i] = nums[j];
  27.         nums[j] = temp;
  28.     }

基数排序