排序大法

关于学习排序相关知识点总结：

　　一方面用于巩固，另一方面也是对自己的一个检测。

　　代码纯手敲，自己检验了下，结果也都正确。

　　弱鸡一只，只能叫，不能跑。如果有错误，或者建议，希望大佬斧正指点。

~~~首先当然是冒泡了，其实冒泡排序应该叫沉底排序，但是当时发明冒泡排序的人可能不会沉底这个英语单词，就这能冒泡了吧！这渣渣的英语水平和我差不多，哈哈哈哈。。。

废话不说，直接上代码：

#include
//#include
using namespace std; const int MAXN=1010; int a[MAXN]; void BubbleSort(int a[], int n) { for(int i=1; ifor( int j=n; j>=1; j-- ){ if(a[j-1]>a[j]){ int k=a[j-1]; a[j-1]=a[j]; a[j]=k; } } } } int main() { int n; scanf("%d",&n); for( int i=1; i<=n; i++ ){ scanf("%d",&a[i]); } BubbleSort(a,n); for( int i=1; i<=n; i++){ printf("%d%c",a[i],i==n?'\n':' '); } return 0; }
废话不多说了，选择排序一起出来吧！！！

#include
//#include
using namespace std; const int MAXN=1010; int a[MAXN]; void SelectSort(int a[], int n) { for(int i=1; iint flag=i;//设立哨兵 for( int j=i+1; j<=n; j++ ){ if(a[j]if(flag!=i){ int k =a[i]; a[i]=a[flag]; a[flag]=k; } } } int main() { int n; scanf("%d",&n); for( int i=1; i<=n; i++ ){ scanf("%d",&a[i]); } SelectSort(a,n); for( int i=1; i<=n; i++){ printf("%d%c",a[i],i==n?'\n':' '); } return 0; }

　　接下来说说归并排序，个人感觉，归并还是非常牛逼的一个排序方法

　　他的最好最坏时间复杂度都是O(nlogn),空间复杂度是O(n),还TM稳定。这就是排序比排序，气死排序。

　　归并排序：是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。

　　将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并

#include
using namespace std; const int MAXN=1010; int num[MAXN]; void merge(int a[], int first, int mid, int last)//归并有序代码段 { int i=first,j=mid+1,m=mid,n=last; int l=m-i; int k=0; int temp[MAXN]; while(i<=m&&j<=n){ if(a[i]else{ temp[k++]=a[j++]; } } while(i<=m){ temp[k++]=a[i++]; } while(j<=m){ temp[k++]=a[j++]; } for( int i=0; ivoid mergesort(int a[], int first, int last)//分段有序代码段 { if(firstint mid=(first+last)/2; mergesort(a,first,mid);//左边有序 mergesort(a,mid+1,last);//右边有序 merge(a,first,mid,last);//合并有序 } } int main() { int n; scanf("%d",&n); for( int i=1; i<=n; i++ ){ scanf("%d",&num[i]); } mergesort(num,1,n); for( int i=1; i<=n; i++ ){ printf("%d%c",num[i],i==n?'\n':' '); } return 0; }

 另外说说希尔排序，原来我一直一位希尔排序也叫哈希排序，就像一个人的小名似的，但是现实往往是残酷的，Oh，Mygod!

希尔排序：该方法实质上是一种分组插入方法 比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比[2] 较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。 一般的初次取序列的一半为增量，以后每次减半，直到增量为1。 给定实例的shell排序的排序过程 假设待排序文件有10个记录，其关键字分别是： 49，38，65，97，76，13，27，49，55，04。 增量序列的取值依次为： 5，3，1

#include
#include
using namespace std;
const int MAXN=101; int num[MAXN]; void shell_sort(int *data,int len) { if(len<1||data==NULL){ return ; } // for( int div=len/2; div>=1; div=div/2)//定量div // { // for( int i=0; i<=div; i++ ){//分成div组 // for(int j=i;jdiv;j+=div) //对每组进行插入排序 // for(int k=j;kdiv) // if(data[j]>data[k]) // swap(*(data+j),*(data+k)); //交换两个数的值 // } // } int div=len/2; do{ for( int i=0; i<=div; i++ ){//分成div组 for( int j=i;jdiv; j+=div ){//对每组进行div排序 for( int k=j; kdiv ){ if(data[j]>data[k]){ swap(*(data+j),*(data+k)); } } } } div=div/2; }while(div>=1); } int main() { int n; scanf("%d",&n); for( int i=0; i"%d",&num[i]); } shell_sort(num,n); for( int i=0; i"%d%c",num[i],i==n-1?'\n':' '); } return 0; } 

 接下来说说快排，总体来说，快排还是很不错的排序，只不过他有一点臭毛病，有时候很快，有时候是真的慢，或许还赶不上冒泡，平均时间复杂度O(nlogn),这个还是不错的，不稳定,另外说说他的臭毛病，正序和逆序的时候他的臭毛病就出来了，时间复杂度都O(n^2)了，有辅助栈，空间复杂度最坏为O(n),值得一提的是，在快排时枢纽的选择直接影响快排的效率，当选择枢纽为素数时性能会更好。

上代码：

#include
//#include
using namespace std; const int MAXN=1010; int a[MAXN]; void QuickSort(int first, int last) { int i=first,j=last,temp; if(first>last){ return ; } temp=a[first];//temp存储基准枢纽 while(iwhile(a[j]>=temp&&i//先找右边的 j--; } while(a[i]<=temp&&i//在找左边的 i++; } if(iint k=a[i]; a[i]=a[j]; a[j]=k; } } a[first]=a[i]; a[i]=temp; QuickSort(first,i-1); QuickSort(i+1,last); } int main() { int n; scanf("%d",&n); for( int i=1; i<=n; i++ ){ scanf("%d",&a[i]); } QuickSort(1,n); for( int i=1; i<=n; i++){ printf("%d%c",a[i],i==n?'\n':' '); } return 0; }
关于堆排序：这涉及到一些堆的知识，像最大堆，最小堆，大家可以自己百度下。。。
啊啊啊啊，你们都会，就我不会，让我伤心一会。
这个代码是当时做PTA遇到的一道题，就像用堆排序跑一边，
于是查阅了各种资料，改了无数的bug,才写出来，至今印象深刻啊！！！

#include
using namespace std; #define MAXSIZE 100010 typedef long ElementType; typedef struct TNode *Position; typedef Position BinTree; struct TNode { ElementType Data; BinTree Left; BinTree Right; }; BinTree Insert(BinTree,ElementType); void InorderTraversal(BinTree); int main(){ int n; scanf("%d",&n); BinTree B=NULL; long num; for(int i=0;iscanf("%ld",&num); B=Insert(B,num); } InorderTraversal(B); return 0; } BinTree Insert( BinTree BST, ElementType X ) { //二分生长树 BinTree NewT=(BinTree)malloc(sizeof(struct TNode)); NewT->Data=X; NewT->Left=NULL; NewT->Right=NULL; BinTree head=BST; while(BST) { if(BST->Data>=X) { if(BST->Left)BST=BST->Left; else {//相同的树将其插入左子树，为左子树的最右结点 BST->Left=NewT; return head; } } else { if(BST->Right)BST=BST->Right; else { BST->Right=NewT; return head; } } } return NewT;//若为空树 则新建 } void InorderTraversal( BinTree BT ) { static char flag=0; if(BT) { InorderTraversal(BT->Left); if(flag)printf(" ");else flag=1; printf("%d",BT->Data); InorderTraversal(BT->Right); } }
下面总结一下：

直接插入排序正序时最好时间复杂度O(n),逆序最坏O(n2),平均O(n2)，空间复杂度O(1)；稳定；原始序列基本有序时该方法好

折半插入排序T(n)=O(n2),原本有序无序均如此,最好O(NLogN) S(n)=O(1);稳定

希尔排序(缩小增量排序):平均时间复杂度O(n1.x),S(n)=O(1);不稳定

冒泡排序(改进)正序时间复杂度最好O(n),逆序最坏O(n2),平均O(n2),S(n)=O(1); 稳定

快速排序平均时间复杂度O(nlogn),平均性能最优,正序或逆序最坏O(n2), 有辅助栈,空间复杂度最坏O(n),平均O(logn);不稳定. 枢轴改进

选择排序复杂度T(n)=O(n2),原本有序无序均如此,S(n)=O(1);稳定

堆排序T(n)=O(nlogn),S(n)=O(1);不稳定（因为间隔着比和移动）

归并排序最好最坏复杂度为O(nlogn),空间复杂度O(n),稳定

链式基数排序最好最坏时间复杂度为O(d*(n+ rd )),空间O(rd),稳定

内部排序方法分类：复杂度O(n2)的简单排序方法，O(nlogn)的高效排序方法(比较法的理论下界)，O(d*(n+rd))的基数排序方法.

在学习排序这一章的时候，印象很深刻，也悟出了一个道理，思想啊 ，思想很重要，学习就是学习思想的过程，只要思想理解了，代码就好敲了，脑海中的印象也深

，更不容易忘。

题后话：如果有人能够光临寒舍，看到我的这一篇开头博客，哈哈哈，大家一定要给我指点一下哈，哇，谢大佬！！！

有些目标看似很遥远，但只要付出足够多的努力，这一切总有可能实现！！！拜托诸位，为了不辜负以前经历过的困难，为了自己的努力，也为了将来遇见更好的自己，请坚守自己的初心！！！

转载于:https://www.cnblogs.com/Bravewtz/p/10041029.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！