学步园

算法描述：

在当前参加排序的序列array[0..n-1] 中任意选择一个元素(通常称该元素为分界元素或者基准元素), 把小于等于分界元素的所有元素都移到分界元素的前边，把大于等于分界元素的所有元素都移到分界元素的后边，这样，分界元素正好处在排序的最终位置上，并且把当前参加排序的序列分成前后两个子序列，前一个子序列中所有元素都小于等于分界元素，后一个子序列中所有元素都小于等于分解元素。然后分别对这两个子序列中长度大于1的序列递归地进行上述过程，直到使得所有元素都到达整个排序后它们所处的位置。

分界元素可以选取

1. 排序序列的第一个元素

2. 排序序列的最后一个元素

3. 位置居中的元素

这里选择排序序列的第一个元素。

排序过程中需要设定两个排序变量i, j.  

1. i的初始值设置为排序序列中第一个元素之后的一个元素， j的初始值设置为排序序列的最后一个元素位置

2. 当 array[i] <= array[0] && i < n - 1, 一直执行 i += 1；当array[j] >= array[0], 一直执行 j -= 1;

3. 如果 i < j, 交换 array[ i ] 和 array[ j ]，重复步骤2和步骤3或者步骤4

4. 如果 i >= j, 交换 array[ 0 ] 和 array[ j ]，然后分别递归的对序列 array[0..j-1] 和序列 array[j+1 . . n-1]中长度大于1的子序列执行上述过程，直到整个序列排序结束

看代码，只需关注函数 void quickSort(int array[], int left, int right) 和 void quick_sort(int array[], int n);

1. 快速排序的递归算法实现

#include <stdlib.h>
#include <stdio.h>

void print_array(int array[], int n)
{
    int i;
    for( i = 0 ; i < n ; ++i )
    {
        printf("%d ", array[i]);
    }
    printf("\n");
}

void swapElem(int *elem1, int *elem2)
{
    int temp;
    temp = *elem1;
    *elem1 = *elem2;
    *elem2 = temp;
}

void quickSort(int array[], int left, int right)
{
    if( left < right )
    {
        int i = left + 1, j = right;
        int temp;
        while( 1 )
        {
            while( array[i] <= array[left] && i < right )
                ++i;

            while( array[j] >= array[left] && j > left )
                --j;

            if( i < j )
            {
                swapElem(&array[i], &array[j]);
            }
            else
                break;
        }

        swapElem(&array[left], &array[j]);

        quickSort(array, left, j-1);
        quickSort(array, j+1, right);
    }
}

void quick_sort(int array[], int n)
{
    quickSort(array, 0, n - 1);
}

int main()
{
    int array[]= {1, 5, 3, 12, 34, 1, 98, 56, 199};
    int n = sizeof(array) / sizeof(int);
    quick_sort(array, n);
    print_array(array, n);
}

2. 快速排序算法的非递归算法C++实现, 参考点选用的是一个数组元素中的随机数

void swapElem(int &elem1, int &elem2)
{
    int temp;
    temp = elem1;
    elem1 = elem2;
    elem2 = temp;
}

int RandomInRange(int start, int end)
{
    if(end > start)
    {
        srand(time(NULL));
        return start + rand()%(end-start);
    }
    return start;
}

int partition(int array[], int length, int start, int end)
{
    if(array == NULL || length < 1 || start < 0 || end >= length)
        throw new std::exception();

    int index = RandomInRange(start, end);
    swapElem(array[index], array[end]);
    int small = start - 1;
    for(index = start; index < end; ++index)
    {
        if(array[index] < array[end])
        {
            ++small;
            if(small != index)
            {
                swapElem(array[index], array[small]);
            }
        }
    }

    ++small;
    swapElem(array[small], array[end]);

    return small;
}

void quicksort(int array[], int length)
{
    if(array == NULL || length < 1)
        return;

    stack<int> st;
    int start = 0;
    int end = length - 1;
    if(end > start)
    {
        st.push(start);
        st.push(end);

        while(!st.empty()) {
            end = st.top();
            st.pop();
            start = st.top();
            st.pop();
            int index = partition(array, length, start, end);
            if(index - 1 > start) {
                st.push(start);
                st.push(index - 1);
            }

            if(index + 1 < end) {
                st.push(index + 1);
                st.push(end);
            }
        }
    }
}

算法时间复杂度：

1. worst case, 当初始序列已经是升序的序列，则第一次排序经过 n - 1次比较之后，将第1个元素确定在原来的位置上。由于得到的两个子序列中前一个子序列长度 小于 2，于是只得到一个长度为 n - 1 的子序列继续递归执行快速排序，由此可见总的排序次数为 (n - 1) + (n -2) + (n -3) + . . . + 1 = n(n-1) / 2, 时间复杂度是 O(n^2)

2. best case, 每趟快速排序之后，分界元素正好位于排序序列的正中间，于是将排序序列分成大小相等的两个子序列，直到子序列的长度为1

T(n) <= n + 2 T(n/2)

<= n + 2 * n/2 + 4T(n/4) = 2n + 4T(n/4)

. . . . . . 

< = n * log2 n + nT(1)

于是时间复杂度为 n * log2 n