代码语言
.
CSharp
.
JS
Java
Asp.Net
C
MSSQL
PHP
Css
PLSQL
Python
Shell
EBS
ASP
Perl
ObjC
VB.Net
VBS
MYSQL
GO
Delphi
AS
DB2
Domino
Rails
ActionScript
Scala
代码分类
文件
系统
字符串
数据库
网络相关
图形/GUI
多媒体
算法
游戏
Jquery
Extjs
Android
HTML5
菜单
网页交互
WinForm
控件
企业应用
安全与加密
脚本/批处理
开放平台
其它
【
C
】
常用排序算法
作者:
罗南山
/ 发布于
2014/4/8
/
547
//常用的排序算法包括直接插入排序法、shell排序法、冒泡法、快速排序、直接选择排序。本博客将对他们的基本思想,c/c++描述、以及时间复杂度和空间复杂度进行讨论和概括。程序经过测试,没有发现错误。 //讨论用各种方法对数据进行排序 #include<iostream> using namespace std; //1.插入排序 //1.1直接插入排序 基本思想:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列中的适当位置,直到全部记录插入完成为止。 //时间复杂度:最好O(n),平均和最坏O(n^2) //空间复杂度: void InsSort(int a[],int n) { int i,j,k; for (i=1;i<n;i++) { for(j=i-1;j>=0;j--) { if(a[i]>=a[j])//为a[i]找合适的位置。 break; } if (j != i - 1) //如找到了一个合适的位置。 { //如果j=i-1,则不用移动。 //将比a[i]大的数据向后移 int temp = a[i]; for (k = i - 1; k > j; k--) a[k + 1] = a[k]; //将a[i]放到正确位置上 a[k + 1] = temp; } } } //1.2希尔排序 基本思想:按增量d划分为若干组,再对每组用直接增量法进行排序。 //时间复杂度:O(nlog n) 空间复杂度:O(1) void ShellSort(int a[],int n) { int d, i, j, temp; for(d=n/2;d>0;d/=2) //设定步长d. { for(i=d;i<n;++i) //在元素间移动为止 for(j=i-d;j>=0&&a[j]>a[j+d];j-=d) //j=i-d只是初始条件。比较相距d的元素,逆序互换 { temp=a[j]; //后面元素比前面元素大时需要交换。 a[j]=a[j+d]; a[j+d]=temp; } } } //2.交换排序 //2.1冒泡排序 基本思想:对n个记录的序列,进行n-1次扫描。每次扫描时,都从小到大对相邻的两个关键字进行比较,第一次扫描把最大者置尾,第二次次大者…… //如果不符合由小到大的顺序,就交换他们的位置。 //时间复杂度: 最好O(n),最坏O(n^2),平均O(O^2) 空间复杂度:O(1) void BubbleSort(int a[],int n) { int i,j,temp; for(i=1;i<n;i++)//对序列进行n-1次扫描。 { for(j=0;j<n-i;j++)//减少循环次数。 { if(a[j]>a[j+1]) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } } } //2.2快速排序 基本思想是:先从数列中取出一个数作为基准数。 //分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。 //再对左右区间重复第二步,直到各区间只有一个数。 //时间复杂度:最坏O(n^2),平均O(nlog2N) 空间复杂度:nlog void QuickSort(int a[],int t,int n) { //挖坑填数 int x=a[t];//将a[t]作为基准。 int i=t,j=n-1,l; while(i<j) { while(i<j&&a[j]>=x)//从数组的最右面开始,找出比x小的元素去填坑。 j--; if(i<j) { a[i]=a[j]; i++;//a[j]放入a[i]中后,a[j]就形成了一个坑。 } while(i<j&&a[i]<x)//从数组的最左面开始,找出比x大的数。 i++; if(i<j) { a[j]=a[i];//a[i]形成了一个坑。 j--; } //退出循环是i=j; a[i]=x;//将基准放入坑。 //接下来分而治之 l=i; QuickSort(a,0,l-1); QuickSort(a,l+1,n); } } void main() { int a[19]={2,1,7,5,4,7,3,1,8,46,43,34,45,57,12,8,5,4,3}; /*InsSort(a,19);*/ /*ShellSort(a,19);*/ /*BubbleSort(a,19);*/ QuickSort(a,0,19); for(int i=0;i<19;i++) cout<<a[i]<<'\t'; }
试试其它关键字
排序算法
同语言下
.
获取手机通讯录 iOS去除数字以外的所有字符
.
异步加载音乐等资源
.
交通罚单管理系统
.
freemark实现,简单的替换
.
计算斐波那契数列
.
base64解码 包括解码长度
.
图像显示
.
冒泡排序
.
输入十进制数,输出指定进制
.
链式栈
可能有用的
.
C#实现的html内容截取
.
List 切割成几份 工具类
.
SQL查询 多列合并成一行用逗号隔开
.
一行一行读取txt的内容
.
C#动态修改文件夹名称(FSO实现,不移动文件)
.
c# 移动文件或文件夹
.
c#图片添加水印
.
Java PDF转换成图片并输出给前台展示
.
网站后台修改图片尺寸代码
.
处理大图片在缩略图时的展示
罗南山
贡献的其它代码
(
1
)
.
常用排序算法
Copyright © 2004 - 2024 dezai.cn. All Rights Reserved
站长博客
粤ICP备13059550号-3