转载

快速排序

快速排序

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列,快速排序的时间复杂度为O(n*log(n)),最坏的情况是O(n^2),快速排序是不稳定的

复杂度的证明

最优情况

在最优情况下,Partition每次都划分得很均匀,如果排序n个关键字,其递归树的深度就为 [log2n]+1( [x] 表示不大于 x 的最大整数),即仅需递归 log2n 次,需要时间为T(n)的话,第一次Partiation应该是需要对整个数组扫描一遍,做n次比较。然后,获得的枢轴将数组一分为二,那么各自还需要T(n/2)的时间(注意是最好情况,所以平分两半)。于是不断地划分下去,就有了下面的不等式推断:

图片

最坏情况

当待排序的序列为正序或逆序排列时,且每次划分只得到一个比上一次划分少一个记录的子序列,注意另一个为空。如果递归树画出来,它就是一棵斜树。此时需要执行n‐1次递归调用,且第i次划分需要经过n‐i次关键字的比较才能找到第i个记录,也就是枢轴的位置,因此比较次数为 ,最终其时间复杂度为O(n^2)。

图片

c++代码

#include<iostream>
using namespace std;

int quickSort(int *a, int start, int end) {
	if(start >= end) return 0;
	
	int temp = 0;
	int key = a[start];
	int low = start, high = end;
	
	while(low < high) {
		while(low < high && a[high] >= key) high--;
		while(low < high && a[low] <= key) low++;
		
		if(low != high) {
			temp = a[low];
			a[low] = a[high];
			a[high] = temp;
		}
	}
	
	a[start] = a[high];
	a[high] = key;
	quickSort(a, start,  high - 1);
	quickSort(a, high + 1, end);
	return 0;
}
int main() {
	int a[10] = {1, 3, 2, 5, 8, 5, 4, 4, 0, 3};
	
	quickSort(a, 0, 9);
	
	for(int i = 0; i < 10; i++) printf("%d ", a[i]);
} 

另一种partition的方法

这种方法更容易理解。简单的把小于基准值的元素全部交换到数组的左边

python代码

#快速排序,另一种partition的实现

def exchange(arr, a, b):
    value = arr[a]
    arr[a] = arr[b]
    arr[b] = value

def quickSort(arr, start, end):
    if start >= end:
        return

    #基准坐标为start
    key = arr[start]
    position = start

    for i in range(start+1, end+1):
        #如果值比key小,则交换数组中位置i和位置position+1的两个元素的值
        #并把position加1
        if arr[i] < key:
            exchange(arr, i, position+1)
            position += 1

    exchange(arr, start, position)

    quickSort(arr, start, position-1)
    quickSort(arr, position+1, end)



arr = [2, 3, 9, 4, 2, 4, 4, 7, 3]

quickSort(arr, 0, 8)

print (arr)
正文到此结束
本文目录