main.cpp

计算机算法

/*****
院系：信息科学与技术学院
专业：计算机技术
姓名：胡衡英
学号：08250797
******/

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

#define MAX 20  //预先定义数组大小

//实体位置交换
void swap(int &front, int &behind)
{
	int temp;  //定义一个临时变量用于交换的存储区
	temp = front;
	front = behind;
	behind = temp;
}

/**
功能：快速排序子程序
原理：以某序列的第一个元素为比较对象，从序列头部开始与这个元素比较，如果找到第一个大于这个元素的
	  元素，则进行交换，再从数组的尾部开始与这个元素进行比较，如果找到第一个小于这个元素的元素则
	  交换位置，这样反复以上操作，比较完毕一轮以后，比这个元素小的元素都在该元素的左边，比这个元
	  素大的元素都在该元素的右边(此时，这个元素为中间值，不大不小，不参与下一次递归比较)，再以这
	  个元素为分界点将原序列分解为2个子序列，分别进行相同规则的排序。递归调	  用该子程序，最终使
	  得比较结果为该序列中的所有元素从小到大排列。
*/
int subsort(int array[], int left, int right)
{
	int object = array[left];		//将子序列的第一个元素记下，作为比较对象
	int i = left - 1;				//序列首位置
	int j = right + 1;				//序列尾位置

	while(i+1 != j)
	{
		if(array[i+1] <= object)			//寻找左边第一个比比较对象大的值，没找到就继续找，找到
			i++;							//就停留在此，去从右边找起
		else if(array[j-1] > object)		//寻找右边第一个比比较对象小的值，没找到就继续找，找到
			j--;							//就停留在此，进行左右交换
		else								//这时左边的元素大于比较对象，右边的元素小于比较对象
			swap(array[++i], array[--j]);   //则交换左右两边的元素，确保小于该对象的在左边，大于
	}                                       //该对象的在右边

	array[left] = array[i];
	array[i] = object;

	cout<<"本次交换后结果为："<<array[0];
	for(int n=1; n<=MAX-1; n++)
		cout<<","<<array[n];
	cout<<endl;
	getch();

	return i;
}


//分治法，将序列分为两部分，然后重复按此法划分，直至无可划分为止
void sort(int array[], int left,int right)
{
	int objectsite;
	if (left < right) {

		//获得本轮比较对象排序后的所在位置
		objectsite = subsort(array, left, right);

		//这两个就是递归调用，分别整理比较对象的左边的数组和右边的数组
		//上一轮比较的对象将不参与下一轮比较
		sort(array, left, objectsite-1);
		sort(array, objectsite+1, right); 
	}
}

void main()
{
	//定义一个测试排序用的数组
	int test[20] = {18, 15, 6, 14, 3, 7, 2, 1, 9, 8, 5, 16, 10, 13, 12, 11, 0, 17, 19, 4};

	cout<<"排序前结果为："<<test[0];
	for(int i=1; i<=19; i++)
		cout<<","<<test[i];
	cout<<"(按空格跟踪运行情况)"<<endl;

	sort(test, 0, 19);

	cout<<"排序后结果为："<<test[0];
	for(int j=1; j<=19; j++)
		cout<<","<<test[j];
	cout<<endl;

	getch();
}