简述

快速排序是一种排序执行效率很高的排序算法，它利用分治法来对待排序序列进行分治排序，它的思想主要是通过一趟排序将待排记录分隔成独立的两部分，其中的一部分比关键字小，后面一部分比关键字大，然后再对这前后的两部分分别采用这种方式进行排序，通过递归的运算最终达到整个序列有序，下面我们简单进行阐述。

快排思路

我们从一个数组来逐步逐步说明快速排序的方法和思路。

  1. 假设我们对数组{7, 1, 3, 5, 13, 9, 3, 6, 11}进行快速排序。
  2. 首先在这个序列中找一个数作为基准数，为了方便可以取第一个数。
  3. 遍历数组，将小于基准数的放置于基准数左边，大于基准数的放置于基准数右边。
  4. 此时得到类似于这种排序的数组{3, 1, 3, 5, 6, 7, 9, 13, 11}。
  5. 在初始状态下7是第一个位置，现在需要把7挪到中间的某个位置k，也即k位置是两边数的分界点。
  6. 那如何做到把小于和大于基准数7的值分别放置于两边呢，我们采用双指针法，从数组的两端分别进行比对。
  7. 先从最右位置往左开始找直到找到一个小于基准数的值，记录下该值的位置（记作 i）。
  8. 再从最左位置往右找直到找到一个大于基准数的值，记录下该值的位置（记作 j）。
  9. 如果位置i<j，则交换i和j两个位置上的值，然后继续从(j-1)的位置往前和(i+1)的位置往后重复上面比对基准数然后交换的步骤。
  10. 如果执行到i==j，表示本次比对已经结束，将最后i的位置的值与基准数做交换，此时基准数就找到了临界点的位置k，位置k两边的数组都比当前位置k上的基准值或都更小或都更大。
  11. 上一次的基准值7已经把数组分为了两半，基准值7算是已归位（找到排序后的位置）。
  12. 通过相同的排序思想，分别对7两边的数组进行快速排序，左边对[left, k-1]子数组排序，右边则是[k+1, right]子数组排序。
  13. 利用递归算法，对分治后的子数组进行排序。

快速排序之所以比较快，是因为相比冒泡排序，每次的交换都是跳跃式的，每次设置一个基准值，将小于基准值的都交换到左边，大于基准值的都交换到右边，这样不会像冒泡一样每次都只交换相邻的两个数，因此比较和交换的此数都变少了，速度自然更高。当然，也有可能出现最坏的情况，就是仍可能相邻的两个数进行交换。
快速排序基于分治思想，它的时间平均复杂度很容易计算得到为O(N_log_N)。

代码实现：

java：

  1. public class QuickSorting {
  2.     public static void main(String[] args) {
  3.         int[] array = {3, 5, 4, 2, 1,6,2,4};
  4.         quickSort(array, 0, array.length - 1);
  5.     }
  7.     public static void quickSort(int[] array, int low, int high) {
  8.         if (low > high) {
  9.             return;
  10.         }
  11.         int base = array[low];
  12.         int i = low, j = high;
  13.         while (i != j) {
  14.             while (array[j] > base && i < j) {
  15.                 j--;
  16.             }
  17.             while (array[i] <= base && i < j) {
  18.                 i++;
  19.             }
  20.             if (i < j) {  //大的放在右边，小的移到左边
  21.                 int temp = array[i];
  22.                 array[i] = array[j];
  23.                 array[j] = temp;
  24.             }
  25.             System.out.println("循环内部");
  26.             Arrays.stream(array).forEach(System.out::print);
  27.         }
  28.         array[low] = array[i];
  29.         array[i] = base;
  30.         System.out.println("循环外部");
  31.         Arrays.stream(array).forEach(System.out::print);
  32.         System.out.println("递归小于部分");
  33.         quickSort(array, low, i - 1);
  34.         System.out.println("递归大于部分");
  35.         quickSort(array, i + 1, high);
  36.     }
  37. }

python：

  1. import numpy as np
  2. def quickSort(list):
  3.     if(len(list))<2:
  4.         return list
  5.     mid=list[len(list)//2]
  6.     print('mid:',mid)
  7.     list.remove(mid)
  8.     left,right=[],[]
  9.     for i in list:
  10.         if i<mid:
  11.             left.append(i)
  12.         else:
  13.             right.append(i)
  14.     return quick_sort(left)+[mid]+quick_sort(right)

高逼格写法：

  1. #快排
  2. quick_sort = lambda array: array if len(array) <= 1 \
  3.     else quick_sort([item for item in array[1:] if item <= array[0]]) \
  4.          + [array[0]] \
  5.          + quick_sort([item for item in array[1:] if item > array[0]])
  7. quick_sort([2,5,9,3,7,1,5,1])