九种排序算法_归并排序适用于链式存储吗

一：插入排序

①直接插入排序

//以从小到大排序为例
void InsertSort(int a[],int len)
{
    int i;
    for(i=1;i<len;i++)
    {
        if(a[i]<a[i-1])
        {
            int temp=a[i];//哨兵，保存将要插入的值
            int j;
            for(j=i-1;a[j]>a[i];j--)
                a[j+1]=a[j];
            //移动，耗时最长
            a[j+1]=temp;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

直接插入排序最好的情况就是不需要移动，直接就是一个从大到小排好的顺序，那么就只需要比较一遍就可以了（不需要移动<交换>），时间复杂度为O（n），最差的情况下需要全部移动一遍，就是按照从小到大的顺序排的，那么，时间复杂度为O（n²），空间复杂度为O（1），因为只需要一个数据存储要插入的数据即可，是一个稳定的排序算法，链式存储也可以用，比较适合基本有序的数据。

②折半插入排序

#include<iostream>
using namespace std;

void BInsertSort(int a[],int len) 
{   
    int i;
    for(i=1;i<len;i++)
    {
        int temp=a[i];
        int low=0;
        int high=i-1;
        while(low<=high)
        {
            int mid=(low+high)/2;
            if(a[i]>a[mid])
                low=mid+1;
            else
                //if(a[i]<a[mid])
                    high=mid-1;
        }
        //cout<<low<<" "<<high<<" "<<a[i]<<endl;
        int j;
        for(j=i-1;j>=high+1;j--)
            a[j+1]=a[j];
        a[high+1]=temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

折半插入比较的时间不依赖于初始数据顺序，是一个固定的值，所以平均来看较直接插入排序减少了，但是在初始数据基本有序的时候，还是直接插入比较的次数少。
折半插入并没有缩减移动的次数，与直接插入一致，移动的次数依赖于初始数据的顺序。所以折半插入排序的时间复杂为****O（n²）。
折半插入排序是一种稳定的算法，因为涉及到折半，所以不适合链式存储结构。
比较适合n比较大，原始数据无序。
空间复杂度O（1）。

③希尔排序算法

void ShellInsert(int a[],int dk,int len)
{
    int i;
    for(i=dk;i<len;i++)
    {
        if(a[i]<a[i-dk])
        {
            int temp=a[i];
            int j;
            for(j=i-dk;j>=0&&a[j]>temp;j-=dk)
                a[j+dk]=a[j];
            a[j+dk]=temp;
        }
    } 
}

int dk[]={5,3,1};

void ShellSort(int a[],int dt[],int t,int len)
{
    int k;
    for(k=0;k<t;k++)
        ShellInsert(a,dt[k],len);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

希尔排序的要有一个“直接插入函数”，一个计量步长的数组，一个函数控制希尔排序。
因为直接插入排序法在初始序列基本有序的时候会有很好的效果，所以希尔排序就先“粗略”排序，以达到初始序列基本有序的效果，步长必须包括1且彼此之间互质。
希尔插入其实就是在步长的控制下，把原始序列中的几个数挑出来。
时间复杂度不清楚，大概n的1.3次方，空间复杂度为O（1），不适合链式排序，适合数据量大，无序的时候。

二：交换排序

①冒泡排序

void BubbleSort(int a[],int len)
{
    int i,j,flag=1;
    for(i=0;i<len-1&&flag;i++)
    {
        flag=0;
        for(j=0;j<len-1-i;j++)
        {
            if(a[j]>a[j+1])
            {
                flag=1;
                int temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

冒泡排序的想法就是每次换过去一个（未排序中的）最大的，然后直到不需要换。
这个比我大一写的冒泡排序多了一个flag变量，如果一趟排序下来没有移动元素，那就不用下一趟排序了，机智！
时间复杂度是O（n²），空间复杂度是O（1），适合于链式存储结构，移动次数太多，算法效率不高。

②快速排序

int Partition(int a[],int low,int high)
{
    int temp=a[low]; 
    while(low<high)
    {
        while(low<high&&a[high]>=temp)
            high--;
        a[low]=a[high];
        while(low<high&&a[low]<=temp)
            low++;
        a[high]=a[low];
    }
    a[low]=temp;
    return low; 
} 

void QSort(int a[],int low,int high)
{
    if(low<high)
    {
        int partition=Partition(a,low,high);
        QSort(a,low,partition-1);
        QSort(a,partition+1,high);
    }   
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

快排排序依次排序可以消除多个逆序，快排的时间复杂度为O（nlog2n），空间复杂度因为用了递归，执行时需要一个栈来存储数据，所以最好的情况下是O（log2n），最坏的情况下为O（n）。
属于不稳定的排序算法，不适合于链式存储结构。

三：选择排序

①简单选择排序

void SelectSort(int a[],int len)
{
    int i,j;
    for(i=0;i<len-1;i++)
    {
        int minn=i;
        for(j=i+1;j<len;j++)
        {
            if(a[j]<a[minn])
            minn=j;
        }
        if(minn!=i)
        {
            int temp=a[i];
            a[i]=a[minn];
            a[minn]=temp;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

简单选择排序就是每一趟找出最小的一个，换到合适的位置上！简单选择排序主要是比较用的时间多，所以时间复杂度为O（n²），空间复杂度为O（1）。
稳定排序（也可以不稳定），可用于链式存储结构。

②树形选择排序

树形选择排序又称锦标赛排序，比如8个人比赛，选出前三名，最少需要比11次。

③堆排序

void HeapAdjust(int a[],int s,int m)
{
    int rc=a[s];
    int j;
    for(j=2*s;j<=m;j*=2)
    {
        if(j<m&&a[j]<a[j+1])
            j++;
        if(rc>=a[j])
            break;
        a[s]=a[j];
        s=j;
    }
    a[s]=rc;
}

void CreatHeap(int a[],int len)
{
    int i;
    for(i=(len-1)/2;i>=0;i--)
        HeapAdjust(a,i,len-1);
}

void HeapSort(int a[],int len)
{
    CreatHeap(a,len);
    int i;
    for(i=len-1;i>0;i--)
    {
        int x=a[0];
        a[0]=a[i];
        a[i]=x;
        HeapAdjust(a,0,i-1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

堆排序是建立在完全二叉树的基础上的，但其实是一个线性表存储的，主要有两个函数，调整堆和建堆，其实核心就是调整堆。
先把一个无序的序列建成大根堆，然后固定一个最大的，然后把剩下的再调整为一个大根堆，在固定一次。
调整堆就是从第一个非叶子结点开始，向下寻找，找到大的那个就换。

堆排序的时间复杂度O（nlog2n），空间复杂度O（1）。

四：归并排序
归并排序时间复杂度为O（nlog2n），空间复杂度O（n）