快速排序基本特性
时间复杂度:O(n*lgn)
最坏:O(n^2)
空间复杂度:最好情况下:O(lgn),最坏情况:O(n),平均情况:O(lgn)
不稳定。
关于快速排序的空间复杂度,谢谢@命运他爹 同学指正。详述一下。
快速排序由于每次递归的时候会占用一个空间返回中间数位置,所以一次递归的空间复杂度为O(1)。
最好情况和最坏情况下的递归深度为O(lgn),相应的空间复杂度就是O(lgn)
最坏情况下的递归深度为O(n),空间复杂度为O(n)。
算法
QUICKSORT(A, p, r)
if p A[j]
exchange A[i + 1] A[r]
return i + 1
示例
待排序数组:7 3 5 9 8 5 1 10 4 6
一趟排序过程分析:
源码
类声明
class BaseSort {
public:
BaseSort() { }
virtual void sort() = 0;
};
class QuickSort : public BaseSort {
public:
QuickSort(int Array[], int len) : BaseSort() {
this->Array = Array;
this->len = len;
}
void sort();
private:
int partition(int Array[], int start, int end);
void quicksort(int Array[], int start, int end);
private:
int* Array;
int len;
};
相关成员函数实现
void QuickSort::sort() {
quicksort(Array, 0, len-1);
}
void QuickSort::quicksort(int Array[], int start, int end) {
if ( start partition(Array, start, end);
if ( start
测试:
int a[10] = {7,3,2,9,8,5,1,10,4,6};
int len = 10;
QuickSort* quicksort= new QuickSort(a, len);
quicksort->sort();
printArray(a, len, "QuickSort");
运行截图:
更多精彩内容:http://www.bianceng.cn/Programming/cplus/