时间戳

首页 > 技术文章 > 排序大法

排序大法

Bravewtz 2018-11-29 21:36 原文

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

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

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

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

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

废话不说，直接上代码：

#include<bits/stdc++.h>
//#include<cstdio>
using namespace std;
const int MAXN=1010;
int a[MAXN];

void BubbleSort(int a[], int n)
{
    for(int i=1; i<n; i++ ){
        for( 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<bits/stdc++.h>
//#include<cstdio>
using namespace std;
const int MAXN=1010;
int a[MAXN];

void SelectSort(int a[], int n)
{
    for(int i=1; i<n; i++ ){
        int flag=i;//设立哨兵
        for( int j=i+1; j<=n; j++  ){
            if(a[j]<a[i]){
                flag=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<bits/stdc++.h>
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]<a[j]){
            temp[k++]=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; i<k; i++ ){
        a[first+i]=temp[i];
    }
}
void mergesort(int a[], int first, int last)//分段有序代码段
{
    if(first<last){
        int 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<iostream>
#include<cstdio>
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;j<len-div;j+=div) //对每组进行插入排序
//            for(int k=j;k<len;k+=div)
//            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;j<len-div; j+=div ){//对每组进行div排序
                for( int k=j; k<len; k+=div ){
                    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<n; i++ ){
        scanf("%d",&num[i]);
    }
    shell_sort(num,n);
    for( int i=0; i<n; i++ )
    {
        printf("%d%c",num[i],i==n-1?'\n':' ');
    }
    return 0;
}

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

上代码：

#include<bits/stdc++.h>
//#include<cstdio>
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(i<j){
        while(a[j]>=temp&&i<j){//先找右边的
            j--;
        }
        while(a[i]<=temp&&i<j){//在找左边的
            i++;
        }
        if(i<j){
            int 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<bits/stdc++.h>
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;i<n;i++){
    scanf("%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))的基数排序方法.

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

，更不容易忘。

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

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

推荐阅读