nbhkdz.com冰点文库

c++9中排序算法解释及代码

时间:2017-10-12

9 个排序算法 1. 计数排序
int a[1005]={0};//数值范围的大小 int main(){ int i,n,j,x; scanf("%d",&n); for(i=0;i<n;i++){ scanf("%d",&x); a[x]++;//统计每个数值出现的次数 } for(i=0;i<=1000;i++) for(j=1;j<=a[i];j++) printf("%d ",i); puts(""); return 0; } 复杂度最低的排序算法,稳定排序,O(n+m),n 为元素个数,m 为数值范围。

2. 选择排序
int num[1005]; int main(){ int n,i,j,k,t; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&num[i]); for(i=1;i<=n;i++){ k=i; for(j=i+1;j<=n;j++)//在[i+1,n]的范围找到最小值的下标 if(num[j]<num[k])k=j; if(k!=i){//第 i 个数与最小值交换 t=num[i];num[i]=num[k];num[k]=t; } } for(i=1;i<=n;i++) printf("%d ",num[i]); puts(""); return 0; } 复杂度为 O(n^2),是不稳定的排序算法,可用“5 5 2”模拟。

3. 冒泡排序
int a[20005]; int main(){ int n,i,j,t; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&a[i]); for(i=1;i<n;i++){ int f=1; //第 i 次冒泡时,判断[1,n-i]内每个数与它后面的数 for(j=1;j<=n-i;j++) if(a[j]>a[j+1]){ t=a[j]; a[j]=a[j+1]; a[j+1]=t; f=0;//发生了冒泡 } if(f)break;//如果没有发生冒泡,说明已经有序,可结束。 } for(i=1;i<=n;i++) printf("%d ",a[i]); puts(""); return 0; } 稳定排序,复杂度 O(n^2),最好情况下 O(n),冒泡排序发生的交换次数等于逆序对数。

4. 插入排序
int a[20005]; int main(){ int n,i,j,x; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&a[i]); for(i=1;i<=n;i++){ x=a[i]; //[1,i-1]已经有序,把 x 插入进去 for(j=i-1;j>0&&x<a[j];j--) a[j+1]=a[j];//比 x 大的数往后挪 a[j+1]=x;//插入 x } for(i=1;i<=n;i++) printf("%d ",a[i]); puts(""); return 0; } 稳定的排序算法,平均为 O(n^2),最好 O(n)。

5. 基数排序
int s[10][20005],A[20005]; int main(){ int n,i,j,k; scanf("%d",&n); for(i=0;i<n;i++)scanf("%d",&A[i]); int len[10],d=1; for(i=0;i<10;i++){ for(j=0;j<10;j++)len[j]=0; for(j=0;j<n;j++){ k=A[j]/d%10;//第 i 位上的数值 s[k][len[k]++]=A[j]; } int m=0; for(j=0;j<10;j++){//按第 i 位依次排序 for(k=0;k<len[j];k++) A[m++]=s[j][k]; } d*=10;//继续判断下一位 } for(i=0;i<n;i++)printf("%d ",A[i]); puts(""); return 0; } 稳定排序算法,复杂度(n*m),m 为最长数位长度,注意数值需要是非负的,如果数据中有 负数可以都加上一个很大的值。 初始数组:105 46301 124 2 12 1125 2054 55505 100 按倒数第 1 位: 46301 2 12 124 2054 105 1125 55505 按倒数第 2 位: 46301 2 105 55505 12 124 1125 2054 按倒数第 3 位: 2 12 2054 105 124 1125 46301 55505 按倒数第 4 位: 2 12 105 124 1125 2054 55505 46301 按倒数第 5 位: 2 12 105 124 1125 2054 46301 55505

6. 归并排序
合并有序序列的复杂度可以做到 O(a+b),a 和 b 表示两个有序序列的长度。可以将待排序的 数组划分成两个序列,将这两个序列排序后,再进行合并。这是一个递归过程,一直递归的 序列的长度为 1,就可以返回了。合并,返回,直到最初那层。共 logn 层,每层向上合并的 复杂度是 O(n),总的复杂度是 O(nlogn)。

#define M 200005 int A[M],B[M]; long long cnt=0;//统计逆序对数 void Merge(int L,int R){//在 main 函数中调用 Merge(1,n); if(L==R)return;//序列长度为 1,叶子节点 int mid=(L+R)/2; Merge(L,mid); //递归排序左边 Merge(mid+1,R);//递归排序右变 int i=L,j=mid+1,k=L;//合并[L,mid]和[mid+1,R]这两个有序序列 //先把合并结果放到 B 数组的[L,R] while(i<=mid&&j<=R){ if(A[i]<=A[j])B[k++]=A[i++]; else{ B[k++]=A[j++]; cnt+=mid-i+1;//A[j]比左边[i,mid]这个区间的数都小,产生逆序对 } } while(i<=mid)B[k++]=A[i++]; while(j<=R)B[k++]=A[j++]; for(k=L;k<=R;k++)A[k]=B[k];//赋值回 A 数组 } 稳定的排序算法,可以用来统计逆序对数。

7. 快速排序
基本思想是:首先任意选取一个数据(通常选用数组的第一个数)作为关键数据,然后将所 有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。 然后再递归对这两部分进行排序。

#define M 200005 int s[M]; void sort(int L,int R){//在 main 函数中调用 sort(1,n) int low=L,high=R; int key=s[low]; while(low<high){ while(low<high&&key<=s[high])high--;//滑动右边指针 if(low<high)s[low]=s[high]; while(low<high&&key>=s[low])low++;//滑动右边指针 if(low<high)s[high]=s[low]; } s[low]=key;//此时 low 与 high 相同 if(L<low-1)sort(L,low-1);//递归排序左区间 if(low+1<R)sort(low+1,R);//递归排序右区间 } 不稳定的排序,平均复杂度是 O(nlogn),最坏情况 O(n^2)(有序数组) 。 扩展用法:求序列中第 K 大数。

8. 希尔排序
希尔排序是把记录按下标的一定增量分组, 对每组使用直接插入排序算法排序; 随着增量逐 渐减少,每组包含的关键词越来越多,当增量减至 1 时,整个文件恰被分成一组,算法便终 止。

int A[200005]; int main(){ int n,i,j,k,step,tmp; scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&A[i]); for(step=n/2;step>0;step/=2){//增量 for(i=step;i<n;i++){ if(A[i]<A[i-step]){ tmp=A[i];k=i-step; while(k>=0&&A[k]>tmp){ A[k+step]=A[k]; k-=step; } A[k+step]=tmp; } } } for(i=0;i<n;i++) printf("%d ",A[i]); return 0; }
不稳定的排序算法,复杂度存在争议,下限是 O(nlogn),平均 O(n^1.5)

9. 堆排序
堆得定义: 一个长度为 n 的数组 A,下标 1,2,3,….,n-2,n-1,n。 如果对于在[1,n/2]范围内的 i,有 A[i]<=A[i*2]且 A[i]<=A[i*2+1],则称为小顶堆。 如果对于在[1,n/2]范围内的 i,有 A[i]>=A[i*2]且 A[i]>=A[i*2+1],则称为大顶堆。 如果要将数组从小到大排序,则需要维护小顶堆。每次取出堆顶元素,再删除,一直维护小 顶堆。

向下调整过程,可以用一个 down()函数来完成。 void swap(int &a,int &b){//交换两个数 int t=a;a=b;b=t; } void down(int k){ while(2*k<=sz){ int a=2*k; if(a+1<=sz&&heap[a]>heap[a+1])a++;//找较小的儿子 if(heap[k]>heap[a])swap(heap[k],heap[a]);//交换 else break; k=a;//往下走 } } 初始化堆得时候,可以把 n/2 到 1 的每个元素都 down 下。 int heap[200005],sz;//sz 记录当前堆得大小,也是最后一个元素的下标 int main(){ int i,j,k,n; scanf("%d",&n); sz=n; for(i=1;i<=n;i++) scanf("%d",&heap[i]); for(i=n/2;i>=1;i--) down(i);//初始化堆 for(i=1;i<=n;i++){ printf("%d ",heap[1]); heap[1]=heap[sz--];//用最后一个元素覆盖堆顶,在删除最后一个元素 down(1);//调整堆 } return 0; } 堆也可以添加元素,原理 down 类似,用 up,把数字添加在 heap[++sz]的位置上。 如果父亲节点比当前元素小,就不断向上。 void up(int k){ while(k>1){ int a=k/2;//a 是父亲节点 if(heap[a]>heap[k])swap(heap[k],heap[a]); else break; k=a; } } 每次向上和向下都是 logn,通过堆实现排序,复杂度是 O(nlogn),不稳定, “1 2 2”可以说 明,删除 1 后,第二个 2 被赋值到堆顶,下次出来。 因此堆可以添加元素,并维护最大值,删除最大值,在很多贪心问题上,可以用到。


c++9中排序算法解释及代码.doc

c++9中排序算法解释及代码 - 9 个排序算法 1. 计数排序 int a[1

C++ 八种排序算法总结及实现.doc

C++ 八种排序算法总结及实现 - 八种排序算法总结之 C++版本 版本 五种简单排序算法 一、 冒泡排序 【稳定的】 稳定的】 void BubbleSort( int* a,int Coun....

C++程序中各种排序实现详细讲解_图文.ppt

C++程序中各种排序实现详细讲解_教学计划_教学研究_...? 移动次数为:3(n-1) 9 2、选择排序 ? 上述...{// 利用堆排序算法对a[1:n] 进行排序 // ...

数据结构(C++版)第9章 排序-1_图文.ppt

数据结构(C++版)第9章 排序-1 - 第9章 排序 第6章 树与二叉树 第1讲 1 第9章 排序 排序是一种重要运算,在很多领域中有广泛 的应用。排序的方法很多,...

C++各种排序代码 - 百度文库.txt

C语言中排序程序代码参考... 6页 快速排序代码-c语言 1页 排序 算法设计与说明 C程... 5页 喜欢此文档的还喜欢 各种排序C++实现代码 2页 排序算法...

C++各类排序算法介绍_1018_图文.ppt

C++各类排序算法介绍_1018_计算机软件及应用_IT/计算机_专业资料。9.

C++排序算法简介与总结 - 百度文库.txt

C++排序算法简介与总结。专业文档 专业文档是百度文库认证用户/机构上传的专业性...主程序中直接调用sort(a+1,a+n+1,cmp); 完整代码如下: #include<iostrea...

C++排序算法全集.doc

C++排序算法全集_计算机软件及应用_IT/计算机_专业...在代码的后面给出了

数据结构中常见的8种排序算法的C++代码实现.doc

数据结构中常见的8种排序算法C++代码实现_IT/...9/29 //学校:C

合并排序算法的C++实现代码.doc

标签: 计算机软件及应用| 算法| 代码|合并排序算法C++实现代码_计算机软件及应用_IT/计算机_专业资料。合并排序算法-用数组表示的实现算法 ...

C++各种排序算法.pdf

各种内排序算法C++实现(不断更新中)分类: C/C++学习笔记 2010-09-28 14:18 7117 人阅读 评论(10) 收藏 举报 算法 c++sorting 数据结构 mergepivot 和...

c++常见排序算法.doc

c++常见排序算法_工学_高等教育_教育专区。哈工大软设,实现各种排序及排序之间

设计排序典型算法(冒泡与快速排序),C++课程设计_图文.pdf

设计排序典型算法(冒泡与快速排序),C++课程设计_...冒泡法和快速排序法对比 9.参考文献 14 1.课程...课程设计成果★ 程序源代码: #include <iostream.h...

C++程序设计 冒泡排序法_讲解.doc

C++程序设计 冒泡排序法_讲解_计算机软件及应用_IT/...次就可以了;有 10 个 元素的时候,冒泡 9 次就...这个问题,在程序代码中,有很好的体现。请认真 看...

C++八大排序算法.doc

C++八大排序算法 - 插入排序 1.直接插入排序 原理: 将数组分为无序区和有

c++排序算法.doc

c++排序算法 - 当 n 较大,则应采用时间复杂度为 O(nlog2n)的排序

数据结构C++版实现各种排序算法语句.doc

数据结构C++版实现各种排序算法语句_计算机软件及应用_IT/计算机_专业资料。

C++程序中各种排序实现详解_图文.ppt

C++程序中各种排序实现详解_IT/计算机_专业资料。...移动次数为:3(n-1) 9 2、选择排序上述程序中...(n-1)/2 比较 移动 19 4、插入排序算法设计: ...

C++常用算法经典代码.doc

C++常用算法经典代码 隐藏>> 一、快速排序 void qsort(int x,int y) //待...后序遍历 void preorder(int x)//二叉树的先序遍历 { if(x==0) ...

快速排序与归并排序算法及时间复杂度分析(C++).doc

快速排序归并排序算法及时间复杂度分析(C++)_IT/计算机_专业资料。归并排序与...(大于 700): 归并排序:(代码) #include <iostream> #include using namespace...