排序

1.直接插入排序(straight insertion sort)
思想:第一趟比較前兩個數,然後把第二個數按大小插入到有序表中;
第二趟對前兩個數從後向前掃描,把第三個數按大小插入到有序表中;依次進行下去,進行(n-1)趟掃描
以後就完成了整個排序過程
屬於穩定的排序,最壞時間複雜度O(n^2),空間複雜度為O(1)

#include <stdio.h>
void move(int start,int end,int *s,int e)
{
    for(int t=end;t>=start;t--)
        s[t+1] = s[t];
}
void InsertSort(int *s,int n)
{
    int t;
    for(int i=1;i<n;i++)
    {
        t = s[i];
        for(int j=i-1;j>=0;j--)
            if(t >= s[j])
            {
                move(j+1,i-1,s,t);
                s[j+1] = t;
                break;
            }
        if(j < 0)//當前比較的數應該插入到最前面
        {
            move(0,i-1,s,t);
            s[0] = t;
        }
    }
}
int main()
{
    int s[] = {6,3,1,5,7,2,8,4};
    InsertSort(s,8);
    for(int i=0;i<8;i++)
        printf("%d ",s[i]);
    return 0;
}

 2二分歸併排序

 屬於穩定排序,時間複雜度O(n log n) 空間複雜度O（n)

歸併排序的演算法我們通常用遞歸實現

先把待排序區間[s,t]以中點二分，
接著把左邊子區間排序，再把右邊子區間排序，
最後把左區間和右區間用一次歸併操作合併成有序的區間[s,t]。

歸併操作的工作原理如下：
第一步：申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合併後的序列
第二步：設定兩個指針，最初位置分別為兩個已經排序序列的起始位置
第三步：比較兩個指針所指向的元素，選擇相對小的元素放入到合併空間，並移動指針到下一位置
重覆步驟3直到某一指針超出序列尾
將另一序列剩下的所有元素直接複製到合併序列尾

#include <stdio.h>
#include <stdlib.h>
void Merge(int *s,int start,int mid,int end)//兩個順序表長度可能不一
{
    int *s1 = (int *)malloc(sizeof(int)*(end - start + 1));
    int t = 0,i,j;
    i = start,j = mid + 1;//兩個指針指向兩個已經排序序列的起始位置
    while(i <= mid && j <= end)//兩個指針都未超出序列尾
    {
        if(s[i] > s[j])
        {
            s1[t++] = s[j];
            j ++;
        }
        else{
            s1[t++] = s[i];
            i ++;
        }
    }
    if(i > mid)//第一個順序表指針超出序列尾,則將第二個順序表剩下的所有元素直接複製到合併序列尾,反之亦然
    {
        for(int k=j;k<=end;k++)    
            s1[t++] = s[k];
    }
    if(j > end)
    {
        for(int k=i;k<=mid;k++)    
            s1[t++] = s[k];
    }
    for(int k=0;k<t;k++)//將合併後的順序表又複製回去
    {
//        s[start++] = s1[k];數組溢出
        s[start] = s1[k];
        start ++;
    }
    free(s1);
}
void MergeSort(int *s,int start,int end)
{
    if(end - start == 0)
        return;
    else if(end - start == 1){
        if(s[end] < s[start])//交換的前提
            s[end] = s[start] + s[end] - (s[start] = s[end]);//swap
        return;
    }
    else{
        MergeSort(s,start,(end-start)/2+start);
        MergeSort(s,(end-start)/2+start+1,end);
        Merge(s,start,(end-start)/2+start,end);//2-way Merge
    }
}
int main()
{
    int s[] = {10,4,6,3,8,2,5,7};
    MergeSort(s,0,7);
    for(int i=0;i<=7;i++)
        printf("%d ",s[i]);
    return 0;
}

測試樣例:

//10,4,6,3,11,8,2,5,7
//10,4,6,3,8,2,5,7
//2,1,8,3,9,10,5,3,7