| 站点地图 | 联系我
| www.asm32.net | 2006版 | 资料中心 | linux | asm/asm32 | C/C++ | VC++ | java | 书签 | ASP.Net书签 | 上善若水 厚德载物
 现在位置 :: 主页 >> 资料中心 >> ROOT / CODE / C/C++ /
 

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

来源(博客频道 - CSDN.NET)

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

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

标签: 快速排序

2013-07-24 21:49 8906人阅读 评论(1)

分类: 算法与数据结构(22)

版权声明:本文为博主原创文章,未经博主允许不得转载。

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

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

Link: http://www.asm32.net/article_details.aspx?id=7193


浏览次数 0 发布时间 2017/4/16 10:10:08 从属分类 C/C++ 【评论】【 】【打印】【关闭
 
| www.asm32.net | 2006版 | 资料中心 | linux | asm/asm32 | C/C++ | VC++ | java | 书签 | ASP.Net书签 | 京ICP备09029108号-1