sort.cpp

一些常用的代码

/************************************************************************/
/* 常用的排序算法														*/
/* 陈俊珊																*/
/* 2009-3-6                                                             */
/************************************************************************/

#include<iostream>
using namespace std;


/**
 * 功能:直接插入排序
 * 参数:t[]要排序的数组,len数组的长度
 * 返回:void ,t[]变成排序完的数组
 */
void InsertSort(int t[],int len)
{
	int i,j;

	for (i=1;i<len;i++)
	{
		t[0] = t[i];			 //t[0]为哨兵,且用来存放当前插入的值

		//从i处进行泡冒找位置
		for (j=i;t[0]<t[j-1];j--)
			t[j] = t[j-1];

		t[j]=t[0];				//找到相应的位置,插入值
	}
}

/**
 * 功能:二分插入排序
 * 参数:t[]要排序的数组,len数组的长度
 * 返回:void ,t[]变成排序完的数组
 */
void BInsertSort(int t[],int len)
{
	int i,j,low,high,mid;

	//顺序排序
	for (i=1;i<len;i++)
	{
		t[0] = t[i];			//哨兵,且用来存放当前的项
		low = 1,high =i-1;		

		//二分查找
		while(low<=high)
		{
			mid = (low+high)/2;	//要加括号
			if (t[0]<=t[mid])
				high = mid - 1;
			else
				low = mid + 1;
		}

		//后移
		for (j=i;j>low;j--)
			t[j] = t[j-1];

		t[low] = t[0];		//插入 t[low]和t[higt+1]均可 二分到最后low=higt+1
	}
}


/**
 * 功能:希尔排序
 * 参数:t[]需排序的数组,len数组的长度
 * 返回:void t[]变为排序完后的数组
 */
void ShellSort(int t[],int len)
{
	int i,j,dt,temp,k;

	dt = len/2;							//刚开始分组长度为数组长度的一半(这边也可以用一个数组来进行分段,但是最后一位必须为1)

	//跳跃式分组排序
	while (dt!=0)
	{
		//以dt为长度分组
		for (i=dt+1;i<len;i++)
		{				
			j = i-dt;					//j =>1,2,...,len-dt

			while (j>0)					//第一个放空
			{
				k = j + dt;				//与j间距为dt的项

				//如果前面的比后面的小,则无需交换
				if (t[j]<=t[k])
					j=0;
				//前面的比后面的大,需交换
				else
				{
					temp = t[j];
					t[j]=t[k];
					t[k]=temp;
				}
				j = j - dt;				//回到前一组再比较(如:13,55,38 13和55比 -> 55和38比 -> 13和38)
			}
		}
		dt = dt/2;						//一直减半,直到dt为1
	}
	
}


/**
 * 功能:进行冒泡排序
 * 参数:t[]需排序的数组,len数组长度
 * 返回:void t[]变为排序完后的数组
 */
void BubbleSort(int t[],int len)
{
	int i,j,temp;

	//冒泡(大的向下沉)
	for (i=1;i<len;i++)
	{
		for (j=1;j<len-i;j++)
		{
			//前一个比较大则交换
			if (t[j+1]<t[j])
			{
				temp = t[j];
				t[j] = t[j+1];
				t[j+1] = temp;
			}
		}
	}
}


/**
 * 功能:进行快速排序
 * 参数:t[]需排序的数组,len数组长度
 * 返回:void t[]变为排序完后的数组
 */
void QuickSort(int t[],int low,int high)
{
	int i,j,pivot;		//pivot表示轴
	
	//从两边交替直到low=high
	if (low<high)
	{
		i=low;
		j=high;
		pivot = t[low];	//设置轴的值
	
		//循环扫描
		while (i<j)
		{
			//从高端开始寻找比轴小的位置
			while (i<j && t[j]>=pivot)
				j--;

			//如果找到一个比轴小的且还没到交接处,则交换且i向前一步
			if (i<j)
				t[i++] = t[j];
			
			//从低端开始寻找比轴大的位置
			while (i<j && t[i]<=pivot)
				i++;

			//如果找到一个比轴大的且还没到交接处,则交换且j向后一步
			if (i<j)
				t[j--] = t[i];

		}

		t[i] = pivot;			  //最后把值放到相应的位置

		QuickSort(t,low,i-1);	  //递归左半边
		QuickSort(t,i+1,high);	  //递归右半边
	}
}

/**
 * 功能:建堆过程 (这边的堆为小顶堆)
 * 参数:t[]需排序的数组,len数组长度,s为开始调整的元素
 * 返回:void t[]变为调整好的堆
 */
void HeapAdjust(int t[],int len,int s)
{
	int i,temp;

	temp = t[s];			//存放可能要向下渗透的元素
	
	//i为开始元素s的左孩子,乘2为一直向下渗透
	for (i=2*s;i<len;i*=2)
	{
		//选出左孩子和右孩子中较大的
		if (i<len-1 && t[i]<t[i+1])		//i必须小于len-1,否则t[i+1]会越界
			i++;						//如果右边比较大,则下标变为右孩子的下标
		
		//渗透元素和较大的孩子比较,比较大则向下渗透
		if (temp < t[i])
		{
			t[s] = t[i];	
			s = i;			//调整渗透元素,继续向下渗透
		}
		else
			break;			//已经是堆了,则跳出
	}

	t[s] = temp;			//把刚开始的渗透元素填入相应的位置

}
/**
 * 功能:堆排序
 * 参数:t[]需排序的数组,len数组长度
 * 返回:void t[]变为排序完后的数组
 */
void HeapSort(int t[],int len)
{
	int i,temp;

	//初始化堆,把堆看成是完全二叉树
	for (i=len/2;i>0;i--)	
		HeapAdjust(t,len,i);

	//循环输出最小元素,即堆顶元素
	for (i=len-1;i>=1;i--)
	{
		//把排序好的堆,首位放到最后
		temp = t[1];
		t[1] = t[i];
		t[i] = temp;
		
		//除去输出的元素后,调整剩下的堆为排序好的堆
		HeapAdjust(t,i-1,1); 
	}
}

void print(int t[],int len,char opt)
{
	switch(opt)
	{
	case 'i':
		cout<<"插入排序结果为:";
		break;
	case 'b':
		cout<<"二分排序结果为:";
		break;
	case 's':
		cout<<"shell排序结果为:";
		break;
	case 'm':
		cout<<"冒泡排序结果为:";
		break;
	case 'q':
		cout<<"快速排序结果为:";
		break;
	case 'h':
		cout<<"堆排序的结果为:";
		break;
	default:
		break;
	}

	for (int i=1;i<len;i++)
		cout<<t[i]<<" ";
	cout<<endl;
	
}


int main()
{
	char opt;

	//为了统一风格,数组首位要么为哨兵,要么放空没用
	int t[]={100,6,8,7,2,9,10,1,80,3,64,12,13,54,22,66,88,56,78,24,2,5,6,7,45,4,65,12,32,12};
	int len = sizeof(t)/sizeof(int);
	
	cout<<"请选择一种排序方式(i|b|s|m|q|h):";
	cin>>opt;

	switch (opt)
	{
	case 'i':
		InsertSort(t,len);
		break;
	case 'b':
		BInsertSort(t,len);
		break;
	case 's':
		ShellSort(t,len);
		break;
	case 'm':
		BubbleSort(t,len);
		break;
	case 'q':
		QuickSort(t,1,len-1);
		break;
	case 'h':
		HeapSort(t,len);
		break;
	default:
		break;
	}

	print(t,len,opt);

	return 0;
}