排序和查找_选择_冒泡_折半插入_快速_堆_顺序查找_折半查找.cpp

常用的数据结构排序和查找算法:简单选择排序,冒泡排序,折半插入排序,快速排序,堆排序 顺序查找,折半查找.

#include <iostream.h>
#include <conio.h>

#define MAXSIZE 50

/*typedef struct //定义排序表的结构
{
	int elemword[MAXSIZE]; //数据元素关键字
	int length; //表中当前元素的个数
}SqList;

void InitialSqList(SqList &L, int R[], int n)
{	//表初始化
	int i;
	L.length = n;
	for(i = 1; i <= L.length; i++)
		L.elemword[i] = R[i-1];
}*/

void SelectSort (int R[], int n)	//选择排序,升序
{	// 对记录序列R[0..n-1]作简单选择排序
	int min;
	int j;
	for (int i = 0; i < n; i++) 
	{	// 选择第i小的记录，并交换
		j = i;
		min = R[i];
		for (int k = i; k < n; k++) 
		{	// 在R[i..n-1]中选择最小的记录
			if (R[k] < min) 
			{
				min = R[k];
				j = k;
			}
		}
		if (i != j) 
		{	// 与第i个记录交换
			int temp = R[i];
			R[i] = R[j];
			R[j] = temp;
		}
	}
}	// SelectSort

void BubbleSort (int R[], int n)	//冒泡排序,升序
{	// 设待排记录放在R[0]到R[n-1]中
	for(int i = 0; i < n; i++)
        for(int j = 0; j < n - i - 1; j++)
            if(R[j] > R[j+1])	// 交换元素,每次寻找最大的让其沉底
			{
				int temp = R[j+1];
				R[j+1] = R[j];
				R[j] = temp;
			}
}	// BubbleSort

void BiInsertionSort (int R[], int n)	//折半插入排序,升序
{
	int low, high, temp, m;
	for (int i = 1; i < n; i++) 
	{
		temp = R[i];      // 将R[i]暂存到temp
		low = 0;   
		high = i - 1;
		while (low <= high)		 // 在R[0..i-1]中折半查找插入位置
		{ 
			m = (low + high) / 2;      // 折半	
			if (temp < R[m])
		        high = m - 1;        // 插入点在低半区
			else  
				low = m + 1;        // 插入点在高半区
		}
		for (int j = i - 1; j > high; j--)
			R[j + 1] = R[j];      // 记录后移
		R[high + 1] = temp;      // 插入
	}	// for
}	// BInsertSort

int SeqSearch (int R[], int n, int m)	//顺序从前往后查找
{
	for (int i = 0; i < n; i++)
	{
		if (R[i] == m)
			return i+1;
	}
	return -1;	//找不到则返回-1
}

int BiSearch (int R[], int n, int m)	//折半查找
{
	int low, high, mid;
	low = 0;
	high = n - 1;	
	while (low <= high)
	{
		mid = (low + high) / 2;
		if (R[mid] == m)
			return mid+1;
		if (m > R[mid])
			low = mid + 1;
		else
			high = mid - 1;
	}
	return -1;	//找不到则返回-1
}


int Partition (int R[], int low, int high) 
{
	int pivotkey = R[low];	// 枢轴  
	while (low < high) 
	{
		while ((low < high) && (R[high] >= pivotkey))	// 从右向左搜索
			high--;
		R[low] = R[high];
		while ((low < high) && (R[low] <= pivotkey))	// 从左向右搜索
			low++;
		R[high] = R[low];
	}
	R[low] = pivotkey;
	return low;     // 返回枢轴所在位置
}	// Partition


void QSort (int R[], int s, int t) 
{	// 对记录序列R[s..t]进行快速排序
	if (s < t) 
	{	// 长度大于1
		int pivotloc = Partition(R, s, t);	// 对 R[s..t] 进行一次划分
		QSort(R, s, pivotloc - 1);	// 对低子序列递归排序，pivotloc是枢轴位置
		QSort(R, pivotloc + 1, t);	// 对高子序列递归排序
	}
}	// QSort


void HeapAdjust(int R[], int s, int m)
{
	//已知R[s..m]中除R[s]之外均满足堆的定义,本函数调整R[s]
	//使R[s..m]成为一个大顶堆
	int j,rc;
	rc=R[s];
	for(j=2*s;j<=m;j*=2) //沿关键字叫大的结点向下筛选
	{
		if(j<m&&R[j]<R[j+1])
			++j; //j为关键字较大的记录的下标
		if(rc>=R[j])
			break; //rc应插入在位置s上
		R[s]=R[j];
		s=j;
	}
	R[s]=rc; //插入
}

void HeapSort(int R[], int n)
{
	//对顺序表R做堆排序
	int i,t;
	for(i=n/2;i>0;--i) //把R[1..n]建成大顶堆
		HeapAdjust(R,i,n);
	for(i=n;i>1;--i)
	{//大顶堆
		t=R[1]; //将堆顶记录和当前未经排序子序列R[1..i] 
		R[1]=R[i]; //中的最后一个记录相互交换
		R[i]=t;//此交换将最大元素放在末尾,即取出堆顶元素
		HeapAdjust(R,1,i-1); //将R[1..i-1]重新调整为大顶堆
	}
}

void main()
{
	char next = 'y';
	int n, i, m2;
	int *num;
	int *num2;
	int *num3;
	cout<<"请输入元素个数:"<<endl;
	cin>>n;
	num = new int[n];
	num2 = new int[n];
	num3 = new int[n + 1];
	cout<<"请依次输入每个元素:"<<endl;
	for(i = 0; i < n; i++)
		cin>>num[i];
	cout<<"您输入的元素为:"<<endl;
	for(i = 0; i < n; i++)
		cout<<num[i]<<" ";
	cout<<endl;

	for(i = 0; i < n; i++)
		num2[i]=num[i];
	cout<<"选择排序:"<<endl;
	SelectSort(num2, n);
	for(i = 0; i < n; i++)
		cout<<num2[i]<<" ";
	cout<<endl;

	for(i=0; i<n; i++)
		num2[i]=num[i];
	cout<<"冒泡排序:"<<endl;
	BubbleSort(num2, n);
	for(i = 0; i < n; i++)
		cout<<num2[i]<<" ";
	cout<<endl;

	for(i = 0; i < n; i++)
		num2[i]=num[i];
	cout<<"折半插入排序:"<<endl;
	BiInsertionSort(num2, n);
	for(i = 0; i < n; i++)
		cout<<num2[i]<<" ";
	cout<<endl;

	for(i = 0; i < n; i++)
		num2[i]=num[i];
	cout<<"快速排序:"<<endl;
	QSort(num2, 0, n-1);
	for(i = 0; i < n; i++)
		cout<<num2[i]<<" ";
	cout<<endl;

	for(i = 0; i < n; i++)
		num3[i + 1]=num[i];
	cout<<"堆排序:"<<endl;
	HeapSort(num3, n);
	for(i = 0; i < n; i++)
		cout<<num3[i+1]<<" ";
	cout<<endl;

	cout<<"您输入的元素为:"<<endl;
	for(i = 0; i < n; i++)
		cout<<num[i]<<" ";
	cout<<endl;
	while(next != 'n')
	{
		cout<<"请输入要查找的元素:"<<endl;
		cin>>m2;
		cout<<"顺序查找(原始序列):"<<endl<<SeqSearch(num, n, m2)<<endl;
		cout<<"顺序查找(排序序列):"<<endl<<SeqSearch(num2, n, m2)<<endl;
		cout<<"折半查找(排序序列):"<<endl<<BiSearch(num2, n, m2)<<endl;
		cout<<"继续?(y/n):"<<endl;
		cin>>next;
	}
	cout<<"任意键退出"<<endl;
	getch();
}