快速排序的基本思想是:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序，已达到整个 序列有序.
快速排序是一种不稳定的排序方法，其平均时间复杂度为: 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
