博客
关于我
排序(插入排序、起泡排序、选择排序和快速排序)
阅读量:563 次
发布时间:2019-03-09

本文共 1790 字,大约阅读时间需要 5 分钟。

排序

一、插入排序

算法思想:逐步将记录插入到已排好序的有序表中。

(一)直接插入排序(Straight Insertion Sort)

//直接插入排序void InsertSort(int a[], int n){   	int i,j;	int t; //交换中间变量 	//从第二个开始插入	for(i = 2; i<=n; i++) //控制循环多少趟 	{   		if(a[i-1]>a[i])		{   			a[0] = a[i];			for(j = i-1; a[j] > a[0]; j--)				a[j+1] = a[j]; //大于a[0]的记录往后移 			a[j+1] = a[0];		}	}}

(二)折半插入排序(Binary Insertion Sort)

//折半插入排序 void BInsertSort(int a[], int n){   	int i,j;	int t;	int low, high, mid;	for(i = 2; i<=n; i++) //控制循环的趟数,每一趟采用折半查找 	{   		a[0] = a[i];		low = 1; 		high = i-1;		while(low <= high)		{   			mid = (low + high)/2;			if(a[mid] >= a[0])				high = mid - 1;			else				low = mid + 1;		}		for(j = i-1; j >= high+1; j--) //查找之后进行记录后移 			a[j+1] = a[j];		a[high+1] = a[0];	}}

二、起泡排序(Bubble Sort)

算法思想:从前向后依次检查每一对相邻元素,一旦发现逆序即交换二者的位置。对于长度为n的序列,共需做n - 1次比较和不超过n - 1次交换,这一过程称作一趟扫描交换。每一趟扫描都至少会有一个元素就位。

//起泡排序void BubSort(int a[], int n){   	int i, j, t;	for(i = 1; i
a[j+1]) { t = a[j]; a[j] = a[j+1]; a[j+1] = t; } } }}

三、快速排序(Quick Sort)

算法思想: 通过一趟排序将第一个记录排好位置,同时将待排序记录分割成独立的两部分。其中前部分的关键字都比后部分的关键字小。然后再分别对这两部分继续递归排序,以达到整个序列有序。

//第一趟排序int Partition(int a[], int low, int high){   	int pkey;	pkey = a[low];	while(low < high)	{   		while(a[high] >= pkey && low < high)			high--;		a[low] = a[high];		while(a[low] < pkey && low < high)			low++;		a[high] = a[low];	}	a[low] = pkey;	return low;}//进行递归排序void QSort(int a[], int low, int high){   	if(low < high)	{   		int mid = Partition(a, low, high);		QSort(a, low, mid-1);		QSort(a, mid+1, high);	}}void QuickSort(int a[], int n){   	QSort(a, 1, n);}

四、简单选择排序(Simple Selection Sort)

算法思想:

  1. 第一趟:
    在n个记录中选一个最小关键字的记录与第一个记录进行交换;
  2. 第二趟:
    在后n-1个记录中选一个最小关键字的记录与第二个记录交换;
  3. 第 i 趟:
    在后n-(i-1)个记录中选一个最小关键字的记 与第i个记录交换; 共需n-1趟。
void SelectSort(int a[], int n){   	int i, j;	int min, t;	for(i = 1; i

转载地址:http://vytpz.baihongyu.com/

你可能感兴趣的文章
MySQL 中开启二进制日志(Binlog)
查看>>
MySQL 中文问题
查看>>
MySQL 中日志的面试题总结
查看>>
mysql 中的all,5分钟了解MySQL5.7中union all用法的黑科技
查看>>
MySQL 中的外键检查设置:SET FOREIGN_KEY_CHECKS = 1
查看>>
Mysql 中的日期时间字符串查询
查看>>
mysql 中索引的问题
查看>>
MySQL 中锁的面试题总结
查看>>
MySQL 中随机抽样:order by rand limit 的替代方案
查看>>
MySQL 为什么需要两阶段提交?
查看>>
mysql 为某个字段的值加前缀、去掉前缀
查看>>
mysql 主从
查看>>
mysql 主从 lock_mysql 主从同步权限mysql 行锁的实现
查看>>
mysql 主从互备份_mysql互为主从实战设置详解及自动化备份(Centos7.2)
查看>>
mysql 主从关系切换
查看>>
MYSQL 主从同步文档的大坑
查看>>
mysql 主键重复则覆盖_数据库主键不能重复
查看>>
Mysql 事务知识点与优化建议
查看>>
Mysql 优化 or
查看>>
mysql 优化器 key_mysql – 选择*和查询优化器
查看>>