数据结构与算法——排序算法—（3）快速排序-蒲公英云

数据结构与算法——排序算法—（3）快速排序

1.3 快速排序
快速排序（Quick Sort）的基本思想是选择一个基数，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的数据都比另一部分的所有数据要小。然后，在按此方法对这两部分的数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序流畅：
（1）从数列中挑出一个基准值。
（2）将所有比基准值小的摆放在前面，所有比基准值大的放在后面（相同的数可以任意一边）；在这个分区退出之后，该基准值就处于数列的中间位置。
（3）递归地把基准值前面和后面的子序列进行排序

//快速
void quickSort(int* array, int low, int high)
{
    if (low >= high)
    {
        return;
    }
    int first = low;
    int last = high;
    int key = array[first];
    while (first < last)//>=退出循环
    {
//从右往左，比基准值大的继续执行while,找到比基准值小的跳出while
        while (first < last && array[last] >= key)
        {
            --last;
        }
        //将第一个比基准值小的数，放在first的位置。（不是最左边）
        array[first] = array[last];
//从左往右，比基准值小的继续执行while，找到比基准值大的跳出while
        while (first < last && array[first] <= key)
        {
            ++first;
        }
        //将第一个比基准值大的数，放在last的位置。（不是最右边）
        array[last] = array[first];
    }
    array[first] = key ;//将基准值还原到相应位置
    quickSort(array,low,first-1);//基准值位置之前 -1
    quickSort(array, first+1, high);//基准值位置之后 +1
}

快速排序的时间复杂度和稳定性

快速排序时间复杂度：快速排序的时间复杂度在最坏情况下是O(N2)，平均的时间复杂度是O(N*lgN)。
这句话很好理解：假设被排序的数列中有N个数。遍历一次的时间复杂度是O(N)，需要遍历多少次呢？至少lg(N+1)次，最多N次。
(01) 为什么最少是lg(N+1)次？快速排序是采用的分治法进行遍历的，我们将它看作一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的定义，它的深度至少是lg(N+1)。因此，快速排序的遍历次数最少是lg(N+1)次。
(02) 为什么最多是N次？这个应该非常简单，还是将快速排序看作一棵二叉树，它的深度最大是N。因此，快读排序的遍历次数最多是N次。

快速排序稳定性：不稳定

快速排序目前被认为是同数量级O(nlgn)中最快的内部排序方法