快速排序
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n²)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好，可是这是为什么呢，我也不知道。好在我的强迫症又犯了，查了 N 多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案：
快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
1. 算法步骤
- 1.从数列中挑出一个元素，称为 “基准”（pivot）;
- 2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
2. 动图演示
动图演示
3. JavaScript 代码实现
1
function quickSort(arr, left, right) {
2
var len = arr.length,
3
partitionIndex,
4
left = typeof left != 'number' ? 0 : left,
5
right = typeof right != 'number' ? len - 1 : right;
6
7
if (left < right) {
8
partitionIndex = partition(arr, left, right);
9
quickSort(arr, left, partitionIndex-1);
10
quickSort(arr, partitionIndex+1, right);
11
}
12
return arr;
13
}
14
15
function partition(arr, left ,right) { // 分区操作
16
var pivot = left, // 设定基准值（pivot）
17
index = pivot + 1;
18
for (var i = index; i <= right; i++) {
19
if (arr[i] < arr[pivot]) {
20
swap(arr, i, index);
21
index++;
22
}
23
}
24
swap(arr, pivot, index - 1);
25
return index-1;
26
}
27
28
function swap(arr, i, j) {
29
var temp = arr[i];
30
arr[i] = arr[j];
31
arr[j] = temp;
32
}
33
function partition2(arr, low, high) {
34
let pivot = arr[low];
35
while (low < high) {
36
while (low < high && arr[high] > pivot) {
37
--high;
38
}
39
arr[low] = arr[high];
40
while (low < high && arr[low] <= pivot) {
41
++low;
42
}
43
arr[high] = arr[low];
44
}
45
arr[low] = pivot;
46
return low;
47
}
48
49
function quickSort2(arr, low, high) {
50
if (low < high) {
51
let pivot = partition2(arr, low, high);
52
quickSort2(arr, low, pivot - 1);
53
quickSort2(arr, pivot + 1, high);
54
}
55
return arr;
56
}
Copied!
4. Python 代码实现
1
def quickSort(arr, left=None, right=None):
2
left = 0 if not isinstance(left,(int, float)) else left
3
right = len(arr)-1 if not isinstance(right,(int, float)) else right
4
if left < right:
5
partitionIndex = partition(arr, left, right)
6
quickSort(arr, left, partitionIndex-1)
7
quickSort(arr, partitionIndex+1, right)
8
return arr
9
10
def partition(arr, left, right):
11
pivot = left
12
index = pivot+1
13
i = index
14
while i <= right:
15
if arr[i] < arr[pivot]:
16
swap(arr, i, index)
17
index+=1
18
i+=1
19
swap(arr,pivot,index-1)
20
return index-1
21
22
def swap(arr, i, j):
23
arr[i], arr[j] = arr[j], arr[i]
Copied!
5. Go 代码实现
1
func quickSort(arr []int) []int {
2
return _quickSort(arr, 0, len(arr)-1)
3
}
4
5
func _quickSort(arr []int, left, right int) []int {
6
if left < right {
7
partitionIndex := partition(arr, left, right)
8
_quickSort(arr, left, partitionIndex-1)
9
_quickSort(arr, partitionIndex+1, right)
10
}
11
return arr
12
}
13
14
func partition(arr []int, left, right int) int {
15
pivot := left
16
index := pivot + 1
17
18
for i := index; i <= right; i++ {
19
if arr[i] < arr[pivot] {
20
swap(arr, i, index)
21
index += 1
22
}
23
}
24
swap(arr, pivot, index-1)
25
return index - 1
26
}
27
28
func swap(arr []int, i, j int) {
29
arr[i], arr[j] = arr[j], arr[i]
30
}
Copied!
6. C++版
1
//严蔚敏《数据结构》标准分割函数
2
Paritition1(int A[], int low, int high) {
3
int pivot = A[low];
4
while (low < high) {
5
while (low < high && A[high] >= pivot) {
6
--high;
7
}
8
A[low] = A[high];
9
while (low < high && A[low] <= pivot) {
10
++low;
11
}
12
A[high] = A[low];
13
}
14
A[low] = pivot;
15
return low;
16
}
17
18
void QuickSort(int A[], int low, int high) //快排母函数
19
{
20
if (low < high) {
21
int pivot = Paritition1(A, low, high);
22
QuickSort(A, low, pivot - 1);
23
QuickSort(A, pivot + 1, high);
24
}
25
}
Copied!
7. Java 代码实现
1
public class QuickSort implements IArraySort {
2
3
@Override
4
public int[] sort(int[] sourceArray) throws Exception {
5
// 对 arr 进行拷贝，不改变参数内容
6
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
7
8
return quickSort(arr, 0, arr.length - 1);
9
}
10
11
private int[] quickSort(int[] arr, int left, int right) {
12
if (left < right) {
13
int partitionIndex = partition(arr, left, right);
14
quickSort(arr, left, partitionIndex - 1);
15
quickSort(arr, partitionIndex + 1, right);
16
}
17
return arr;
18
}
19
20
private int partition(int[] arr, int left, int right) {
21
// 设定基准值（pivot）
22
int pivot = left;
23
int index = pivot + 1;
24
for (int i = index; i <= right; i++) {
25
if (arr[i] < arr[pivot]) {
26
swap(arr, i, index);
27
index++;
28
}
29
}
30
swap(arr, pivot, index - 1);
31
return index - 1;
32
}
33
34
private void swap(int[] arr, int i, int j) {
35
int temp = arr[i];
36
arr[i] = arr[j];
37
arr[j] = temp;
38
}
39
40
}
Copied!
8. PHP 代码实现
1
function quickSort($arr)
2
{
3
if (count($arr) <= 1)
4
return $arr;
5
$middle = $arr[0];
6
$leftArray = array();
7
$rightArray = array();
8
9
for ($i = 1; $i < count($arr); $i++) {
10
if ($arr[$i] > $middle)
11
$rightArray[] = $arr[$i];
12
else
13
$leftArray[] = $arr[$i];
14
}
15
$leftArray = quickSort($leftArray);
16
$leftArray[] = $middle;
17
18
$rightArray = quickSort($rightArray);
19
return array_merge($leftArray, $rightArray);
20
}
Copied!
Last modified 2yr ago