十大排序算法总结

各个排序算法的时间复杂度及稳定性

排序方法	时间复杂度(最坏)	时间复杂度(最好)	时间复杂度(平均)	空间复杂度	排序方式	稳定性
冒泡排序	O(n^2^)	O(n)	O(n^2^)	O(1)	in-place	稳定
选择排序	O(n^2^)	O(n^2^)	O(n^2^)	O(1)	in-place	不稳定
插入排序	O(n^2^)	O(n^2^)	O(n)	O(1)	in-place	稳定
希尔排序	O(n^2^)	O(n)	O(n^1.3^)	O(1)	in-place	不稳定
快速排序	O(n^2^)	O(nlog n)	O(nlog n)	O(log n)	in-place	不稳定
归并排序	O(nlog n)	O(nlog n)	O(nlog n)	O(n)	out-place	稳定
堆排序	O(nlog n)	O(nlog n)	O(nlog n)	O(1)	in-place	不稳定
计数排序	O(n + k)	O(n + k)	O(n + k)	O(k)	out-place	稳定
桶排序	O(n^2^)	O(n + k)	O(n + k)	O(n + k)	out-place	稳定
基数排序	O(n * k)	O(n * k)	O(n * k)	O(n + k)	out-place	稳定

冒泡排序

• 冒泡排序作为最基础的排序，博主大学各项期末考试就被考过至少三次，在这里给出优化版写法。

    public class Sort {
      public void BubbleSort(int[] arr) {
          for (int i = 1; i < arr.length; i++) {
              //flag若为true,则此次循环没有交换元素，即待排序数组已经有序
              boolean flag = true;
              for (int j = 0; j < arr.length - i; j++) {
                  if (arr[j] > arr[j + 1]) {
                      swap(arr, j, j + 1);
                      flag = false;
                  }
              }
              if (flag) {
                  break;
              }
          }
      }
  
      private static void swap(int[] arr, int i, int j) {
          arr[i] = arr[i] ^ arr[j];
          arr[j] = arr[i] ^ arr[j];
          arr[i] = arr[i] ^ arr[j];
      }
  }

选择排序

1.不断在未排序序列中找到最小的元素，与本轮循环起始元素比较。
2.若此元素较小，则更新最小元素下标。
3.交换本轮起始位置元素及最小位置元素。
4.重复上述步骤。

public class Sort {
    public void selectSort(int[] arr) {

        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;//记录最小值下标
            for (int j = arr.length - 1; j > i; j--) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;//更新最小值下标
                }
            }
            if (i != minIndex) {
                swap(arr, i, minIndex);
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }
}

插入排序

1.把第一个元素看作已有序。
2.从第二个元素开始依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。

public class Sort {
    public void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > tmp) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = tmp;
        }
    }
}

希尔排序

• 希尔排序是对插入排序的优化，在元素无序且step > 1时，分组并交换能让无序序列更快趋于有序，此时就可以发挥序列趋于有序时插入排序更快的优势。
• 但需要注意的是，如果数组本就有序或趋于有序，插入排序要优许希尔排序，因为它省去了分组的过程，直接对数组进行排序。

  public class Sort {
      public void shellSort(int[] arr) {
          for (int step = arr.length / 2; step > 0; step /= 2) {
              for (int i = step; i < arr.length; i += step) {
                  int tmp = arr[i];
                  int j = i - step;
                  while (j > 0 && arr[j] > tmp) {
                      arr[j + step] = arr[j];
                      j -= step;
                  }
                  arr[j + step] = tmp;
              }
          }
      }
  }

快速排序

• 快排，顾名思义就是“快”，就连JDK自带的Arrays.sort()在传入整形参数时也会调用其自身的双轴快速排序,可见其重要性。
• 快排体现了“分治”的思想，它以基准值为根节点将一个数组转化为二叉树进行深度优先查找，并依次将符合条件的元素放入对应的位置。
• 要想找到基准，最关键的莫过于partition()方法，再构造这个方法前，我们先搭起快排的框架。

  public void quickSort(int[] arr, int L, int R){
      if (L >= R) return;
      int pivot = partition(arr, L, R);
      quickSort(arr, L, pivot - 1);
      quickSort(arr, pivot + 1, R);
  }

• 如果遇上了数组量巨大且有序的情况，插入排序看了直接笑嘻，但这是快排的最坏情况，因为若不做处理，二叉树会退化为一条单链表，最后出现StackOverFlowError()，要解决栈溢出问题，我们要先引入三数取中法

  //将数组起始下标，中间下标与最后一个下标位置的元素作比较，返回中间值
  private static int MiddleOfThree(int[] arr, int L, int R) {
      int M = L + ((R - L) >> 1);
      if (arr[L] < arr[R]) {//左小右大
          if (arr[M] < arr[L]) {
              return L;
          } else if (arr[M] > arr[R]) {
              return R;
          } else {
              return M;
          }
      } else {//左大右小
          if (arr[M] > arr[L]) {
              return L;
          } else if (arr[M] < arr[R]) {
              return R;
          } else {
              return M;
          }
      }
  }

• 这样做的好处是：第一次返回的基准值pivot能保证是一个“不大不小”的元素，这样就算遇到了最差情况，它仍然会演化成一颗二叉树。
• 下面正式介绍partition()方法

分割方法

Hoare法

/*
    1.从右往左找比pivot小的值，找到后停下
    2.从左往右找比pivot大的值，找到后停下
    3.交换左右的值
    4.当L == R,退出循环并交换pivot和arr[L],使得pivot左边都小于它，右边都大于它
 */
private static int partition(int[] arr, int L, int R) {
    int pivotVal = arr[L];
    int pivotIdx = L;
    while (L < R) {
        while (L < R && arr[R] >= pivotVal) {//直到找到小于pivotVal的下标
            R--;
        }
        while (L < R && arr[L] <= pivotVal) {//直到找到大于pivotVal的下标
            L++;
        }
        swap(arr, L, R);
    }
    swap(arr, L, pivotIdx);
    return L;
}

• 初始基准值为arr[L],就要从右边开始找，否则可能出现最后基准值交换后又换回来的情况。
• >=和<=不可改为>和<，若左右元素相等，就进入了死循环。

挖坑法

/*
    1.将arr[L]保存在临时变量pivotVal中
    2.从右往左找比pivotVal小的值，找到后停下并把它赋给L
    3.从左往右找比pivotVal大的值，找到后停下并把它赋给R
    4.直到L和R相遇，退出循环并把pivotVal和arr[L]交换
 */
private static int partition(int[] arr, int L, int R) {
    //此时的arr[L]已经通过三数取中法交换得到中间值
    int pivotVal = arr[L];
    while (L < R) {
        while (L < R && arr[R] >= pivotVal) {
            R--;
        }
        arr[L] = arr[R];//此时已经找到比pivotVal小的值，把它赋给arr[L]
        while (L < R && arr[L] <= pivotVal) {
            L++;
        }
        arr[R] = arr[L];//此时已经找到比pivotVal大的值，把它赋给arr[R]
    }
    arr[L] = pivotVal;//此时L和R已相遇，把pivotVal赋给任意一个即可
    return L;
}

快慢指针法

/*
    1.定义cur起始在prev后一个位置
    2.如果arr[cur] < arr[L], 即快指针找到了小于基准值的位置，此时让慢指针向前走一步
    3.如果快慢指针的值不相等，交换
    4.退出循环，交换慢指针与原来的基准值arr[L]并返回
*/
private static int partitionPoint(int[] arr, int L, int R) {
    int prev = L;
    int cur = L + 1;
    while (cur < R) {
        while (arr[cur] < arr[L] && arr[++prev] != arr[cur]) {
            swap(arr, prev, cur);
        }
        cur++;
    }
    swap(arr, prev, L);
    return prev;
}

迭代版

• 下面我们借助栈来实现快排的迭代版本。

  public class Sort {
      public void quickSortItr(int[] arr, int L, int R) {
          Stack<Integer> stack = new Stack<>();
          int M = MiddleOfThree(arr, L, R);//三数取中
          swap(arr, L, M);
          int pivot = partition(arr, L, R);//得到基准值下标
          /*
              把基准值两边的左、右边界下标入栈
              此处判断L + 1和R - 1的原因：
              当数组长度较小，例如数组长度小于4时，仅靠MiddleOfThree()就可完成排序,
              不需要入栈，若改为仅判断L和R，可能会导致重复的下标入栈。
           */
          if (L + 1 < pivot) {
              stack.push(L);
              stack.push(pivot - 1);
          }
          if (R - 1 > pivot) {
              stack.push(pivot + 1);
              stack.push(R);
          }
          //重复上述过程
          while (!stack.isEmpty()) {
              R = stack.pop();
              L = stack.pop();
              M = MiddleOfThree(arr, L, R);
              swap(arr, L, M);
              pivot = partition(arr, L, R);
              if (L + 1 < pivot) {
                  stack.push(L);
                  stack.push(pivot - 1);
              }
              if (R - 1 > pivot) {
                  stack.push(pivot + 1);
                  stack.push(R);
              }
          }
      }
  }

升级版

• 我们不难发现，上述的方法都是以单个下标作为基准值，下面我借用荷兰国旗问题给出快排的优化版本。它引入两个基准值下标，将数组分为小于区、等于区、大于区三个区域，这样我们就能一次排好一批数。

  此算法理论上的最差时间复杂度也为*O(nlog n)*，每次递归它都随机从数组长度内取出一个值与小于区的边界值做交换，这样就使得人为无法造出最差情况，具体的数学推导不在这里展开分析。

  public class Sort {
      public void quickSortPlus(int[] arr, int L, int R) {
          if (L < R) {
              //从数组长度中随机获取一个下标作为基准值，将每种情况概率化
              int randomFlag = L + (int) (Math.random() * (R - L + 1));
              swap(arr, L, randomFlag);
              //返回等于区的左右边界，若等于区只有一个数，则返回两个相同的值
              int[] pivot = partitionPlus(arr, L, R);
              quickSortPlus(arr, L, pivot[0] - 1);
              quickSortPlus(arr, pivot[1] + 1, R);
          }
      }
  
      private static int[] partitionPlus(int[] arr, int L, int R) {
          int less = L;//小于区左边界
          int more = R;//大于区有边界
          while (L < more + 1) {
              //如果小于区的值 < 大于区的值,把小于区的值放入小于区左边界内
              if (arr[L] < arr[R]) {
                  swap(arr, less++, L++);
                  //如果小于区的值大于 > 大于区的值,交换并把换过来的值纳入大于区
              } else if (arr[L] > arr[R]) {
                  swap(arr, L, more--);
                  //等于则不做处理
              } else {
                  L++;
              }
          }
          //返回的less和more则为等于区的左右下标
          return new int[]{less, more};
      }
  
      private static void swap(int[] arr, int l, int r) {
          int tmp = arr[l];
          arr[l] = arr[r];
          arr[r] = tmp;
      }
  }

归并排序

• 归并排序是一种典型的空间换时间的排序算法，它开辟了一个与原数组等大小的辅助数组用来存储每次分治的结果，这就使得它的空间复杂度来到了O(n),它也是本文比较排序算法中唯一一个需要计算机额外开辟内存(out-place)的排序算法。
• mergeSort()体现了分的过程，而merge()则体现了治的过程。

  public class Sort {
      public void mergeSort(int[] arr, int L, int R) {
          if (L >= R) return;
          int M = L + ((R - L) >> 1);
          mergeSort(arr, L, M);
          mergeSort(arr, M + 1, R);
          merge(arr, L, M, R);
      }
  
      private static void merge(int[] arr, int L, int M, int R) {
          int[] help = new int[R - L + 1];
          int i = 0;//help数组下标
          int p1 = L, p2 = M + 1;//M将数组分割为左右区域,p1,p2分别为两区域起始下标
          while (p1 <= M && p2 <= R) {
              help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
          }
          //若两数组不等长,则把长的数组剩余元素移到help数组中
          while (p1 <= M) {
              help[i++] = arr[p1++];
          }
          while (p2 <= R) {
              help[i++] = arr[p2++];
          }
          for (i = 0; i < help.length; i++) {
              arr[L + i] = help[i];//L的值可能因递归发生变动,L + i防止后面的值把前面的值覆盖
          }
      }
  }

迭代版

public class Sort {
    public void mergeSortItr(int[] arr) {
        int step = 1;
        while (step < arr.length) {
            for (int i = 0; i < arr.length; i += step * 2) {
                int L = i;
                int M = i + step - 1;
                int R = M + step;
                //step二倍扩容可能导致M和R越界，故修正下标
                if (M >= arr.length) {
                    M = arr.length - 1;
                }
                if (R >= arr.length) {
                    R = arr.length - 1;
                }
                merge(arr, L, M, R); //沿用递归版本的merge()
            }
            step *= 2;
        }
    }
}

堆排序

• 堆排序本质上也是利用二叉树构建了大顶堆或小顶堆，通过不断的heapify()过程实现。
• JDK中自带的小顶堆名为PriorityQueue,可以使用它解决topK问题，我们可以实现其内置的Comparator()接口来使用自定义排序。
• 下面我们使用手动构建大顶堆的方式实现数组从小到大的排序。

构建大顶堆

private static void buildMaxHeap(int[] arr, int len) {
    for (int i = len - 1; i >= 0; i--) {
        heapify(arr, i, len);//将父节点i传入heapify()方法进行向下调整
    }
}

private static void heapify(int[] arr, int p, int len) {
    int L = p * 2 + 1;//左子节点
    int R = p * 2 + 2;//假设有右子节点
    int maxIndex = p;//记录最大值下标
    //在L和中找到最大值下标
    if (L < len && arr[L] > arr[maxIndex]) {
        maxIndex = L;
    }
    if (R < len && arr[R] > arr[maxIndex]) {
        maxIndex = R;
    }
    //把最大值换到父节点位置，构建局部大顶堆
    if (maxIndex != p) {
        swap(arr, maxIndex, p);
        //递归，直至从p往下的所有节点均为大顶堆
        heapify(arr, maxIndex, len);
    }
}

private static void swap(int[] arr, int L, int R) {
    arr[L] = arr[L] ^ arr[R];
    arr[R] = arr[L] ^ arr[R];
    arr[L] = arr[L] ^ arr[R];
}

实现堆排序

public class Sort {
    public void heapSort(int[] arr) {
        int len = arr.length;
        buildMaxHeap(arr, len);
        /*
            1.利用大根堆堆顶元素恒为最大值的性质，将堆顶元素与最后一个元素交换
            2.将换下去的最大元素移出检测范围
            3.heapify()将数组修正为大顶堆
         */
        for (int i = len - 1; i >= 1; i--) {
            swap(arr, i, 0);
            len--;
            heapify(arr, 0, len);
        }
    }
}

计数排序

• 从这里开始的三种排序算法，都不是基于比较的排序算法，计数排序在输入的元素在n个0到k之间的整数时，其效率优于任何比较排序算法。

  public class Sort {
      public void countingSort(int[] arr) {
          int[] maximum = getMaximum(arr);
          int[] help = new int[maximum[1] - maximum[0] + 1];//建立一个大小为最值之差的计数数组
          for (int i = 0; i < arr.length; i++) {
              help[arr[i] - maximum[0]]++;//记录数组中每个值与最小值的差值
          }
          int index = 0;
          for (int i = 0; i < help.length; i++) {
              //把计数数组中的值加上差值放入原数组
              while (help[i] > 0) {
                  int val = i + maximum[0];
                  arr[index++] = val;
                  help[i]--;
              }
          }
      }
  
      //获取数组最值
      private int[] getMaximum(int[] arr) {
          int min = Integer.MAX_VALUE;
          int max = Integer.MIN_VALUE;
          for (int i = 0; i < arr.length; i++) {
              if (arr[i] < min) {
                  min = arr[i];
              }
              if (arr[i] > max) {
                  max = arr[i];
              }
          }
          return new int[]{min, max};
      }
  }

桶排序

基数排序