快速排序递归算法（利用C++ 函数模板实现）

    最近学习算法，终于弄明白了快速排序的原理，并敲了代码验证，稍微总结一下以便复习。
概述：
    快速排序(Quick Sort)是一种有效的排序算法。虽然算法在最坏的情况下运行时间为O(n^2)，但由于平均运行时间为O(nlogn)，并且在内存使用、程序实现复杂性上表现优秀，尤其是对进行随机化的可能，使得快速排序在一般情况下是最实用的排序方法之一。
　快速排序被认为是当前最优秀的内部排序方法。

：
      快速排序每次将待排序数组分为两个部分，在理想状况下，每一次都将待排序数组划分成等长两个部分，则需要logn次划分。
　　而在最坏情况下，即数组已经有序或大致有序的情况下，每次划分只能减少一个元素，快速排序将不幸退化为，所以快速排序时间复杂度下界为O(nlogn)，最坏情况为O(n^2)。在实际应用中，快速排序的平均时间复杂度为O(nlogn)。
　　快速排序在对序列的操作过程中只需花费常数级的空间。S(1)。
　　但需要注意递归栈上需要花费最少logn 最多n的空间。

c++ code :

/* quikSork.cpp    快排递归算法*/
/*  快排算法描述如下：
 * 快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

步骤为：

    1） 从数列中挑出一个元素，称为 "基准"（pivot），
    2） 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面
       （相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
    3） 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
        合并：由于两个子序列是就地排序的，所以对它们的合并不需要操作，整个序列L[m .. n]已排好序。
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
using namespace std;

template <class T>
void Swap(T &x, T &y)
{
    T tmp;

    tmp = x;
    x = y;
    y = tmp;
}
// 进行一趟快排,并返回分界的基准
template <class Type>
int partition(Type array[], int left, int right)
{
    Type x = array[left]; // 找基准点，之后array[left]相当空单元
/*
    while (left < right) {
        // right --> left 扫描 find smaller than x
        while (right > left && array[right] >= x) {
            right--;
        }
        if (left < right) {
            array[left] = array[right]; // 将<= x的存入空单元
            left++;
        }
        // left --> right 扫描 find bigger than x
        while (left < right && array[left] < x) {
            left++;
        }
        if (left < right) {
            array[right] = array[left]; // 将>= x的存入空单元
            right--;
        }
    }
    array[left] = x; //insert
    return left;
*/

 /*       或者使用下面的改进代码,原理和上面一样，只不过代码少点  */
    int p_left = left;
    int p_right  = right + 1;

    // 找分界点，
    for( ; ;) {
        while(array[++p_left] < x && p_left < right)
            ; //left-->right find one bigger than x
        while(array[--p_right] > x)  //array[p_right] >= x = array[left]相当一道栏杆
            ; //right-->left find one smaller than x
        if(p_left >= p_right)
            break;
        Swap(array[p_left], array[p_right]);//交换后左边小，右边大
    } // end for

    // 找到的数 array[p_right] 一定 <= x，found one middle position for x
    array[left] = array[p_right];
    array[p_right] = x; // insert to middle position

    return p_right; //返回分界下标
}

template <class Type>
void quikSort(Type array[], int pos_start, int pos_end)// pos_start,pos_end为下标
{
    if (pos_start < pos_end) {
        int partition_pos;
        partition_pos = partition(array, pos_start, pos_end);//一趟快排，获得基准点

        quikSort(array, pos_start, partition_pos-1);  //递归分解，对左边进行快排
        quikSort(array, partition_pos+1, pos_end); //递归分解，对右边进行快排
    }
}


template <class T>
void print_array(T a[], int n)
{
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
}

/* ------------------------------------------------------------------------ */
/* 我们容易发现，快排算法的性能取决于划分的对称性。通过修改partition函数可以设计出采用
 * 随机选择策略的快排算法。也就是说找基准时从array[left,right]中随机找一个作为划分的基准
 * 而不是只以第一个[left]作为基准。
 */
 （关于随机数请阅读我的另一博文：http://blog.chinaunix.net/uid-27034868-id-3368530.html）
 //随机生成某范围的随机整数,调用前用srand设置种子
int range_random(int start, int end)
{
    return    ( start + rand() % (end - start + 1) );
}

template < class T >
int Random_part(T array[], int left, int right)
{
    int rd = range_random(left, right);// 从left到right中取随机下标
    Swap(array[rd], array[left]);

    return partition(array, left, right);
}

template <class Type>
void random_quikSort(Type array[], int pos_start, int pos_end)// pos_start,pos_end为下标
{
    if (pos_start < pos_end) {
        int partition_pos;
        partition_pos = Random_part(array, pos_start, pos_end);//一趟快排，获得基准点

        random_quikSort(array, pos_start, partition_pos-1);  //递归分解，对左边进行快排
        random_quikSort(array, partition_pos+1, pos_end); //递归分解，对右边进行快排
    }
}

/* ------------------------------------------------------------------------- */

int main(void)
{
    int a[] = {7, 2, 5, 6, 0, 10, 4};

    quikSort(a, 0, sizeof(a)/sizeof(a[0])-1);
    print_array(a, sizeof(a)/sizeof(a[0]));

    int b[] = {1, 2, -2, 0, 7, 18, 4, 3, 4, 8};

    srand((unsigned)time(NULL));
    random_quikSort(b, 0, sizeof(b)/sizeof(b[0])-1);
    print_array(b, sizeof(b)/sizeof(b[0]));

    return 0;
}

  注：本博客的文章除注明有“转载”字样的外，均为原创，欢迎转载，请注明文字出处，谢谢！