sort.cpp

各种排序算法

//冒泡排序、选择排序和插入排序等的时间复杂性是O(n2)，
//快速排序、堆排序和归并排序等高级排序算法的时间复杂度为O(n*logn)，
//因此后者的排序效率较高。但这并不意味着总是要使用高级排序算法，下面给出各种排序算法选用的一般原则：
//（1）当数据量不大时选插入或选择排序，不要用冒泡排序；
//事实上，冒泡排序虽然简单，但的确是最不宜采用的排序算法，因为其性能表现是最差的。
//（2）当数据量大而又注重时间复杂度时选快速或堆排序等；
//堆排序的设计思路是：定义堆为一个键值序列{k1 ,k2 ,…,kn}，
//它具有如下特性：ki < = k2i，ki < = k2i + 1 (i = 1 ,2 ,…, [ n/ 2 ]) 。
//对一组待排序的键值，首先把它们按堆的定义排列成一个序列(称为初建堆)，这就找到了最小键值。
//然后将最小的键值取出，用剩下的键值再重新建堆，便得到次小键值。
//如此反复进行，直到把全部键值排好序为止由于快速排序和堆排序算法较复杂，因此在待排序的数据量较小时反而比插入和选择排序慢；
//（3）当要在已排序数据上增加新数据时选插入排序。当原有数据本身就有序时，插入排序的性能非常好。
//在已排序数据上增加新数据时，时间复杂性仅为O(n)。
																															
#include <iostream>
#include <math.h>
using namespace std;

void Selection_Sort(int a[],int size);
void Sort_Bubble(int a[], int size);
void Sort_Bubble_BiDirectional(int a[],int size);
void Sort_Insert(int a[],int size);
void Sort_Fast(int a[],int low,int high);
void Sort_Shell(int a[],int size);
void main()
{
	int a[10] = {12,23,4,56,43,3,17,89,7,32};
	Selection_Sort(a,10);
	for(int i=0;i<10;i++)
		cout<<a[i]<<" ";
	cout<<endl;

	int b[10] = {12,23,4,56,43,3,17,89,7,32};
	Sort_Bubble(b,10);
	for(i=0;i<10;i++)
		cout<<b[i]<<" ";
	cout<<endl;

	int c[20] = {12,34,3,567,213412,32,234,34,6,2344,344,67,5,2,235,6456,45646,23,98,232};
	Sort_Bubble_BiDirectional(c,20);
	for(i=0;i<20;i++)
		cout<<c[i]<<" ";
	cout<<endl;

	int d[20] = {12,34,3,567,213412,32,234,34,6,2344,344,67,5,2,235,6456,45646,23,98,232};
	Sort_Insert(d,20);
	for(i=0;i<20;i++)
		cout<<d[i]<<" ";
	cout<<endl;

	int e[20] = {12,34,3,567,213412,32,234,34,6,2344,344,67,5,2,235,6456,45646,23,98,232};
	Sort_Fast(e,0,19);
	for(i=0;i<20;i++)
		cout<<e[i]<<" ";
	cout<<endl;

	
	int f[20] = {12,34,3,567,213412,32,234,34,6,2344,344,67,5,2,235,6456,45646,23,98,232};
//	for(i=0;i<20;i++)
//		cout<<f[i]<<" ";
//	cout<<endl;
	
	Sort_Shell(f,20);
	for(i=0;i<20;i++)
		cout<<f[i]<<" ";
	cout<<endl;

	int g[10]={49,38,65,97,76,13,27,49,55,04};
	Sort_Shell(g,10);
	for(i=0;i<10;i++)
		cout<<g[i]<<" ";
	cout<<endl;



}

//////////////////////////////////////////////////////////////////////////
//选择排序法：
//基本思想：将第i项分别和第i+1,i+2,...项比较，将最大（或最小）的项放到i。
//////////////////////////////////////////////////////////////////////////
void Selection_Sort(int a[],int size)
{
	int i,j;
	int temp;
	for(i=0;i<size;i++)
	{
		for(j=i;j<size;j++)
		{
			if(a[i]>a[j])
			{
				temp = a[i];
				a[i] = a[j];
				a[j] = temp;
			}
		}
	}
}
//////////////////////////////////////////////////////////////////////////
//冒泡排序法：
//基本思路：每次循环将一个最大（或最小）的项放在序列的最后（或最前面）
//改进方法一：设置一个标志，如果在一次循环中没有任何交换，说明排序已经完成，可以跳出
//改进方法二：双向排序，设置两个标志为，分别指示当前已经排好序的最低和最高的数据项
//////////////////////////////////////////////////////////////////////////
void Sort_Bubble(int a[],int size)
{
	bool b = false; //true 进行了比较，false 没有进行比较.如果中间某次循环排序没有进行比较,说明排序已经完成,不必进行后面的循环
	int temp;
	int i,j;
	
	for(i=0;i<size;i++)
	{
		for(j=0;j<size-1-i;j++)
		{	
			if(a[j]>a[j+1])
			{
				temp = a[j];
				a[j] = a[j+1];
				a[j+1] = temp;
				b = true;
			}
		}
		if(b == false)
			return;	
	}
	
}
//////////////////////////////////////////////////////////////////////////
//冒泡排序法改进方法二
//////////////////////////////////////////////////////////////////////////
void Sort_Bubble_BiDirectional(int a[],int size)  //双向排序法
{

	int temp;
	int i;
	int low = 0 ,up = size-1;
	int flag;
	bool b = false;
	
	while(low<up)
	{
		flag = low;
		for(i=low;i<up;i++)
		{
			if(a[i]>a[i+1])
			{
				temp = a[i];
				a[i] = a[i+1];
				a[i+1] = temp;
				flag = i;
				b = true;
			}
		}
		up = flag;
		for(i=up;i>low;i--)
		{
			if(a[i]<a[i-1])
			{
				temp = a[i];
				a[i] = a[i-1];
				a[i-1] = temp;
				flag = i;
				b =true;
			}
		}
		low = i;
		if(b == false)
			return;
		b = false;

	}	
}
//////////////////////////////////////////////////////////////////////////
//插入排序法：
//基本思想：经过i-1遍处理后,a[1..i-1]己排好序。
//第i遍处理仅将a[i]插入a[1..i-1]的适当位置，使得a[1..i]又是排好序的序列。
//////////////////////////////////////////////////////////////////////////
void Sort_Insert(int a[],int size)
{
	int i,j,x;
	int temp;
	for(i=1;i<size;i++)
	{
		for(x=0;x<i;x++)
		{
			if(a[i]<=a[x])
				break;
		}
		temp=a[i];
		for(j=i;j>x;j--)
		{
			a[j]=a[j-1];
		}
		a[x]=temp;
	}
}
//////////////////////////////////////////////////////////////////////////
//快速排序法：
//基本思想：
//////////////////////////////////////////////////////////////////////////
void Sort_Fast(int a[],int low,int high)//用快速排序法
{
	// low, high表示扫描的范围
	
	int pivot;//存放中心索引及其值的局部变量
	int scanup,scandown,mid;//用于扫描的索引
	if (high-low<=0) //如果数组中的元素少于两个,则返回
		return;
	else 
	{
		if(high-low==1) //如果有两个元素,对其进行比较
		{
			if(a[high]<a[low]) //如果后一个比前一个小,
				swap(a[low],a[high]);//那么交换位置
			return;
		}//end if
		
		mid=(low+high)/2;//取得中心索引
		pivot=a[mid];//将中间索引的值,赋给pivot
		swap(a[mid],a[low]);//交换pivot及低端元素的值
		scanup=low+1;
		scandown=high;//初始化扫描索引scanup和scandown
		do{
			//从低端子表向上扫描,当scanup进入高端子表或遇到大于pivot的元素时结束.
			while(scanup<=scandown && a[scanup]<=pivot)
				scanup++;
			//从高端子表向下扫描,当scandown遇到小于或等于pivot的元素时结束
			while(pivot<a[scandown])
				scandown--;
			//如果两个索引还在各自的子表中,则表示两个元素错位,将两个元素换位
			if(scanup<scandown)
				swap(a[scanup],a[scandown]);
		}while(scanup<scandown);
		//将pivot拷贝到scandown位置,分开两个子表
		a[low]=a[scandown];
		a[scandown]=pivot;
		//如果低端子表(low至scandown-1)有2个或更多个元素,则进行递归调用
		if(low<scandown-1)
			Sort_Fast(a,low,scandown-1);
		//如果高端子表(scandown+1至high) 有2个或更多个元素,则进行递归调用
		if(scandown+1<high)
			Sort_Fast(a, scandown+1, high);
	}
}
//////////////////////////////////////////////////////////////////////////
//快速排序法
//////////////////////////////////////////////////////////////////////////
int partition(int a[],int p,int r)
{
	int i,j,x;
	i=p;
	j=r+1;
	x=a[p];
	while(true)
	{
		while(a[++i]<x);
		while(a[--j]>x);
		if(i>=j)
			break;
		swap(a[i],a[j]);
	}
	a[p]=a[j];
	a[j]=x;
	return j;
}
void quicksort(int a[],int p,int r)
{
	if (p<r)
	{
		int q=partition(a,p,r);
		quicksort(a,p,q-1);
		quicksort(a,q+1,r);
	}
}
//////////////////////////////////////////////////////////////////////////
//Shell排序法
//////////////////////////////////////////////////////////////////////////
void Sort_Shell(int a[],int size)
{
	for(int gap=size/2;gap>0;gap/=2)
	{
		for(int i=gap;i<size;i++)
		{
			for(int j=i-gap;j>=0;j-=gap)
			{
				if(a[j]>a[j+gap])
					swap(a[j],a[j+gap]);
			}
		}
	}
}