当前位置:首页 > 开发 > 编程语言 > 算法 > 正文

c++ 实现五种基础的排序算法

发表于: 2015-06-11   作者:CrazyMizzz   来源:转载   浏览:
摘要: #include<iostream> using namespace std; //辅助函数,交换两数之值 template<class T> void mySwap(T &x, T &y){ T temp = x; x = y; y = temp; } const int size = 10; //一、用直接插入排
#include<iostream>
using namespace std;


//辅助函数,交换两数之值
template<class T>
void mySwap(T &x, T &y){
	T temp = x;
	x = y;
	y = temp;
}

const int size = 10;

//一、用直接插入排序法对数组a中元素进行升序排序
/*直接插入排序的基本思想是:
*顺序地把待排序序列中的各个记录按其关键字的大小,插入到已排序的序列的适当位置。
*/


template<class T>
void insertionSort( T a[], int n){

	

	//将下标为1~n-1的元素逐个插入到已排序序列中适当的位置
	for (int i = 1; i != n; i++){

		//从a[i-1]开始向a[0]方向扫描各元素,寻找适当位置插入a[i]

		int j = i;
		T temp = a[i];
		while (j > 0 && temp < a[j - 1]){
			//逐个比较,直到temp>=a[j-1]时,j便是应插入的位置

			//若达到j==0,则0是应插入的位置

			a[j] = a[j - 1];//将元素逐个后移,以便找到插入位置使可立即插入

			j--;
		}
		//插入位置已找到,立即插入
		a[j] = temp;
		for (int i = 0; i != n; i++){//输出每步交换
			cout << a[i] << " ";
		}
		cout << endl;
	}
	
}




//二、用选择法对数组a中元素进行升序排序
/*
*选择排序的基本思想是:
*不断从待排序的序列中选取关键字最小的记录放到已排序的记录序列的后面,直到序列中所有记录都已排序为止。
*/

template<class T>
void selectionSort(T a[], int n){

	for (int i = 0; i != n - 1; i++){
		int leastIndex = i;//最小元素的下标初值设为i

		//在元素a[i+1]....a[n-1]中逐个比较,显出最小值
		for (int j = i + 1; j < n; j++){

			if (a[j] < a[leastIndex])//smallIndex始终记录当前找到的最小值的下标
				leastIndex = j;
			
		}


		mySwap(a[i], a[leastIndex]);//将这一趟找到的最小元素与a[i]交换


		for (int i = 0; i != n; i++){//输出每步交换
			cout << a[i] << " ";
		}
		cout << endl;
	}
}



//三、用起泡法对数组a中元素进行升序排序

/*起泡排序的基本思想是:
*将待排序序列中第一个记录的关键字R1与第二个记录的关键字R2做比较,
*如果R1>R2,则交换R1和R2的位置,否则不交换;
*然后继续对当前序列中的第二个记录和第三个记录同样的处理,依此类推。
*/

template<class T>
void bubbleSort(T a[], int n){
	int i = n - 1;							//i是下一趟需参与排序交换的元素的最大下标
	while (i > 0){							//继续排序过程,直到最后一趟排序没有交换发生,或已达n-1趟
		int lastExchangeIndex = 0;			//每一趟开始时,设置交换标志为0
		for (int j = 0; j < i; j++){		//每一趟对元素a[0]....a[i]进行比较和交换
			if (a[j + 1] < a[j]){			//如果元素a[j+1]<a[j],交换
				mySwap(a[j], a[j + 1]);

				for (int x = 0; x != size; x++){    //输出每步交换
					cout << a[x] << " ";
				}
				cout << endl;

				lastExchangeIndex = j;		//记录被交换的的一对元素中较小的下标
			}
		}
		i = lastExchangeIndex;		//将i设置为本趟被交换的最后一对元素中较小的下标
	}
}


//四、用希尔排序法对数组a中元素进行升序排序

/*希尔排序的基本思想是:
*不断把待排序的记录分成若干个小组,对同一组内的记录进行排序,
*在分组时,始终保证当前组内的记录个数超过前面分组排序时组内的记录个数。
*/
template<class T>
void shellSort(T a[], int n){

	for (int i = 0; i != size; i++){
		cout << a[i] << " ";
	}
	cout << endl;


	for (int i = n / 2; i > 0; i /= 2){

		for (int j = i; j < n; j++){

			int temp = a[j];
			int k = 0;
			for (k = j; k >= i; k -= i){

				if (temp < a[k - i]){
					a[k] = a[k - i];

				}else
				break;
			}

			a[k] = temp;

			for (int i = 0; i != size; i++){
				cout << a[i] << " ";
			}
			cout << endl;
		}
	}

}


//五、用快速排序法对数组a中元素进行升序排序
/**该方法的基本思想是:
1.先从数列中取出一个数作为基准数。
2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
3.再对左右区间重复第二步,直到各区间只有一个数。
*/
void quickSort(int s[], int l, int r)
{
	if (l< r)
	{
		int i = l, j = r, x = s[l];
		while (i < j)
		{
			while (i < j && s[j] >= x) // 从右向左找第一个小于x的数
				j--;
			if (i < j)
				s[i++] = s[j];
			while (i < j && s[i]< x) // 从左向右找第一个大于等于x的数
				i++;
			if (i < j)
				s[j--] = s[i];
		}
		s[i] = x;
		for (int i = 0; i != size; i++){
			cout << s[i] << " ";
		}
		cout << endl;
		quickSort(s, l, i - 1); // 递归调用
		quickSort(s, i + 1, r);
	}
}


int main(){
	int a[10] = { 13, 3, 1, 5, 2, 421, 2, 4, 3, 15 };
	int b[10] = { 13, 3, 1, 5, 2, 421, 2, 4, 3, 15 };
	int c[10] = { 13, 3, 1, 5, 2, 421, 2, 4, 3, 15 };
	int d[10] = { 13, 3, 1, 5, 2, 421, 2, 4, 3, 15 };
	int e[10] = { 13, 3, 1, 5, 2, 421, 2, 4, 3, 15 };
	cout <<  endl;
	for (int i = 0; i != size; i++){
		cout << a[i] << " ";
	}
	cout << endl;

	cout << "*********直接插入排序法************" << endl;
	insertionSort(a, size);
	cout << "*******直接插入排序法结束**********" << endl;


	cout << endl;
	for (int i = 0; i != size; i++){
		cout << b[i] << " ";
	}
	cout << endl;


	cout << "*********选择排序法************" << endl;
	selectionSort(b, size);
	cout << "*******选择排序法结束**********" << endl;

	cout << endl;
	for (int i = 0; i != size; i++){
		cout << c[i] << " ";
	}
	cout << endl;


	cout << "*********起泡排序法************" << endl;
	bubbleSort(c, size);
	cout << "*******起泡排序法结束**********" << endl;

	cout << endl;
	for (int i = 0; i != size; i++){
		cout << d[i] << " ";
	}
	cout << endl;


	cout << "*********希尔排序法************" << endl;
	shellSort(d, size);
	cout << "*******希尔排序法结束**********" << endl;

	cout << endl;
	for (int i = 0; i != size; i++){
		cout << d[i] << " ";
	}
	cout << endl;

	cout << "*********快速排序法************" << endl;
	quickSort(e, 0,size-1);
	cout << "*******快速排序法结束**********" << endl;

	for (int i = 0; i != size; i++){
		cout << e[i] << " ";
	}
	cout << endl;
}

c++ 实现五种基础的排序算法

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
一直以来就很想整理一下基本的算法实现,工作太忙一直没有来得及整理。 基本排序算法: 首先:代码
希尔排序是一种按照增量排序的方法。其中增量值是小于n的正整数。 shell排序的基本思想[1]是: 先取
插入排序的基本思想是每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子文件中的适
选择排序算法就是每一趟从待排序的记录中选出关键字最小(最大)的记录,顺序放在已排好序的子文件
归并排序是利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。常见
与之前的那些比较排序不同,分配排序在排序过程无须比较关键字,而是通过"分配"和"收集"过程来实现
所谓交换,就是根据序列中两个记录值的比较结果来对换这两个记录在序列中的位置。交换排序的特点是
快速排序算法C++实现[评注版] 经常看到有人在网上发快速排序的算法,通常情况下这些人是在准备找工
前言: 本人自接触算法近2年以来,在不断学习中越多地发觉各种算法中的美妙。之所以在这方面过多的
《数据结构与算法分析》几乎是所有计算机编程的基础,而在招聘过程中基本上只要是中大型的互联网公
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号