快速排序的平均情况下是O(nlogn)，但是一般都比其他运行时间为O(nlogn)的算法都要快，因为它隐藏的常数因子比较小，但是在最坏情况之下，快速排序的运行时间是O(n
2)。
性能分析
最好情况
每次基准的最终位置都是在数组中间位置，从而使规模为N的问题分为2个规模为N/2的问题，即T(n) = 2T(n/2) + Θ(n)，用递归树分析或者主定理得到时间T(n) = O(nlogn)。
最坏情况
每次基准的最终位置都是第一个位置，从而规模为N的问题分为一个规模为N-1的问题，即T(n) = T(n-1) + Θ(n),用递归树分析可得运行时间T(n) = O(n2)。
平均情况
假设规模为N的问题分为一个规模为9/10N的问题和规模为1/10N的问题，即T(n) = T(9n/10) + T(n/10) + Θ(n),用递归树分析可得T(n) = O(nlogn)，而且比分区9:1要更平均（也就是情况更好）的概率为80%，所以在绝大部分情况下快速排序算法的运行时间为O(nlogn)。
1
/**//*
2
名称：快速排序
3 最坏时间复杂度：O(n * n)
4 最好时间复杂度：O(n * lg(n))
5
*/
6
#include <iostream>
7#include <time.h>
8#include <stdlib.h>
9using namespace std;
10void quickSort(int*, int);
11void __quickSort(int*, int, int);
12int partition(int*, int, int);
13int main(void)
14
{
15 int n;
16 int *array;
17
srand(time(NULL)); /**//*void srand(unsigned seed)；*/
18 while (true)
19 {
20 cin >> n;
21 array = new int[n];
22 /**//*随机生成数组*/
23 for (int i = 0; i < n; ++i)
24 {
25 array[i] = rand() % 100; /**//*int rand(void)；*/
26
}
27
28 /**//*排序前*/
29 for (int i = 0; i < n; ++i)
30 {
31 cout << array[i] << ' ';
32 }
33 cout << endl;
34
35 /**//*快速排序*/
36 quickSort(array, n);
37
38 /**//*排序后*/
39 for (int i = 0; i < n; ++i)
40 {
41 cout << array[i] << ' ';
42 }
43 cout << endl;
44
45 delete array;
46 }
47 return 0;
48}
49void quickSort(int* array, int length)
50{
51 __quickSort(array, 0, length - 1);
52}
53void __quickSort(int* array, int l, int r)
54{
55 if (l < r)
56 {
57 int pivot = partition(array, l, r);
58 __quickSort(array, l, pivot - 1);
59 __quickSort(array, pivot + 1, r);
60 }
61}
62int partition(int* array, int l, int r)
63{
64 int pivot = array[r];
65 int i = l - 1;
66 int j;
67 for (j = l; j < r; ++j)
68 {
69 if (array[j] <= pivot)
70 {
71 ++i;
72 int temp = array[i];
73 array[i] = array[j];
74 array[j] = temp;
75 }
76 }
77 int temp = array[i + 1];
78 array[i + 1] = array[r];
79 array[r] = temp;
80 return i + 1;
81}
82
posted on 2012-10-22 23:47
zhuxin 阅读(126)
评论(0) 编辑 收藏 引用 所属分类:
排序算法