排序算法之快速排序

目录

• 一、简介
• 二、代码实现
• 三、应用场景

  ---

  一、简介

  算法	平均时间复杂度	最好时间复杂度	最坏时间复杂度	空间复杂度	排序方式	稳定性
  快速排序	O( N N N log ⁡ 2 N \log_{2}N log2​N)	O( N N N log ⁡ 2 N \log_{2}N log2​N)	O(n^2)	O( log ⁡ 2 N \log_{2}N log2​N)	In-place	不稳定

  稳定：如果A原本在B前面，而A=B，排序之后A仍然在B的前面；

  不稳定：如果A原本在B的前面，而A=B，排序之后A可能会出现在B的后面；

  时间复杂度： 描述一个算法执行所耗费的时间；

  空间复杂度：描述一个算法执行所需内存的大小；

  n：数据规模；

  k：“桶”的个数；

  In-place：占用常数内存，不占用额外内存；

  Out-place：占用额外内存。

  快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

  快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

  快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。

  快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

  

  算法步驟：

  • 从数列中挑出一个元素，称为 “基准”（pivot）;
  • 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
  • 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

    ---

    二、代码实现

    public class QuickSort {
        public static void quickSort(int[] arr) {
            sort(arr, 0, arr.length - 1);
        }
        private static void sort(int[] arr, int left, int right) {
            if (left