再谈快速排序

本篇博客是在快速排序基础上优化的。

算法思想

快速排序是基于分治模式构思的，具体描述如下：

分解：数组A[p..r]被划分成两个（可能空）子数组A[p..q-1]和A[q+1..r]，使得A[p..q-1]中的每个元素都小于等于A(q)，而且，小于等于A[q+1..r]中的元素。下标q也在这个划分过程中进行计算。解决：通过递归调用快速排序，对子数组A[p..q-1]和A[q+1..r]排序。合并：因为两个子数组是就地排序的，将它们合并不需要操作：整个数组A[p..r]已排序。 // QUICKSORT QUICKSORT(A, p, r) if p < r then q = PARTITION(A, p, r) QUICKSORT(A, p, q-1) QUICKSORT(A, q+1, r) // PARTITION PARTITION(A, p, r) x = A[r] i = p-1 for j = p to r-1 do if A[j] <= x then i = i+1 exchange(A[i], A[j]) exchange(A[i+1], A[r]) return i+1

算法解析

具体执行步骤如下：

i=p-1, j=p, x=A[r]因为A[i]<=x，i=p，A[i]和A[j]交换A[j]=7>x，j递增当A[j]=1时，因为A[i]<=x，i=p+1，A[i]和A[j]交换当A[j]=3时，因为A[i]<=x，i=p+2，A[i]和A[j]交换A[j]=5>x，j递增A[j]=6>x，j递增j=r，A[r]和A[i+1]交换

源程序

#include <stdio.h> #include <unistd.h> #include <stdlib.h> #include <time.h> #include <sys/time.h> void swap(int &x, int &y); int partition(int *array, int left, int right); void qsort(int *array, int left, int right); void print(int *array, int left, int right); void print(int *array, int n); void input(int *&array, int n); const int number = 8; int main(int argc, char *argv[]) { //int array[] = {13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11}; int array[] = {2, 8, 7, 1, 3, 5, 6, 4}; //int *array = new int[number]; int n = number; //input(array, number); printf("befor qsort\n"); print(array, n); printf("\n"); struct timeval stv; gettimeofday(&stv, NULL); int st_usec = stv.tv_sec * 1000000 + stv.tv_usec; qsort(array, 0, n - 1); struct timeval end_tv; gettimeofday(&end_tv, NULL); int end_usec = end_tv.tv_sec * 1000000 + end_tv.tv_usec; int cost = end_usec - st_usec; printf("qsort cost time : %dus\n", cost); printf("after qsort\n"); print(array, n); //delete []array; exit(0); } void qsort(int *array, int left, int right) { if (left < right) { //print(array, 0, number - 1); int pos = partition(array, left, right); qsort(array, left, pos - 1); qsort(array, pos + 1, right); } } int partition(int *array, int left, int right) { printf("before partition\n"); print(array, 0, number - 1); int i = left - 1; int x = array[right]; for (int j = left; j < right; j++) { printf("in partition : "); if (array[j] <= x) { ++i; swap(array[i], array[j]); } //print(array, 0, number - 1); print(array, left, right); //printf("in partition\n"); } swap(array[i + 1], array[right]); printf("after partition\n"); print(array, 0, number - 1); printf("\n"); return i + 1; } void swap(int &x, int &y) { int temp = x; x = y; y = temp; } void print(int *array, int left, int right) { for (int i = left; i <= right; i++) { printf("%d ", array[i]); } printf("\n"); } void print(int *array, int n) { print(array, 0, n - 1); } void input(int *&array, int n) { for (int i = 0; i < n; i++) { array[i] = rand() % n; } }

算法执行过程

befor qsort 2 8 7 1 3 5 6 4 before partition 2 8 7 1 3 5 6 4 in partition : 2 8 7 1 3 5 6 4 in partition : 2 8 7 1 3 5 6 4 in partition : 2 8 7 1 3 5 6 4 in partition : 2 1 7 8 3 5 6 4 in partition : 2 1 3 8 7 5 6 4 in partition : 2 1 3 8 7 5 6 4 in partition : 2 1 3 8 7 5 6 4 after partition 2 1 3 4 7 5 6 8 before partition 2 1 3 4 7 5 6 8 in partition : 2 1 3 in partition : 2 1 3 after partition 2 1 3 4 7 5 6 8 before partition 2 1 3 4 7 5 6 8 in partition : 2 1 after partition 1 2 3 4 7 5 6 8 before partition 1 2 3 4 7 5 6 8 in partition : 7 5 6 8 in partition : 7 5 6 8 in partition : 7 5 6 8 after partition 1 2 3 4 7 5 6 8 before partition 1 2 3 4 7 5 6 8 in partition : 7 5 6 in partition : 5 7 6 after partition 1 2 3 4 5 6 7 8 qsort cost time : 3610us after qsort 1 2 3 4 5 6 7 8

算法复杂度分析

时间复杂度空间复杂度说明最优情况O(nlogn)O(logn)平均情况O(nlogn)O(logn)最坏情况O(n^2)O(n)

算法耗时分析

数量级耗时说明1万1.7ms1百万238ms1千万2.5s2千万5.4s5千万14s1亿无内存空间有限

参考文献

[1] Thomas H.Cormen, Charles E.Leiserson,etc. 算法导论