首页 / 操作系统 / Linux / 排序算法（1） 快速排序 C++实现

快速排序基本特性

1. 时间复杂度：O（n*lgn）
2. 最坏：O（n^2）
3. 空间复杂度：最好情况下：O（lgn），最坏情况：O（n），平均情况：O（lgn）
4. 不稳定。

关于快速排序的空间复杂度，谢谢@命运他爹 同学指正。详述一下。快速排序由于每次递归的时候会占用一个空间返回中间数位置，所以一次递归的空间复杂度为O（1）。最好情况和平均情况下的递归深度为O（lgn），相应的空间复杂度就是O（lgn）最坏情况下的递归深度为O（n），空间复杂度为O（n）。

算法

123456789101112131415

QUICKSORT（A, p, r）    if p < r       then q ← PARTITION（A, p, r） //关键            QUICKSORT（A, p, q - 1）            QUICKSORT（A, q + 1, r） 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

示例

 待排序数组：7  3  5  9  8  5  1  10  4  6  一趟排序过程分析：  

---

源码

类声明

1234567891011121314151617181920

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;};

 相关成员函数实现

12345678910111213141516171819202122232425262728293031323334

void QuickSort::sort（） {    quicksort（Array, 0, len-1）;}void QuickSort::quicksort（int Array[], int start, int end） {    if （ start < end ） {        int mid = this->partition（Array, start, end）;        if （ start < mid - 1 ）            quicksort（Array, start, mid-1 ）;        if （ mid + 1 < end ）            quicksort（Array, mid+1, end）;    }}int QuickSort::partition（int Array[], int start, int end） {    int i, j, x, tmp;    x = Array[end];    i = start -1;        for （ j = start; j < end; j++ ） {        if （ Array[j] <= x） {            i++;            tmp = Array[j];            Array[j] = Array[i];            Array[i] = tmp;        }    }        tmp = Array[end];    Array[end] = Array[i+1];    Array[i+1] = tmp;    if （DEBUG） {        printArray（Array, len, "MidResult"）;    }    return i+1;}

测试：

123456

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"）;

 运行截图：------------------------------分割线------------------------------C++ Primer Plus 第6版 中文版 清晰有书签PDF+源代码 http://www.linuxidc.com/Linux/2014-05/101227.htm读C++ Primer 之构造函数陷阱 http://www.linuxidc.com/Linux/2011-08/40176.htm读C++ Primer 之智能指针 http://www.linuxidc.com/Linux/2011-08/40177.htm读C++ Primer 之句柄类 http://www.linuxidc.com/Linux/2011-08/40175.htm将C语言梳理一下，分布在以下10个章节中：

1. Linux-C成长之路（一）：Linux下C编程概要 http://www.linuxidc.com/Linux/2014-05/101242.htm
2. Linux-C成长之路（二）：基本数据类型 http://www.linuxidc.com/Linux/2014-05/101242p2.htm
3. Linux-C成长之路（三）：基本IO函数操作 http://www.linuxidc.com/Linux/2014-05/101242p3.htm
4. Linux-C成长之路（四）：运算符 http://www.linuxidc.com/Linux/2014-05/101242p4.htm
5. Linux-C成长之路（五）：控制流 http://www.linuxidc.com/Linux/2014-05/101242p5.htm
6. Linux-C成长之路（六）：函数要义 http://www.linuxidc.com/Linux/2014-05/101242p6.htm
7. Linux-C成长之路（七）：数组与指针 http://www.linuxidc.com/Linux/2014-05/101242p7.htm
8. Linux-C成长之路（八）：存储类，动态内存 http://www.linuxidc.com/Linux/2014-05/101242p8.htm
9. Linux-C成长之路（九）：复合数据类型 http://www.linuxidc.com/Linux/2014-05/101242p9.htm
10. Linux-C成长之路（十）：其他高级议题

本文永久更新链接地址：http://www.linuxidc.com/Linux/2015-02/113518.htm