本文目的

上一章节已经详细的向大家介绍过排序的相关概念学习笔记-排序简单介绍，本文旨在为大家详细的介绍快速排序。

快速排序

快速排序（Quicksort）是对冒泡排序（学习笔记-详解冒泡排序）的一种改进，也是一种交换类排序。

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以进行，以此达到整个数据变成有序。

算法原理

本质是分而治之思想的运用。首先选取一个元素作为分界值，将大于该分界值的元素放在数组的右边，小于主元的元素放在数组的左边，等于分界值的元素位置不变，然后不断迭代上述规则完成排序。

快速排序算法的原理如下：

1，首先设定一个分界值，通过该分界值将数组分成左右两部分。

2，将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。

3，然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

4，重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

算法实现

#include <stdio.h> #define elemType int /*元素类型*/int k=1;//轮次记录 void Print (elemType *arr, int len){		int i;		for (i=0; i<len; i++){		printf ("%d\t", arr[i]);	}            printf("\n");}void Sort(elemType *a, int left, int right){    if(left >= right)	/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/    {        return ;    }    int i = left;    int j = right;    int key = a[left];        printf("第%d轮选取的key值为：%d\n",k,key);         while(i < j)                               	/*控制在当组内寻找一遍*/    {        while(i < j && key <= a[j])        /*而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升        序还是降序）2，没有符合条件1的，并且i与j的大小没有反转*/         {            j--;/*向前寻找*/        }                 a[i] = a[j];        /*找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是        a[left]，那么就是给key）*/                 while(i < j && key >= a[i])        /*这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，        因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反*/        {            i++;        }                 a[j] = a[i];    }        a[i] = key;	/*当在当组内找完一遍以后就把中间数key回归*/    printf("第%d轮排序后结果如下：\n",k);    Print(a, 9);      k=k+1;             Sort(a, left, i - 1);	/*最后用同样的方式对分出来的左边的小组进行同上的做法*/    Sort(a, i + 1, right);	/*用同样的方式对分出来的右边的小组进行同上的做法*/    /*当然最后可能会出现很多分左右，直到每一组的i = j 为止*/} int main() {		int i;    elemType arr[9] = {94,19,29,9,11,1,14,13,29};    printf("待排序的序列为：\n");    Print(arr, 9);      printf("\n\n");        Sort (&arr,0,8);    printf("\n\n");    printf("排好序的结果如下：\n");    Print(arr, 9);       }

序列红框为界

算法分析

时间复杂度

快速排序的一次划分算法从两头交替搜索，直到left和right重合，因此其时间复杂度是O(n)；而整个快速排序算法的时间复杂度与划分的趟数有关。

最优情况:每次划分所选择的中间数恰好将当前序列几乎等分，经过log2n趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为O(nlog2n)。

最坏情况:每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度-1。这样，长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为O(n2)。

为改善最坏情况下的时间性能，可采用其他方法选取中间数。通常采用“三者值取中”方法，即比较H->r[left].key、H->r[right].key与H->r[(left + right)/2].key，取三者中关键字为中值的元素为中间数。

可以证明，快速排序的平均时间复杂度也是O(nlog2n)。因此，该排序方法被认为是目前最好的一种内部排序方法。

空间复杂度

从空间性能上看，尽管快速排序只需要一个元素的辅助空间，但快速排序需要一个栈空间来实现递归。最好的情况下，即快速排序的每一趟排序都将元素序列均匀地分割成长度相近的两个子表，所需栈的最大深度为log2(n+1)；但最坏的情况下，栈的最大深度为n。这样，快速排序的空间复杂度为O(log2n))。适合在数据集比较大的时候使用。

算法稳定性

值得注意的是，快速排序是一种不稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。

本文的初衷为学习笔记的分享，部分图文来源于网络，如侵，联删。