首页 > 基础算法 > 排序 > 快速排序算法及分析
2014
05-17

快速排序算法及分析

快速排序算法和归并排序类似,都是属于分治算法。

快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。

步骤为:

  1. 从数列中挑出一个元素,称为 “基准”(pivot),
  2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
  3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

虽然快速排序是分治算法,但其中主要的操作是分区操作,这个操作的复杂性应该是线性的。划分的实现由很多种,朴素的实现是选取第一个元素和最后一个元素作为基准作为划分。算法导论一书给出的partition 函数是取最后一个元素作为基准,然后通过一遍循环交换元素。代码虽然简洁,但是初看起来不太易懂,建议在纸上模拟下过程。此种方法相对来说交换元素的次数也比较多,后面会给出一种优化的操作。

C语言实现

/* 快速排序朴素的实现 */
#include<stdio.h>

void swap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

/*取最后一个作为基准 */
int partition (int arr[], int l, int h)
{
    int x = arr[h];   
    int i = (l - 1);  // 较小元素的下标
    for (int j = l; j <= h- 1; j++)
    {
        if (arr[j] <= x)
        {
            i++;    //增加较小元素的下标
            swap(&arr[i], &arr[j]); 
        }
    }
    swap(&arr[i + 1], &arr[h]);  
    return (i + 1);//返回基准元素的最终位置
}

/* arr[] --> 待排序数组, l  --> 开始位置, h  -->结束位置 */
void quickSort(int arr[], int l, int h)
{
    if (l < h)
    {
        int p = partition(arr, l, h); /* p为划分的中间位置 */
        quickSort(arr, l, p - 1);
        quickSort(arr, p + 1, h);
    }
}

/* 打印数组 */
void printArray(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// 测试
int main()
{
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    quickSort(arr, 0, n-1);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

输出:

Sorted array:
1 5 7 8 9 10

有必要说下上面的partition函数 ,如果输入是已排序的,那个每个元素都会和自己交换,效率不好。另一个种划分的操作是用头尾指针。实现如下:

//划分操作的 第二种实现
int partition2(int * arr, int start, int end) {
	int i = start;//指向开头
	int j = end + 1;//指向结尾
	int pivot = arr[start];
	while(true){
		while( i<end && arr[++i] < pivot);//从前到后  第一个比 基准(x)大的数。 j指向该数
		while(j>start && arr[--j] > pivot);//从后向前找到第一个比 基准(x)小的数。i指向该数
		if(i >= j)
			break;
		swap(arr[i], arr[j]);
	}
	arr[start] = arr[j];
	arr[j] = pivot;
	return j;
}

这种划分操作在大部分情况下交换的次数较少。

分析

时间的复杂度可以表示为:T(n) = T(k) + T(n-k-1) + \theta(n)

其中 T(k), T(n-k-1) 对应程序中的递归调用,k是在划分后比基准元素小的元素个数。 \theta(n) 就是partition函数的复杂度。

算法的效率对不同的输入数据会有所不同,可以分为下面3中情况:

1) 最坏的情况。当分区过程总是挑选最大或最小的元素作为支点。如果我们考虑以上的分区策略,其中最后一个元素总是被挑为支点,当数组已经排序的递增或递减顺序时,会发生最坏的情况:

T(n) = T(0) + T(n-1) +\theta(n), 即 T(n) = T(n-1) +\theta(n)

此时的复杂度为 O(n^2)

2) 最好的情况发生在最好的情况下,当分区过程总是挑选最中间元素为支点。

T(n) = 2 T(n/2) +\theta(n)

此时的递归表达式和归并排序是一样的。时间时间复杂度为 O(n lg n). 计算方法参考 递归的时间复杂度

3) 平均情况

要做到平均情况分析,我们需要考虑数组中的所有可能的排列,并计算每一个排列所需要的时间,这种计算是比较麻烦的。

可以这么分析,如果划分的结果是这样的两部分 O(n/10) 和 O(9n/10)。递归式为:  T(n) =  T(n/10) + T(n9/10) +\theta(n)

最终的计算结果也为:O(n lg n). 具体计算参考:麻省理工学院公开课:算法导论 

虽然快速排序的最坏情况下复杂度为O(N^2),这比很多其他的排序算法,如归并排序堆排序,在实践中更快,因为它的内部循环可以在大多数架构有效地实现,

对于大部分真实的数据,也是比较高效的。后续会有快速排序的优化算法

参考:http://geeksquiz.com/quick-sort/