快速排序递归与非递归-向日葵屋

快速排序递归与非递归

递归法

#

快排的思想

设当前需要排序的数组为int A[bt…ed]

分解：
在A[]中任选一个记录作为基准（pivot），以pivot为基准将数组A划分为两个小的数组A[bt…pivot-1]和A[pivot+1…ed],并使左边的数组元素均小于等于pivot，右边数组元素均大于等于piovt。此时，pivot处于正确的位置上，它不需要再参加后续的排序

求解：
递归的调用快速排序，对A[bt…pivot-1]和A[pivot+1…ed]进行快速排序

组合：
跟归并排序不同，因为每次调用快速排序，左右两个数组均已有序，因此对于快速排序来说，组合是一个空操作

实现代码（C语言）

快排用c实现其实可以直接调用系统的qsort函数，自己写compare比较函数即可，在php里是调用usort函数，但是面试考察大部分都是不能调用系统函数的，所以这里提供一下代码，供参考：

[cpp] view plain copy

/**
* 基准点排序
*
* T = O(n)
*
*/
int pivotLoc(int *arr, int bt, int ed)
{
int stand;
stand = arr[bt];
while (bt < ed) {
while (bt < ed && arr[ed] >= stand) ed —;
if (bt < ed) arr[bt ++] = arr[ed];
while (bt < ed && arr[bt] <= stand) bt ++;
if (bt < ed) arr[ed —] = arr[bt];
}
arr[bt] = stand;
return bt;
}
/**
* 快排入口代码，递归策略
*
* T = O(nlogn)
*
*/
void quickSort(int *arr, int bt, int ed)
{
int pivot;
if (bt < ed) {
pivot = pivotLoc(arr, bt, ed);
quickSort(arr, bt, pivot - 1);
quickSort(arr, pivot + 1, ed);
}
}

优化

快排的平均时间复杂度是O(nlogn),但是考虑一下最坏的情况：

假设给定的排序序列是逆序，例如5、4、3、2、1,然后用上述快排代码进行从小到大排序，很明显，快排从O（nlogn）降到了O(n^2)，如何避免这种情况呢？

解答：基准点的随机选取，我这里每次采用mid作为基准点

[cpp] view plain copy

/**
* 快排优化，随机选取基准点
*
*/
void optimizeSort(int *arr, int bt, int ed)
{
int mid = bt + ((ed - bt) >> 1);
// 不使用额外空间，进行两数互换
if (arr[bt] != arr[mid]) {
arr[bt] = arr[bt] ^ arr[mid];
arr[mid] = arr[bt] ^ arr[mid];
arr[bt] = arr[bt] ^ arr[mid];
}
}
/**
* 基准点排序
*
* T = O(n)
*
*/
int pivotLoc(int *arr, int bt, int ed)
{
int stand;
// 快排优化
if (bt < ed) {
optimizeSort(arr, bt, ed);
}
stand = arr[bt];
while (bt < ed) {
while (bt < ed && arr[ed] >= stand) ed —;
if (bt < ed) arr[bt ++] = arr[ed];
while (bt < ed && arr[bt] <= stand) bt ++;
if (bt < ed) arr[ed —] = arr[bt];
}
arr[bt] = stand;
return bt;
}
/**
* 快排入口代码，递归策略
*
* T = O(nlogn)
*
*/
void quickSort(int *arr, int bt, int ed)
{
int pivot;
if (bt < ed) {
pivot = pivotLoc(arr, bt, ed);
quickSort(arr, bt, pivot - 1);
quickSort(arr, pivot + 1, ed);
}
}

非递归法

/*
*BLOG:http://blog.csdn.net/wdzxl198
*AUTHOR:Atlas
*EMAIL:wdzxl198@163.com
*/
#include<iostream>
#include<stack>
using namespace std;
int Partition(int array[],int lhs,int rhs)
{
    int x = array[rhs];
    int i = lhs - 1;
    for(int j=lhs;j<=rhs-1;j++)
    {
        if(array[j] <= x)
        {
            ++i;
            std::swap(array[i],array[j]);
        }
    }
    std::swap(array[i+1],array[rhs]);
    return i+1;
}
void QuickSort(int *arr,int left,int right)
{
    stack<int> st;
    if(left < right)
    {
        int mid = Partition(arr,left,right);
        if(left < mid-1)
    {
            st.push(left);
            st.push(mid-1);
        }
        if(mid+1 < right)
    {
            st.push(mid+1);
            st.push(right);
        }
        while(!st.empty())
    {
            int q = st.top();
            st.pop();
            int p = st.top();
            st.pop();
            mid = Partition(arr,p,q);
            if(p < mid-1)
        {
                st.push(p);
                st.push(mid-1);
            }
            if(mid+1 < q)
        {
                st.push(mid+1);
                st.push(q);
            }       
        }
    }
    else
        return;
}
int main()
{
    int a[10] ={3,7,6,4,0,2,9,8,1,5};  
    for(int i=0;i<10;i++)
       cout<<a[i]<<" ";
    cout<<endl; 
    cout<<"快速排序：";    
    QuickSort(a,0,9);
    for(int i=0;i<10;i++)
        cout<<a[i]<<" ";
    cout<<endl;
    system("PAUSE");
    return 0;
}