快排是一种很优雅的排序算法。

思想

快排基于分治，分治即分而治之，强调的是将复杂问题通过分解，变为多个简单子问题，进而解决。举个不恰当栗子，比如你想一年12个月存12万，那么一种方法是每个月存够一万，一年以后不就12万了。

方法

1. 选取基准元素
2. 将比基准元素小的元素均放在基准元素左边，反之，均放在基准元素右边
3. 对上述问题的子集，递归过程1和2

时间复杂度

平均时间复杂是O(n*logn) 最坏的情况是O(n^2)

稳定性

它基于比较 是不稳定的排序算法

python 实现

这里给出两个版本，一个是基准元素选取是动态的，一个是基准元素选取固定

基准元素动态

# 调整函数
# 思想：利用l和r指针，从左右两侧向中间扫描移动，准确说是与base_index不在同一侧的指针不断向base_index靠拢，在此过程中base_index是跳跃式移动的。
# 在r指针向左移动过程中，若发现某个元素值小于基准元素值，那么将其值调整到现在基准元素位置，并且将现在基准元素指针调整到r指针位置。
# 同理，若base_index与l指针不在同一侧，则向右移动l指针。在l指针向右移动过程中，若发现某个元素值大于基准元素值，那么将其值调整到现在基准元素位置，并且将现在基准元素指针调整到r指针位置。
# 最后，l和r指针相遇，将基准元素值赋给他俩所在位置。
def adjust_list(num_list, base_index, l, r):
  base_value = num_list[base_index]
  while l < r:
    while num_list[r] >= base_value and l < r:
      r = r - 1
    num_list[base_index] = num_list[r]
    base_index = r

    while num_list[l] < base_value and l < r:
      l = l + 1
    num_list[base_index] = num_list[l]
    base_index = l

  num_list[l] = base_value
  return l

# 实际的排序函数
# l(left)为左边界移动指针，r(right)为右边界移动指针
def qsort_inner(num_list, l, r):
  if l >=r:
    return
  # base_index 为计算得到的基准元素索引，这里简单的写为与l指针一致
  base_index = l
  i = adjust_list(num_list, base_index, l, r)
  qsort_inner(num_list, l, i - 1)
  qsort_inner(num_list, i + 1, r)

# 最外层封装函数
def qsort(num_list):
  qsort_inner(num_list, 0, len(num_list)-1)

基准元素固定

# 基准元素选取固定与最左侧l指针所在元素一致，故可以少写一个base_index指针，此时的移动原则是：不与基准元素保持同一侧的指针主动朝基准元素所在位置一步一步移动，基准元素仍跳跃移动。
def adjust_list(num_list, l, r):
  vitem = num_list[l]
  while l < r:
    while num_list[r] >= vitem and l < r:
      r = r - 1
    num_list[l] = num_list[r]
    
    while num_list[l] < vitem and l < r:
      l = l + 1
    num_list[r] = num_list[l]
  num_list[l] = vitem

  return l

def qsort_inner(num_list, l, r):
  if l >=r:
    return
  base_index = l
  i = adjust_list(num_list, base_index, l, r)
  qsort_inner(num_list, l, i - 1)
  qsort_inner(num_list, i + 1, r)

def qsort(num_list):
  qsort_inner(num_list, 0, len(num_list)-1)

最后也顺带给出ES6实现吧

class QuickSort {
  adjust_list = (num_list, l, r) => {
    const vitem = num_list[l]
    while(l < r) {
      while(num_list[r] >= vitem && l < r) {
        r = r - 1
      }
      num_list[l] = num_list[r]
      while(num_list[l] < vitem && l < r) {
        l = l + 1
      }
      num_list[r] = num_list[l]
    }
    num_list[l] = vitem

    return l
  }

  qsort_inner = (num_list, l, r) => {
    if(l >= r) {
      return
    }
    const i = this.adjust_list(num_list, l, r)
    this.qsort_inner(num_list, l, i - 1)
    this.qsort_inner(num_list, i + 1, r)
  }

  qsort = (num_list) => {
    this.qsort_inner(num_list, 0, num_list.length - 1);
  }
}