算法-排序-快速

算法-排序

4 快速排序

特点

  • 不稳定
  • 平均性能高

简介

快速排序,顾名思义,很快.

STL库中的sort()函数用的就是快速排序.

演示

原始数据(8个)
X 4 8 3 2 5 1 6
基准值 X = 7

第一次处理
6 4 8 3 2 5 1 X
i j

第二次处理
6 4 X 3 2 5 1 8
i j

第三次处理
6 4 1 3 2 5 X 8
i j

第四次处理
6 4 1 3 2 5 X 8
ij

放回原位

6 4 1 3 2 5 7 8

演示解析

经过处理,数据变成了两部分。在a[i]左侧的是比它小的数字,右侧的是比它大的数字.
我们再将左侧进行处理,右侧进行处理,以此递归,直到左侧下标大于右侧下标,最终数据将变得有序.

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int Part(int array[], int start, int end)
{
int X = array[start];
while(start < end)
{
while(array[end] > X && start < end) //越界检查
{
end--; //找到右侧第一个比参考值小的
}
if(start < end) //越界检查
{
array[start] = array[end]; //交换
start++;
}
while(array[start] < X && start < end) //越界检查
{
start++; //找到左侧第一个比参考值大的
}
if(start < end) //越界检查
{
array[end] = array[start]; //交换
end--;
}
}
//循环结束:start == end
array[start] = X;
return start;
}

void Sort(int array[], int start, int end)
{
if(start >= end) //越界检查
return;
int part = Part(array, start, end);
//分治
Sort(array, start, part - 1); //左半边
Sort(array, part + 1, end); //右半边
}

END

快速排序是一种性能较高的排序. 递归可能有点难以理解,最好自己拿数据试一试.
接下来还有快速、堆、桶排序等.