基本思想
快速排序（Quicksort）是对冒泡排序的一种改进，又称划分交换排序（partition-exchange sort。
快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。
步骤为：
①．从数列中挑出一个元素，称为”基准”（pivot）
②．重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
③．递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序
这里写图片描述
使用快速排序法对一列数字进行排序的过程
排序效率
在平均状况下，排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n)算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
最差时间复杂度 Ο(n^2)
最优时间复杂度 Ο(n log n)
平均时间复杂度Ο(n log n)
最差空间复杂度 根据实现的方式不同而不同
Java实现
public static void main(String[] args) {
int [] arr = {8,1,0,4,6,2,7,9,5,3};
quickSort(arr,0,arr.length-1);
for(int i :arr){
System.out.println(i);
}
}
public static void quickSort(int[]arr,int low,int high){
if (low < high) {
int middle = getMiddle(arr, low, high);
quickSort(arr, low, middle - 1);
quickSort(arr, middle + 1, high);
}
}
public static int getMiddle(int[] list, int low, int high) {
int tmp = list[low];
while (low < high) {
while (low < high && list[high] >= tmp) {
high--;
}
list[low] = list[high];
while (low < high && list[low] <= tmp) {
low++;
}
list[high] = list[low];
}
list[low] = tmp;
return low;
}
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
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
运行结果：
这里写图片描述
分析：
这里写图片描述
取８为中值，红色箭头表示low，绿色箭头表示high
①从high开始向前扫描到第一个比８小的值与８交换。
②从low向后扫描第一比8大的值与8交换。
③重复①②过程只到，high=low完成一次快速排序，然后递归子序列。 |
|
收藏
淘帖
踩
