0、初识排序

0.1 什么是排序？为什么要排序？

排序是计算机内经常进行的一种操作，其目的是将一组 “无序” 的记录序列调整为 “有序” 的记录序列。分内部排序和外部排序，若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。–(来源百度)

将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程叫做排序。

0.2 什么是排序的稳定性？

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。 – (来源百度)

就是上图这个意思！

0.3 几种常见的排序

1、插入排序

插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 [1] 。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动 [2] 。

1.1 直接插入排序

直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，其基本操作是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表。

1.1.1 思路

首先需要跟大家说一个知识点就是
我们需要把整个区间分为：

1. 有序区间
2. 无序区间
   每次选择无序区间的第一个元素，在有序区间中选择合适的位置插入
   举一个例子来帮助大家理解：

9,1,2,5,7,4,8,6,3,5

(1).先看第一个数，将数组分为有序和无序部分

• 首先看第一个数9，一个数必然是有序的，所以将9划分为有序，后面都是无序的。

• 

  (2).无序部分的首个插入到有序部分

• 取出无序部分的首个，在有序部分从后往前比较，插入到合适的位置

• 
  (3).重复第二步，直到无序部分全部插入有序，注意多次比较，不是比较一次插入一次。

  1.1.2 代码实现

  有了整体思路之后，我们就需要去设计代码了！
  如何用代码来实现了？
  我们可以尝试去定义两个循环参数i和j，并且j在i的前面设为i-1；
  
  同时我们创建一个临时变量tmp，每一次插入我们首先拿出要插入的数
  
  j下标往前走，没遇到一个元素就和tmp比较，如果array[j] > tmp，那么array[j+1] = tmp;这样就把前面大的元素放到了后面，j往前遍历的前提是j>=0;如果array[j] <= tmp;那么循环结束，这里要注意的是最后循环条件不满足时，还要执行一次array[j+1] = tmp;因为最后一次没有交换。

      public static void insertSort(int []arr){
          for (int i = 0; i < arr.length; i++) {
              int j = i-1;
              int tmp = arr[i];
              for (; j >=0 ; j--) {
                  if(arr[j] > tmp){
                      arr[j+1] = arr[j];
                  }else{
                      break;
                  }
              }
              arr[j+1] = tmp;
          }
      }
  

  1.1.3 特性分析

  1. 时间复杂度
     最好的情况就是全部有序，此时只需要遍历一次，最好的时间复杂度为O(n)；
     最坏的情况就是全部逆序，内层每次遍历已排部分，最坏的时间复杂度为O(n^2);

  2. 空间复杂度
     空间复杂度：O(1)

  3. 算法稳定性
     稳定的。

  1.2 希尔排序

  希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。
  希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。
  

  1.2.1 思路

  希尔排序是直接插入排序的一种优化，我们需要给希尔排序定义一个步长gap，这个gap可以是4分组，2分组，1分组等等，但是我们常用的是gap = length / 2来当做补充，缩小步长的方法以gap = gap / 2的方式为常用。
  但其实这个步长也不是最优的，这里我们就不讨论这个问题了！

  举一个例子来帮助大家理解：

  9,1,2,5,7,4,8,6,3,5

  (1).对于一个无序序列{9,1,2,5,7,4,8,6,3,5}来说，我们初识步长为gap = length / 2 = 5，所以这个序列被分为5组，分别为{9，4}，{1，8}，{2，6}，{5，3}，{7，5},对于这5组进行直接插入排序，则小的元素被调换到了前面，然后再缩小步长gap = gap / 2；
  
  

  (2).序列再次被分为2组，分别为{4，2，5，8，5}，{1，3，9，6，7}，再对这两组进行直接插入排序，那么序列就更加有序了！
  
  
  (3).然后缩小步长gap = gap / 2 = 1，这时整个序列被分为{2，1，4，3，5，6，5，7，8，9}；

  
  

  1.2.2 代码实现

    public static void shell(int[] array,int gap) {
          for (int i = gap; i < array.length; i++) {
              int tmp = array[i];
              int j = i-gap;
              for (; j >= 0;j-=gap) {
                  if(array[j] > tmp) {
                      array[j+gap] = array[j];
                  }else {
                      break;
                  }
              }
              array[j+gap] = tmp;
          }
      }
      public static void shellSort(int[] array) {
          int gap = array.length;
          while (gap > 1) {
              gap /= 2;
              shell(array,gap);
          }
      }
  

  1.2.3 特征分析

  1. 时间复杂度
     因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定，如果没有特殊说明，我们通常就取时间复杂度为O(n^1.3)。
  2. 空间复杂度
     空间复杂度为O(1)
  3. 稳定性
     不稳定的。

  2、选择排序

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

  2.1 直接选择排序

  直接选择排序(Straight Select Sorting) 也是一种简单的排序方法，它的基本思想是：第一次从R[0]~R[n-1]中选取最小值，与R[0]交换，第二次从R[1] ~ R[n-1]中选取最小值，与R[1]交换，…，第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换，…，第n-1次从R[n-2] ~ R[n-1]中选取最小值，与R[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。

  

  2.1.1 思路

  每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

  举一个例子来帮助大家理解：

  9,1,2,5,7,4,8,6,3,5

  具体排序过程：

  1. 将整个记录序列划分为有序区和无序区，初始时有序区为空，无序区含有待排序的所有记录
  2. 在无序区选择关键码最小的记录，将其与无序区中的第一个元交换，使得有序区扩展一个记录，同时无序区减少了一个记录
  3. 不断重复步骤 2，直到无序区只剩下一个记录为止

  

  2.1.2 代码实现

   public static void selectSort(int[] array){
          int i = 0;
          int minindex = i;
          for (i = 0; i < array.length; i++) {
              for (int j = i+1; j <array.length ; j++) {
                  if(array[j] < array[minindex]){
                      //更新minindex的值
                      minindex = j;
                  }
              }
              //处理两个下标值一样的情况
              if (i != minindex){
                  swap(array,minindex,i);
              }
          }
      }
      public static void swap(int[] array,int i,int j){
          int tmp = array[i];
          array[i] = array[j];
          array[j] =tmp;
      }
  

  2.1.3 特性分析

  1. 时间复杂度
     时间复杂度为O(n^2)
  2. 空间复杂度
     空间复杂度为O(1)
  3. 稳定性
     不稳定的。

  2.2 堆排序

  堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。 需要注意的是排升序要建大堆，排降序建小堆。
  

  2.2.1 思路

  想要学习堆排序的可以去看一下【一起学习数据结构与算法】优先级队列(堆)，这里已经讲过堆排序了！

  2.2.2 代码实现

  我们这里还是附上堆排序的代码！

    public static void heapSort(int[] array) {//堆排序
          createBigHeap(array);//O(n)
          int end = array.length-1;
          while (end > 0) {
              swap(array,0,end);
              shiftDown(array,0,end);
              end--;
          }
      }
   
      private static void createBigHeap(int[] array) {//创建大根堆
          for (int parent = (array.length-1-1)/2; parent >= 0 ; parent--) {
              shiftDown(array,parent,array.length);
          }
      }
   
      private static void shiftDown(int[] array,int parent,int len) {//向下调整
          int child = (2 * parent) + 1;
          while (child < len) {
              if (child + 1 < len && array[child] < array[child + 1]) {
                  child++;
              }
              if (array[child] > array[parent]) {
                  swap(array, child, parent);
                  parent = child;
                  child = 2 * parent + 1;
              } else {
                  break;
              }
          }
      }
  

  特性分析

  1. 时间复杂度
     时间复杂度为O(n * logn)
  2. 空间复杂度
     空间复杂度为O(1)
  3. 稳定性
     不稳定的。

  3、交换排序

  所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序 的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

  3.1 冒泡排序

  冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
  它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行，直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
  这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
  

  3.1.1 思路

  冒泡排序基本思想就是相邻元素挨个比较，遇到比自己小的就交换，直到最后元素有序。

  3.1.2 代码实现

      public static void bubbleSort(int[] array) {
          //最外层控制的是趟数
          for (int i = 0; i < array.length-1; i++) {
              boolean flg = false;
              for (int j = 0; j < array.length-1-i; j++) {
                  if(array[j] > array[j+1]) {
                      swap(array,j,j+1);
                      flg = true;
                  }
              }
              if(flg == false) {
                  break;
              }
          }
      }
  

  3.1.3 特性分析

  1. 时间复杂度
     时间复杂度为O(n ^ 2)
  2. 空间复杂度
     空间复杂度为O(1)
  3. 稳定性
     稳定的。

  3.2 快速排序

  快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元 素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有 元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

  

  3.2.1 思路

  3.2.1.1 Hoare法

  假定基准值pivot是最左侧的元素，比较的时候从数组的尾部进行比较，

  (1).当最右侧的元素大于基准值pivot的时候，right–.如果arr[left]<pivot的时候，就交换arr[left]和arr[right]的值。交换比较的方向，即从数组的头部left的位置向后扫描。

  (2).如果arr[lleft]的值小于基准值pivot的话，left++，当arr[right]>=key的时候，交换arr[left]和arr[right]的值。再次交换比较的方向，数组从尾部high的位置从后往前扫描。

  (3)不断重复1.2步，最终直到(left==right)的时候，low的位置就是该基准值在数组中的正确索引位置。

  3.2.1.2 挖坑法

  具体的步骤：

  1. 我们需要设定一个基准值(一般为序列的最左边元素，也可以是最右边元素)此时最左边的是一个坑。
  2. 开辟两个指针left和right，分别指向序列的头节点和尾节点(选取的基准值在左边，则从右边开始出发，反之，异然)
  3. 假如让right从右往左走，找到第一个比基准小的元素，如果有，则把该值放到坑里，lefr从前往后遍历。
  4. 找到比基准大的元素的下标，然后用这个元素放到坑里。
  5. 依次循环，直到left指针和right指针重合时，我们把基准值放入这连个指针重合的位置。

  举个例子：

  4，7，6，5，3，2，8，1

  我们选定基准元素Pivot，并记住这个位置index，这个位置相当于一个“坑”。并且设置两个指针left和right，指向数列的最左和最右两个元素：

  
  接下来，从right指针开始，把指针所指向的元素和基准元素做比较。如果比pivot大，则right指针向左移动；如果比pivot小，则把right所指向的元素填入坑中。

  在当前数列中，1<4，所以把1填入基准元素所在位置，也就是坑的位置。这时候，元素1本来所在的位置成为了新的坑。同时，left向右移动一位。
  

  接下来，我们切换到left指针进行比较。如果left指向的元素小于pivot，则left指针向右移动；如果元素大于pivot，则把left指向的元素填入坑中。

  在当前数列中，7>4，所以把7填入index的位置。这时候元素7本来的位置成为了新的坑。同时，right向左移动一位。
  
  8>4，元素位置不变，right左移
  
  2<4，用2来填坑，left右移，切换到left。
  
  6>4，用6来填坑，right左移，切换到right。
  
  3<4，用3来填坑，left右移，切换到left。
  
  5>4，用5来填坑，right右移。这时候left和right重合在了同一位置。
  

  这时候，把之前的pivot元素，也就是4放到index的位置。此时数列左边的元素都小于4，数列右边的元素都大于4，这一轮交换终告结束。
  

  3.2.1.3 前后指针法

  什么是前后遍历，前后遍历就是两个指针一前一后，从头开始遍历，当遇到比基准小的值，俩个指针往后走一步，遇到比基准值大的就prev指针不动，cur往后走，当cur遇到比基准值小的就停下来， 然后cur指针每一次停止俩个指针之间的位置比较一下，如果俩个之间的差不是一的话，就交换俩个位置的数据，一直循环，直到遍历结束，用prev的后一个不是基准元素的位置的话，就，让prev和基准值进行交换。

  3.2.2 代码实现

  3.2.2.1 Hoare法

   private static int partitionHoare(int[] array,int left,int right) {//hoare法
          int i = left;
          int pivot = array[left];
          while (left < right) {
              //left < right &&  这个条件不能少 预防后面都比基准大
              while (left < right && array[right] >= pivot) {
                  right--;
              }
              //代码走到这里表示right下标的值 小于pivot
              while (left < right && array[left] <= pivot) {
                  left++;
              }
              //left下标的值 大于pivot
              swap(array,left,right);
          }
          //交换 和 原来的left
          swap(array,left,i);
          return left;
      }
  

  3.2.2.2 挖坑法

    private static int partition(int[] array,int left,int right) {//挖坑法,优先使用
          int pivot = array[left];
          while (left < right) {
              //left < right &&  这个条件不能少 预防后面都比基准大
              while (left < right && array[right] >= pivot) {
                  right--;
              }
              array[left] = array[right];
              //right下标的值 小于pivot
              while (left < right && array[left] <= pivot) {
                  left++;
              }
              array[right] = array[left];
          }
          //交换 和 原来的left
          array[left] = pivot;
          return left;
      }
  

  3.2.2.3 前后指针法

      private static int partition(int[] array, int left, int right) {//前后指针法
          int prev = left ;
          int cur = left+1;
          while (cur <= right) {
              if(array[cur] < array[left] && array[++prev] != array[cur]) {
                  swap(array,cur,prev);
              }
              cur++;
          }
          swap(array,prev,left);
          return prev;
      }
  

  3.2.3 特性分析

  1. 时间复杂度
     时间复杂度为O(n * logn)
     最坏情况达到O(n * 2)
  2. 空间复杂度
     空间复杂度为O(logn)
  3. 稳定性
     不稳定。

  3.2.3 快速排序的优化

  3.2.3.1 规模较小的优化

  每次递归的时候，数据都是再慢慢变成有序的
  当数据量少且趋于有序的时候，我们可以直接使用插入排序进行优化

    public static int partitionHole(int[] array,int low,int high){
          int tmp = array[low];
          while(low < high) {
              while (low < high && array[high] >= tmp){
                  high--;
              }
              array[low] = array[high];
              while (low < high && array[low] <= tmp){
                  low++;
              }
              array[high] = array[low];
          }
          array[low] = tmp;
          return low;
   
      }
    public static void quickSort(int[] array,int left,int right){
          if(left >= right) return;
          if(right-left+1 <= 10000){  //某个区间内的小规模排序直接插入排序
              //进行插入排序
              insertSortRange(array,left,right);
              return;
          }
          int pivot = partitionHole(array,left,right);
          quickSort(array,left,pivot-1);
          quickSort(array,pivot+1,right);
      }
    public static void insertSortRange(int[] array,int low, int end){
          for(int i = low+1 ; i<=end ;i++){
              int tmp = array[i];
              int j = i-1;
              for(; j >= low ; j--){
                  if(array[j] > tmp){
                      array[j+1] = array[j];
                  }else{
                      break;
                  }
              }
              array[j+1] = tmp;
          }
      }
  

  但是这个优化并没有根本解决 有序情况下 递归深度太深的优化

  3.2.3.2 三数取中法

  我们用 三数取中法 选key
  三数取中：头，尾，中间元素中 大小居中 的那一个，再把这个元素和队头元素互换，作为key

   public static int partitionHole(int[] array,int low,int high){
          int tmp = array[low];
          while(low < high) {
              while (low < high && array[high] >= tmp){
                  high--;
              }
              array[low] = array[high];
              while (low < high && array[low] <= tmp){
                  low++;
              }
              array[high] = array[low];
          }
          array[low] = tmp;
          return low;
   
      }    
  //三数取中，找到首，中，尾三个数中 中等大小的数的下标
      private static int medianOfThreeIndex(int[] array, int left, int right){
          int mid = left + ((right-left)>>>1);
          //int mid = (right+left)/2 ;
          if(array[left] < array[right]){
              if(array[mid] < array[left]){
                  return left;
              }else if(array[mid] > array[right]){
                  return right;
              }else{
                  return mid;
              }
          }else{
              if(array[mid] < array[right]){
                  return right;
              }else if(array[mid] > array[left]){
                  return left;
              }else{
                  return mid;
              }
          }
      }
      public static void quickSort(int[] array,int left,int right){
          if(left >= right) return;
          //1.某个区间内的小规模排序直接插入排序【优化的是区间内的比较】
          if(right-left+1 <= 10000){
              //进行插入排序
              insertSortRange(array,left,right);
              return;
          }
          //2.三数取中法【优化的是本身的分割】
          int index = medianOfThreeIndex(array,left,right);
          swap(array,left,index);
   
          int pivot = partitionHole(array,left,right);
          quickSort(array,left,pivot-1);
          quickSort(array,pivot+1,right);
      }
  

  3.2.3.3 非递归实现快速排序

  我们需要用到栈.

  我们之前是在已经确定基准点之后，对剩余的区间递归进行同样的操作

  我们现在创建一个栈，把剩余区间的左、右位置的下标分别放入栈中，如图是已经找到一个基准3的情况

  
  然后弹出栈顶一个元素9给H，再弹出一个栈顶元素6给L，根据新的L和H找到新的基准，再重复上面的操作

  

  //挖坑法
      public static int partitionHole(int[] array,int low,int high){
          int tmp = array[low];
          while(low < high) {
              while (low < high && array[high] >= tmp){
                  high--;
              }
              array[low] = array[high];
              while (low < high && array[low] <= tmp){
                  low++;
              }
              array[high] = array[low];
          }
          array[low] = tmp;
          return low;
      } 
  //快速排序（非递归）
      public static void quickSortNor(int[] array,int left,int right){
        Stack<Integer> stack = new Stack<>();
          int pivot = partitionHole(array,left,right);
          if(pivot > left+1){
              //说明左边有两个或两个以上数据
              stack.push(left);
              stack.push(pivot-1);
          }
          if(pivot < right-1){
              stack.push(pivot+1);
              stack.push(right);
          }
          while (!stack.isEmpty()){
              right = stack.pop();
              left = stack.pop();
   
              pivot = partitionHole(array,left,right);
              if(pivot > left+1){
                  //说明左边有两个或两个以上数据
                  stack.push(left);
                  stack.push(pivot-1);
              }
              if(pivot < right-1){
                  stack.push(pivot+1);
                  stack.push(right);
              }
          }
      }
  

  4、归并排序

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

  4.1 递归实现归并排序

  4.1.1 思路

  分治思想
  
  当我们要排序这样一个数组的时候，归并排序法首先将这个数组分成一半。如图：
  
  然后想办法把左边的数组给排序，右边的数组给排序，之后呢再将它们归并起来。当然了当我们对左边的数组和右边的素组进行排序的时候，再分别将左边的数组和右边的数组分成一半，然后对每一个部分先排序，再归并。如图：
  
  对于上面的每一个部分呢，我们依然是先将他们分半，再归并，如图：
  
  分到一定细度的时候，每一个部分就只有一个元素了，那么我们此时不用排序，对他们进行一次简单的归并就好了。如图：
  
  归并到上一个层级之后继续归并，归并到更高的层级，如图：
  
  

  4.1.2 代码实现

      public static void MergeSort(int[] array) {
          mergeSortChild(array,0,array.length-1);
      }
   
      private static void mergeSortChild(int[] array,int left,int right) {
          if(left == right) {
              return;
          }
          int mid = (left+right) / 2;
          mergeSortChild(array,left,mid);
          mergeSortChild(array,mid+1,right);
          //合并
          merge(array,left,mid,right);
  }
   
      private static void merge(int[] array,int left,int mid,int right) {//归并
          int s1 = left;
          int e1 = mid;
          int s2 = mid+1;
          int e2 = right;
          int[] tmpArr = new int[right-left+1];
          int k = 0;//表示tmpArr 的下标
          while (s1 <= e1  && s2 <= e2) {
              if(array[s1] <= array[s2]) {
                  tmpArr[k++] = array[s1++];
              }else{
                  tmpArr[k++] = array[s2++];
              }
          }
          while (s1 <= e1) {
              tmpArr[k++] = array[s1++];
          }
          while (s2 <= e2) {
              tmpArr[k++] = array[s2++];
          }
          //tmpArr当中 的数据 是right  left 之间有序的数据
          for (int i = 0; i < k; i++) {
              array[i+left] = tmpArr[i];
          }
      }
  

  4.1.3 特性分析

  1. 时间复杂度
     时间复杂度：O(N*logN)。
  2. 空间复杂度
     空间复杂度：O(N)。
  3. 稳定性
     稳定的

  4.2 非递归实现归并排序

  4.2.1 思路

  根据递归的结构不难看出，归并排序的本质也是分割区间分别进行处理，并且归并前要求两个区间范围要分别有序，因此第一步是通过迭代来控制边界到达最小的区间也就是两个区间重叠的位置开始归并，然后不断扩大区间继续归并。

  4.2.2 代码实现

    public static void MergeSort1(int[] array) {
          int gap = 1;
          while (gap < array.length) {
              for (int i = 0; i < array.length; i += gap*2) {
                  int left = i;
                  int mid = left + gap -1;
                  int right = mid+gap;
                  if(mid >= array.length) {
                      mid = array.length-1;
                  }
                  if(right >= array.length) {
                      right = array.length-1;
                  }
                  merge(array,left,mid,right);
              }
              gap *= 2;
          }
      }