描述
采用分治的思想(Divide and conquer)
分解：把数组划分为两个子数组，找一个基准数x，使左边元素都小于x，右边元素都大于x
解决：通过递归调用快速排序对数组A[a:i]和A[i+1:b]排序，基准数不用排
下面试快速排序的伪代码：
伪代码
原理图：
image.png
python描述
def partition(array, a, b):
if len(array) > 0:
x = array[a]
i = a
for j in range(a+1, b):
if array[j] <= x:
i += 1
array[i], array[j] = array[j], array[i]
array[a], array[i] = array[i], array[a]
print(array)
return i
def quick_sort(array, a, b):
if a < b:
i = partition(array, a, b)
quick_sort(array, a, i)
quick_sort(array, i+1,b)
java描述
public class Quick {
public static void sort(Comparable[] a){
sort(a, 0, a.length-1);
}
private static void sort(Comparable[] a, int start, int end){
if(start > end){
return;
}
int j = partition(a, start, end);
// 将左半部分排序
sort(a, start, j-1);
// 将右半部分排序
sort(a, j+1, end);
}
private static int partition(Comparable[] a, int start, int end){
Comparable flag = a[end];
int i = start;
for(int j = start; j < end; j++){
if(less(a[j], flag)){
exch(a, i, j);
i++;
}
}
exch(a, i, end);
return i;
}
public static void main(String[] args) {
Integer[] a = {2, 3, 1, 3, 4, 8, 6, 10};
sort(a);
assert isSorted(a);
show(a);
}
public static boolean less(Comparable V , Comparable W){
return V.compareTo(W) < 0;
}
public static void exch(Comparable[] a, int i, int j){
Comparable temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void show(Comparable[] a){
for (int i = 0; i < a.length; i++){
System.out.print(a[i] + " ");
}
System.out.println();
}
// 测试数组元素是否有序
public static boolean isSorted(Comparable[] a){
for (int i = 1; i < a.length; i++){
if(less(a[i], a[i-1])){
return false;
}
}
return true;
}
}
算法分析
快速排序的最坏时间复杂度是O(n2)，但是只有在已经排好序的情况下时间复杂度是O(n2)，平均时间复杂度或者说期望运行时间比较可观，为O(nlgn)
随机优化
在选择主元素（基准数）时，可以随机选取，因为主元素时随机选取的，我们期望在
在平均的情况下，对数组的划分是比较均衡的
代码下次补上
