快速排序的基本思想是:通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分,其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小,則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序剔宪，已達(dá)到整個(gè) 序列有序.
快速排序是一種不穩(wěn)定的排序方法扒吁，其平均時(shí)間復(fù)雜度為: O(NlogN).
特別注意：快速排序中用到的Partition函數(shù)觅捆，它的作用是進(jìn)行一趟快速排序，返回"曲軸“記錄所在的位置p."曲軸“記錄就是一個(gè)參考記錄,經(jīng)過Partition處理之后,p左邊的記錄關(guān)鍵字均不大于曲軸記錄的關(guān)鍵字,p右邊的記錄關(guān)鍵字均不小于曲軸記錄的關(guān)鍵字。
Partition函數(shù)在找出數(shù)組中最大或最小的k個(gè)記錄也很有用.
快速排序的遞歸和非遞歸實(shí)現(xiàn)的代碼余下:
// 快速排序.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。
#include "stdafx.h"
#include <iostream>
#include <stack>
using namespace std;
/*
//Partition實(shí)現(xiàn)方法1,嚴(yán)蔚敏版數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)方法
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];
}
//此時(shí)low==high
a[low]=pivotkey;
return low;
}
*/
//交換a與b的值
void swap(int &a,int &b)
{
int temp=a;
a=b;
b=temp;
}
//Partition實(shí)現(xiàn)方法2,算法導(dǎo)論實(shí)現(xiàn)方法
int Partition(int * a,int low,int high)
{
int pivotkey=a[high];//將最后一個(gè)元素當(dāng)做曲軸
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);
}
//非遞歸方式實(shí)現(xiàn)快速排序
//定義一個(gè)記錄待排序的區(qū)間[low,high]
typedef struct Region
{
int low;
int high;
}Region;
void NonRecursiveQuickSort(int *a,int len)
{
stack<Region> regions;//定義一個(gè)棧變量
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
