学步园

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

  快速排序是一种不稳定的排序方法，其平均时间复杂度为: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;
}