快速排序的递归和非递归实现

快速排序的基本思想是:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序，已达到整个 序列有序.

快速排序是一种不稳定的排序方法，其平均时间复杂度为: O(NlogN).

特别注意：快速排序中用到的Partition函数，它的作用是进行一趟快速排序，返回"曲轴“记录所在的位置p."曲轴“记录就是一个参考记录,经过Partition处理之后,p左边的记录关键字均不大于曲轴记录的关键字,p右边的记录关键字均不小于曲轴记录的关键字。
Partition函数在找出数组中最大或最小的k个记录也很有用.

快速排序的递归和非递归实现的代码余下:

// 快速排序.cpp : 定义控制台应用程序的入口点。  
#include "stdafx.h"  
#include <iostream>  
#include <stack>  
using namespace std;  
  
/* 
//Partition实现方法1,严蔚敏版数据结构实现方法 
int Partition(int * a,int low,int high) 
{ 
  int pivotkey=a[low]; 
  while(low<high) 
  { 
    while(low<high && a[high]>=pivotkey) 
        --high; 
    a[low]=a[high]; 
    while(low<high && a[low]<=pivotkey) 
        ++low; 
    a[high]=a[low]; 
  } 
  //此时low==high 
  a[low]=pivotkey; 
  return low; 
} 
*/  
  
//交换a与b的值  
void swap(int &a,int &b)  
{  
  int temp=a;  
  a=b;  
  b=temp;  
}  
  
//Partition实现方法2,算法导论实现方法  
int Partition(int * a,int low,int high)  
{  
  int pivotkey=a[high];//将最后一个元素当做曲轴  
  int p=low-1;  
  for(int j=low;j<high;j++)  
  {  
    if(a[j]<=pivotkey)  
    {  
        p++;  
        if(p!=j)  
        {  
          swap(a[p],a[j]);//在p前面的都是大于pivotkey的元素  
        }                 //在p位置和其后的都是小于等于pivotkey的元素  
    }  
  }  
  p+=1;  
  swap(a[p],a[high]);  
  return p;  
}  
  
  
void QSort(int *a,int start,int end)  
{  
    if(start<end)  
    {  
      int p=Partition(a,start,end);  
      QSort(a,start,p-1);  
      QSort(a,p+1,end);  
    }  
}  
  
//递归形式的快速排序   
void QuickSort(int *a,int len)  
{  
  QSort(a,0,len-1);  
}  
  
//非递归方式实现快速排序  
  
//定义一个记录待排序的区间[low,high]  
typedef struct Region  
{  
     int low;  
     int high;  
}Region;  
  
void NonRecursiveQuickSort(int *a,int len)  
{  
   stack<Region> regions;//定义一个栈变量  
   Region region;  
   region.low=0;  
   region.high=len-1;  
   regions.push(region);  
   while(!regions.empty())  
   {  
     region=regions.top();  
     regions.pop();  
     int p=Partition(a,region.low,region.high);  
     if(p-1>region.low)  
     {  
         Region regionlow;  
         regionlow.low=region.low;  
         regionlow.high=p-1;  
         regions.push(regionlow);  
     }  
     if(p+1<region.high)  
     {  
         Region regionhigh;  
         regionhigh.low=p+1;  
         regionhigh.high=region.high;  
         regions.push(regionhigh);  
     }  
   }  
}  
  
void printArray(int *a,int len)  
{  
  for(int i=0;i<len;i++)  
      cout<<a[i]<<" ";  
  cout<<endl;  
}  
  
int _tmain(int argc, _TCHAR* argv[])  
{  
    int a[]={49,38,65,97,76,13,27,49};  
    int len=sizeof(a)/sizeof(int);  
    printArray(a,len);  
    //QuickSort(a,len);  
    NonRecursiveQuickSort(a,len);  
    printArray(a,len);  
    system("PAUSE");  
    return 0;  
}  

From:
http://blog.csdn.net/yunzhongguwu005/article/details/9455991