C/C++实现快速排序的两种典型代码

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
第一种典型实现：通过两个游标来遍历整个待排序数组，i指向数组的第一个元素，j指向数组的最后一个元素。先取出数组中的一个数arr[i]，将其保存在key中，此时arr[i]空出来了，这时游标j往前移，就可找到大于等于key的数，将其放到arr[i]中；然后游标i往后移，找到小于等于key的数，将其保存到arr[j]中；重复j往前移和i往后移的过程，直到i<j不满足，此时i等于j，将key放到下标i处就完成了这轮排序。下标i之前的元素都小于arr[i]，下标i之后的元素都大于arr[i]。最后用同样的方式对分出来的左边的小组和右边的小组进行同上的做法就能使整个数组排序。

void sort(int *a, int left, int right)
{
    if(left >= right) /*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
    {
        return ;
    }
    int i = left;
    int j = right;
    int key = a[left];

    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回归*/
    sort(a, left, i - 1); /*最后用同样的方式对分出来的左边的小组进行同上的做法*/
    sort(a, i + 1, right);/*用同样的方式对分出来的右边的小组进行同上的做法*/
                          /*当然最后可能会出现很多分左右，直到每一组的i = j 为止*/
}

第二种实现：在数组中随便取一个数作为分开数组的标志，下面代码将data[end]作为比较对象。通过游标index遍历整个数组，找到比data[end]小的元素，先将small自增1，然后将下标index和small位置上的交换，即保存在small位置上。遍历结束，下标small之前的数都比data[small]小，之后的数都大于等于data[small]。

void swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}
int Partition(int data[], int length, int start, int end)
{
    if (data == nullptr || length <= 0 || start < 0 || end >= length)
        throw new std::exception("Invalid Parameters");

    int small = start - 1;
    for (int index = start; index < end; index++)
    {
        if (data[index] < data[end])
        {
            small++;/*small初始值是数组首元素位置的前一个位置，当找到比data[end]小的元素，先将small自增1，然后将下标index和small位置上的交换，即保存在small位置上。*/
            if (small != index)
                swap(data[index], data[small]);
        }
    }
    /*下标small之前的数都比data[small]小，之后的数都大于等于data[small]*/
    small++; 
    swap(data[small], data[end]);
    return small;
}
void Quicksort(int data[], int length, int start, int end)
{
    if(start == end)
        return;

    int index = Partition(data, length, start, end);
    if(index > start)
        Quicksort(data, length, start, index-1);
    if(index < end)
        Quicksort(data, length, index+1, end);
}