排序算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了排序算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含4343字,纯文字阅读大概需要7分钟。
内容图文
![排序算法](/upload/InfoBanner/zyjiaocheng/837/163c446ee37d46efaa7e614bddbb4f72.jpg)
常见算法的稳定性(要记住)
堆排序、快速排序、希尔排序、直接选择排序不是稳定的排序算法,而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。
稳定性的意义
1、如果只是简单的进行数字的排序,那么稳定性将毫无意义。
2、如果排序的内容仅仅是一个复杂对象的某一个数字属性,那么稳定性依旧将毫无意义(所谓的交换操作的开销已经算在算法的开销内了,如果嫌弃这种开销,不如换算法好了?)
3、如果要排序的内容是一个复杂对象的多个数字属性,但是其原本的初始顺序毫无意义,那么稳定性依旧将毫无意义。
4、除非要排序的内容是一个复杂对象的多个数字属性,且其原本的初始顺序存在意义,那么我们需要在二次排序的基础上保持原有排序的意义,才需要使用到稳定性的算法,例如要排序的内容是一组原本按照价格高低排序的对象,如今需要按照销量高低排序,使用稳定性算法,可以使得想同销量的对象依旧保持着价格高低的排序展现,只有销量不同的才会重新排序。(当然,如果需求不需要保持初始的排序意义,那么使用稳定性算法依旧将毫无意义)。
排序法 | 平均时间 | 最差情形 | 稳定度 | 额外空间 | 备注 |
冒泡 | O(n2) | O(n2) | 稳定 | O(1) | n小时较好 |
交换 | O(n2) | O(n2) | 不稳定 | O(1) | n小时较好 |
选择 | O(n2) | O(n2) | 不稳定 | O(1) | n小时较好 |
插入 | O(n2) | O(n2) | 稳定 | O(1) | 大部分已排序时较好 |
基数 | O(logRB) | O(logRB) | 稳定 | O(n) |
B是真数(0-9), R是基数(个十百) |
Shell | O(nlogn) | O(ns) 1<s<2 | 不稳定 | O(1) | s是所选分组 |
快速 | O(nlogn) | O(n2) | 不稳定 | O(nlogn) | n大时较好 |
归并 | O(nlogn) | O(nlogn) | 稳定 | O(1) | n大时较好 |
堆 | O(nlogn) | O(nlogn) | 不稳定 | O(1) | n大时较好 |
/*
*排序算法汇总(C/C++实现)
*/
#include <cstdio>
#include <cstring>
//#define swap(x,y){x^=y;y^=x;x^=y;}
#define swap(x,y){int temp=x;x=y;y=temp;}
const int N = 10;
void selectSort(int *a,int n){
for(int i=0;i<n;i++){
int min=i;
for(int j=i+1;j<n;j++){
if(a[j]<a[min]) min=j;
}
swap(a[i],a[min]);
}
}
//something error!
void bubbleSort(int *a,int n){
for(int i=0;i<n;i++){
for(int j=i;j<n;j++)
if(a[j]<a[i]) swap(a[i],a[j]);
}
}
void insertSort(int *a,int n){
for(int i=1;i<n;i++){
for(int j=i;j-1>=0&&a[j]<a[j-1];j--){
swap(a[j],a[j-1]);
}
}
}
void shellSort(int *a,int n){
//设定划分步长step
int step=3;
int h=1;
while(h*step<n) h=h*step + 1;
while(h>=1){
for(int i=1;i<n;i++){
for(int j=i;j-h>=0&&a[j]<a[j-h];j-=h)
swap(a[j],a[j-h]);
}
h /= step;
}
}
void mergeSort(int *a,int p,int q,int *T){
//[p,q)左闭右开
if(p+1>=q) return;
int m = p+(q-p)/2;
//printf("m=%d\n",m);
mergeSort(a,p,m,T);
mergeSort(a,m,q,T);
for(int i=p,x=p,y=m;i<q;){
if( x<m && y<q && a[x]<a[y] || y>=q) T[i++]=a[x++];
else T[i++]=a[y++];
}
for(int i=p;i<q;i++)
a[i] = T[i];
}
void qSort(int *a,int p,int q){
if(p>=q) return ;
int i=p-1;
for(int j=p;j<q;j++) if(a[j]<a[q]){
i=i+1;
swap(a[i],a[j]);
}
i=i+1;
swap(a[i],a[q]);
qSort(a,p,i-1);
qSort(a,i+1,q);
}
void sink(int *a,int n,int k){
while(2*k<=n){
int j=2*k;
if(j<n && a[j]<a[j+1]) j++;
//if(a[j]<a[j+1]) j=j+1;
if(a[k] > a[j]) break;
swap(a[j],a[k]);
k = j;
}
}
void heapSort(int *a,int n){
for(int k=n/2;k>=1;k--)
sink(a,n,k);
for(;n>1;){
swap(a[1],a[n]);
n--;
sink(a,n,1);
}
}
void pt(int *a,int s,int n){
for(int i=s;i<n;i++)
printf("%d ",a[i]);
printf("\n");
}
int main(){
//printf("Hello world!\n");
int a[N]={2,1,-1,123,0,1,21,7,-10,1};
int b[N+1]={-999,2,1,-1,123,0,1,21,7,-10,1};
int T[N];
int c;
printf("请选择一种排序算法:\n 1.选择排序\n 2.冒泡排序\n 3.插入排序\n 4.希尔排序\n 5.归并排序\n 6.快速排序\n 7.堆排序\n ----> ");
scanf("%d",&c);
switch(c){
case 1:
selectSort(a,N);
break;
case 2:
bubbleSort(a,N);
break;
case 3:
insertSort(a,N);
break;
case 4:
shellSort(a,N);
break;
case 5:
mergeSort(a,0,N,T);
break;
case 6:
qSort(a,0,N-1);
break;
case 7:
heapSort(b,N);
break;
default:
printf("选择无效!");
return 1;
}
printf("输出结果:\n");
if(c==7)
pt(b,1,N+1);
else
pt(a,0,N);
return 0;
}
内容总结
以上是互联网集市为您收集整理的排序算法全部内容,希望文章能够帮你解决排序算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。