排序汇总

排序算法即是一种能将一串数据依照特定排序方式进行排列的一种算法。本文将简单介绍几种常用的排序算法,并给出源代码,仅供参考。

1.直接插入排序:是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

2.希尔排序:是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。实质上是一种分组插入方法。

3.冒泡排序:重复地遍历要排序的数列,一次比较相邻两个元素,如果顺序颠倒(取决于排序要求)就把他们交换过来。直到不再需要交换,也就是说此时该序列已经排序完成。

4.简单选择排序:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找次小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

5.堆排序:堆排序是指利用堆积树(堆)这种数据结构所设计的一种排序算法,是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆,是一种近似于完全二叉树的结构。大根堆的要求是每个节点的值都不大于其父结点的值,即A[PARENT[i]] >= A[i]。在数组的非降序排序中,需要使用的就是大根堆,因为根据大根堆的要求可知,最大的值一定在堆顶。

6.归并排序:归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

归并过程为:比较a[i]和a[j]的大小,若a[i]≤a[j],则将第一个有序表中的元素a[i]复制到r[k]中,并令i和k分别加上1;否则将第二个有序表中的元素a[j]复制到r[k]中,并令j和k分别加上1,如此循环下去,直到其中一个有序表取完,然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现,先把待排序区间[s,t]以中点二分,接着把左边子区间排序,再把右边子区间排序,最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。

7.快速排序:基本思想是通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

源代码如下:

#include "stdio.h"

typedef struct table
{
	int data[10];
	int length;
}table;

void create(table &T);                             //创建线性表
void swap(int &a, int &b);                         //交换两变量值
void insert_sort(table T);                         //直接插入排序
void shell_sort(table T);                          //希尔排序
void bubble_sort(table T);                         //冒泡排序
void select_sort(table T);                         //简单选择排序
void heap_sort(table T);                           //堆排序
void merge_sort(table &s, int left, int right);    //归并排序
void quick_sort(table &T, int left, int right);    //快速排序

int main()
{
	table T;
	create(T);
	insert_sort(T);                                //直接插入排序
	shell_sort(T);                                 //希尔排序
	bubble_sort(T);                                //冒泡排序
	select_sort(T);                                //简单选择排序
	heap_sort(T);                                  //堆排序
	table s = T;
	merge_sort(s, 0, T.length);                    //归并排序
	printf("归并排序后结果为:");
	for(int j = 0; j < s.length; ++j)
	printf("%d ", s.data[j]);
	printf("\n\n");
	printf("快速排序前序列为:");
	for(j = 0; j < T.length; ++j)
	printf("%d ", T.data[j]);
	printf("\n\n");
	quick_sort(T, 0, T.length-1);                  //快速排序
	printf("快速排序后结果为:");
	for(j = 0; j < T.length; ++j)
	printf("%d ", T.data[j]);
	printf("\n");

	return 0;
}

void create(table &T)
{
	int a[8] = {6, 2, 4, 8, 5, 3, 7, 1};
	T.length = 8;
	for(int i = 0; i < T.length; ++i)
		T.data[i] = a[i];
	printf("线性表中元素:");
	for(i = 0; i < T.length; ++i)
		printf("%d ", T.data[i]);
	printf("\n\n");
}
//交换两变量值
void swap(int &a, int &b)
{
	int k;
	k = a;
	a = b;
	b = k;
}
//直接插入排序
void insert_sort(table T)
{
	int i, j;
	for(i = 1; i < T.length; ++i)
		for(j = i; j > 0; --j)
			if(T.data[j-1] > T.data[j])
				swap(T.data[j-1], T.data[j]);
	printf("直接插入排序后结果为:");
	for(i = 0; i < T.length; ++i)
		printf("%d ", T.data[i]);
	printf("\n\n");
}
//折半查找排序
void shell_sort(table T)
{
	int i, d, j;
	for(d = T.length/2; d >= 1; d = d/2)
		for(i = d; i < T.length; ++i)
			for(j = i; j > 0; j = j - d)
				if((j - d >= 0) && (T.data[j] < T.data[j-d]))
					swap(T.data[j-d], T.data[j]);
	printf("希尔排序后结果为:");
	for(i = 0; i < T.length; ++i)
		printf("%d ", T.data[i]);
	printf("\n\n");
}
//冒泡排序
void bubble_sort(table T)
{
	int i, j;
	for(i = 0; i < T.length - 1; ++i)
	{
		for(j = 0; j < T.length - 1 - i; ++j)
			if((j < T.length) && (T.data[j] > T.data[j+1]))
				swap(T.data[j+1], T.data[j]);
		printf("冒泡排序第%d趟结果:", i+1);
		for(j = 0; j < T.length; ++j)
			printf("%d ", T.data[j]);
		printf("\n");
	}
	printf("\n");
}
//简单选择排序
void select_sort(table T)
{
	int i, j, min;
	for(i = 0; i < T.length; ++i)
	{
		min =T.data[T.length-1];
		for(j = T.length-2; j >= 0; --j)
			if(min >= T.data[j])
				min = T.data[j];
			else
			{
				swap(T.data[j+1], T.data[j]);
				min = T.data[j];
			}
	}
	printf("简单选择排序后结果为:");
	for(j = 0; j < T.length; ++j)
		printf("%d ", T.data[j]);
	printf("\n\n");
}
//堆排序
void heapadjust(table &T, int k, int len)
{
	int a = T.data[k];
	for(int i = 2*k+1; i <= len-1; i = i*2+1)
	{
		if((i < len-1) && (T.data[i] < T.data[i+1]))
			++i;
		if(a >= T.data[i])
			break;
		else
		{
			T.data[k] = T.data[i];
			k = i;
		}
	}
	T.data[k] = a;
}

void heap_sort(table T)
{
	int i;
	for(i = (T.length/2-1); i >= 0; --i)
		heapadjust(T, i, T.length);
	for(i = T.length-1; i >= 1; --i)
	{
		swap(T.data[0], T.data[i]);
		heapadjust(T, 0, i);
	}
	printf("堆排序后结果为:");
	for(int j = 0; j < T.length; ++j)
		printf("%d ", T.data[j]);
	printf("\n\n");
}
//归并排序
void merge_sort(table &s, int left, int right)
{
	if(left + 1< right)
	{
		int p = left, q = right;
		int mid = (p + q)/2;
		merge_sort(s, left, mid);
		merge_sort(s, mid, right);
		int a[8];
		for(int t = 0; t < s.length; ++t)
			a[t] = s.data[t];
		int i = p, j = mid;
		for(int k = i; (i < mid) && (j < q); ++k)
			if(a[i] < a[j])
				s.data[k] = a[i++];
			else
				s.data[k] = a[j++];
		while(i < mid)
			s.data[k++] = a[i++];
		while(j < q)
			s.data[k++] = a[j++];
	}
}
//快速排序
void quick_sort(table &T, int left, int right)
{
	int p = left, q = right;
	if(p  > q)
		return;
	int k = T.data[p];
	while(p < q)
	{
		while((p < q) && (k <= T.data[q]))
			q--;
		if(p < q)
			T.data[p++] = T.data[q];
		while((p < q) && (k >= T.data[p]))
			p++;
		if(p < q)
			T.data[q--] = T.data[p];
	}
	T.data[p] = k;
	quick_sort(T, left, p-1);
	quick_sort(T, p+1, right);
}

示例:(读者可自行验证)

时间: 05-16

排序汇总的相关文章

基数排序-八大排序汇总(8)

基数排序的性能 排序类别 排序方法 时间复杂度 空间复杂度 稳定性 复杂性 平均情况 最坏情况 最好情况 基数排序 基数排序 O(d(n+r)) O(d(n+r)) O(d(n+r)) O(n+r) 稳定 较复杂 时间复杂度:假设在基数排序中,r为基数,d为位数.则基数排序的时间复杂度为O(d(n+r)).可以看出,基数排序的效率和初始序列是否有序没有关联. 空间复杂度:基数排序过程中,对于任何位数上的基数进行“装桶”操作时,都需要n+r个临时空间. 算法稳定性:基数排序过程中,每次都是将当前位

java排序集锦

java实现排序的一些方法,来自:http://www.javaeye.com/topic/548520 1 package sort; 2 3 import java.util.Random; 4 5 /** 6 * 排序测试类 7 * 8 * 排序算法的分类如下: 1.插入排序(直接插入排序.折半插入排序.希尔排序): 2.交换排序(冒泡泡排序.快速排序): 9 * 3.选择排序(直接选择排序.堆排序): 4.归并排序: 5.基数排序. 10 * 11 * 关于排序方法的选择: (1)若n较

《Python数据分析常用手册》一、NumPy和Pandas篇

一.常用链接: 1.Python官网:https://www.python.org/ 2.各种库的whl离线安装包:http://www.lfd.uci.edu/~gohlke/pythonlibs/#scikit-learn 3.数据分析常用库的离线安装包(pip+wheels)(百度云):http://pan.baidu.com/s/1dEMXbfN 密码:bbs2 二.常用库 1.NumPy NumPy是高性能科学计算和数据分析的基础包.部分功能如下: ndarray, 具有矢量算术运算和

iOS数组使用

相关链接: ios数组基本用法和排序 NSArray 排序汇总 iOS 数组排序方法 IOS-筛选数组内的元素 关于EnumerateObjectsUsingBlock和for-in之间的较量 [iOS开发技术]NSPredicate谓词的用法 数组过滤

[有向树的最小表示] poj 1635 Subway tree systems

题目链接: http://poj.org/problem?id=1635 Subway tree systems Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 6541   Accepted: 2747 Description Some major cities have subway systems in the form of a tree, i.e. between any pair of stations, th

SQL从入门到基础 - 04 SQLServer基础2(数据删除、数据检索、数据汇总、数据排序、通配符过滤、空值处理、多值匹配)

一.数据删除 1. 删除表中全部数据:Delete from T_Person. 2. Delete 只是删除数据,表还在,和Drop Table(数据和表全部删除)不同. 3. Delete 也可以带where子句来删除一部分数据:Delete from T_Person where FAge>20. 二.数据检索 1. 执行备注中的代码创建测试数据表. 2. 简单的数据检索:select *from T_Employee(*表示所有字段) 3. 只检索需要的列:select FNumber

若干排序算法简单汇总(一)

转载请注明出处 http://blog.csdn.net/pony_maggie/article/details/35819279 作者:小马 从题目看,首先不是全部是若干.排序算法很多,我个人的能力也有限,不可能都讲到.另外,是简单汇总,是希望能用最简单的代码,最简短的语言说明问题,不搞太多理论分析. 就像前面说的,排序算法有很多,而且不存在哪一种最不好,哪一种最好这样的说法.根据用途不同选择最适合的就行了.不过仅从时间复杂度来看,基本上有两种,一种是O(n^2), 一种是O(nlogn).

排序算法汇总总结_Java实现

一.插入排序 直接插入排序(Insertion Sort)的算法描述是一种简单直观的排序算法.它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入.插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间. 代码实现: public class Inseretion_Sort {     public static void main(Stri

若干排序算法简单汇总(二)

转载请注明出处 http://blog.csdn.net/pony_maggie/article/details/36706131 作者:小马 一希尔排序 上一篇讲到的直接插入排序,时间复杂度O(n^2). 请在脑海里想一下它的过程.如果一个序列本来就是有序的,对它排序的时间复杂度是O(n).所以当序列基本有序时,插入排序排序的效率大大提高,因为减少了移动的动作. 另外,直接插入排序还有一个特点,当n比较小时,它的效率比较高. 希尔排序正是基于上面两个思想做的一种改进算法.它先将整个序列分成若干