# Quick Sort - 快速排序

1. 定基准——首先随机选择一个元素最为基准
2. 划分区——所有比基准小的元素置于基准左侧，比基准大的元素置于右侧
3. 递归调用——递归地调用此切分过程

## out-in-place - 非原地快排

#!/usr/bin/env python

def qsort1(alist):
print(alist)
if len(alist) <= 1:
return alist
else:
pivot = alist[0]
return qsort1([x for x in alist[1:] if x < pivot]) + \
[pivot] + \
qsort1([x for x in alist[1:] if x >= pivot])

unsortedArray = [6, 5, 3, 1, 8, 7, 2, 4]
print(qsort1(unsortedArray))


[6, 5, 3, 1, 8, 7, 2, 4]
[5, 3, 1, 2, 4]
[3, 1, 2, 4]
[1, 2]
[]
[2]
[4]
[]
[8, 7]
[7]
[]
[1, 2, 3, 4, 5, 6, 7, 8]


『递归 + 非原地排序』的实现虽然简单易懂，但是如此一来『快速排序』便不再是最快的通用排序算法了，因为递归调用过程中非原地排序需要生成新数组，空间复杂度颇高。list comprehension 大法虽然好写，但是用在『快速排序』算法上就不是那么可取了。

### 复杂度分析

$\sum_{i=0}^n (n-i+1) = O(n^2)$

## in-place - 原地快排

### Python

#!/usr/bin/env python

def qsort2(alist, l, u):
print(alist)
if l >= u:
return

m = l
for i in xrange(l + 1, u + 1):
if alist[i] < alist[l]:
m += 1
alist[m], alist[i] = alist[i], alist[m]
# swap between m and l after partition, important!
alist[m], alist[l] = alist[l], alist[m]
qsort2(alist, l, m - 1)
qsort2(alist, m + 1, u)

unsortedArray = [6, 5, 3, 1, 8, 7, 2, 4]
print(qsort2(unsortedArray, 0, len(unsortedArray) - 1))


### Java

public class Sort {
public static void main(String[] args) {
int unsortedArray[] = new int[]{6, 5, 3, 1, 8, 7, 2, 4};
quickSort(unsortedArray);
System.out.println("After sort: ");
for (int item : unsortedArray) {
System.out.print(item + " ");
}
}

public static void quickSort1(int[] array, int l, int u) {
for (int item : array) {
System.out.print(item + " ");
}
System.out.println();

if (l >= u) return;
int m = l;
for (int i = l + 1; i <= u; i++) {
if (array[i] < array[l]) {
m += 1;
int temp = array[m];
array[m] = array[i];
array[i] = temp;
}
}
// swap between array[m] and array[l]
// put pivot in the mid
int temp = array[m];
array[m] = array[l];
array[l] = temp;

quickSort1(array, l, m - 1);
quickSort1(array, m + 1, u);
}

public static void quickSort(int[] array) {
quickSort1(array, 0, array.length - 1);
}
}


[6, 5, 3, 1, 8, 7, 2, 4]
[4, 5, 3, 1, 2, 6, 8, 7]
[2, 3, 1, 4, 5, 6, 8, 7]
[1, 2, 3, 4, 5, 6, 8, 7]
[1, 2, 3, 4, 5, 6, 8, 7]
[1, 2, 3, 4, 5, 6, 8, 7]
[1, 2, 3, 4, 5, 6, 8, 7]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]


### Two-way partitioning

1. 选中3作为基准
2. lo指针指向元素6, hi指针指向4, 移动lo直至其指向的元素大于等于3, 移动hi直至其指向的元素小于3。找到后交换lohi指向的元素——交换元素62
3. lo递增，hi递减，重复步骤2，此时lo指向元素为5, hi指向元素为1. 交换元素。
4. lo递增，hi递减，发现其指向元素相同，此轮划分结束。递归排序元素3左右两边的元素。

1. 下标 $i$$j$ 初始化为待排序数组的两端。
2. 基准元素设置为数组的第一个元素。
3. 执行 partition 操作，大循环内包含两个内循环：
• 左侧内循环自增 $i$, 直到遇到不小于基准元素的值为止。
• 右侧内循环自减 $j$, 直到遇到小于基准元素的值为止。
4. 大循环测试两个下标是否相等或交叉，交换其值。

### Python

#!/usr/bin/env python

def qsort3(alist, lower, upper):
print(alist)
if lower >= upper:
return

pivot = alist[lower]
left, right = lower + 1, upper
while left <= right:
while left <= right and alist[left] < pivot:
left += 1
while left <= right and alist[right] >= pivot:
right -= 1
if left > right:
break
# swap while left <= right
alist[left], alist[right] = alist[right], alist[left]
# swap the smaller with pivot
alist[lower], alist[right] = alist[right], alist[lower]

qsort3(alist, lower, right - 1)
qsort3(alist, right + 1, upper)

unsortedArray = [6, 5, 3, 1, 8, 7, 2, 4]
print(qsort3(unsortedArray, 0, len(unsortedArray) - 1))


### Java

public class Sort {
public static void main(String[] args) {
int unsortedArray[] = new int[]{6, 5, 3, 1, 8, 7, 2, 4};
quickSort(unsortedArray);
System.out.println("After sort: ");
for (int item : unsortedArray) {
System.out.print(item + " ");
}
}

public static void quickSort2(int[] array, int l, int u) {
for (int item : array) {
System.out.print(item + " ");
}
System.out.println();

if (l >= u) return;
int pivot = array[l];
int left = l + 1;
int right = u;
while (left <= right) {
while (left <= right && array[left] < pivot) {
left++;
}
while (left <= right && array[right] >= pivot) {
right--;
}
if (left > right) break;
// swap array[left] with array[right] while left <= right
int temp = array[left];
array[left] = array[right];
array[right] = temp;
}
/* swap the smaller with pivot */
int temp = array[right];
array[right] = array[l];
array[l] = temp;

quickSort2(array, l, right - 1);
quickSort2(array, right + 1, u);
}

public static void quickSort(int[] array) {
quickSort2(array, 0, array.length - 1);
}
}


[6, 5, 3, 1, 8, 7, 2, 4]
[2, 5, 3, 1, 4, 6, 7, 8]
[1, 2, 3, 5, 4, 6, 7, 8]
[1, 2, 3, 5, 4, 6, 7, 8]
[1, 2, 3, 5, 4, 6, 7, 8]
[1, 2, 3, 5, 4, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]


1. 归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序。递归调用发生在处理整个数组之前。
2. 快速排序将一个数组分成两个子数组并对这两个子数组独立地排序，两个子数组有序时整个数组也就有序了。递归调用发生在处理整个数组之后。

Robert Sedgewick 在其网站上对 Quicksort 做了较为完整的介绍，建议去围观下。