Insertion Sort and Merge Sort

  • 2021 年 4 月 24 日
  • 筆記

Insertion Sort（插入排序）

思路：for 循環遍曆數組中的每一個數

　　　用while將每次遍歷到的數於左側的數進行對比，將小的排到左邊

void InsertionSort(int*A, int n){
    int key,i=0,p;
    for(p=0;p<n;p++){
        key=A[p];
        i=p-1;
        while(i>=0 && A[i]>key){
            A[i+1]=A[i];
            i=i-1;
        }
        A[i+1]=key;
    }
}

中規中矩的排序方法

時間複雜度：

Best-case Running time  ： O(n)（數組已經被排好序的情況）

Worst-case Running Time :  O(n^2)

Average Running Time :  O(n^2)

從時間複雜度來看，處理少量數據還可以。當數據量較為龐大時，速度就很慢了

 

Merge Sort

思路：利用遞歸將數組分成兩個相同大小的部分，直至長度為1

　　　然後利用merge函數分別對每個部分進行排序

　　　最後重新放在一起

void Merge(long int*A,long int left,long int center,long int right){
    long int i1=left,i2=center+1,i=0,j;
    long int B[100000];
    long int length =sizeof(B)/sizeof(B[0]);
//比較左右兩側的大小，然後將小的的放入數組B
    while (i1<=center && i2<=right)
    {   
        if(A[i1]>A[i2]){
            B[i++]=A[i2++];
        }else{
            B[i++]=A[i1++];
        }
    }
//將左側或者右側剩餘的數以此放入數組B中
    for(;i1<=center;i1++){
        B[i++]=A[i1];
    }
    for(;i2<=right;i2++){
        B[i++]=A[i2];
    }
//將數組B中排好序的值賦給A
//由於每調用一次函數，B數組都會重新創建，因此B從0開始，A從left開始
    for(j=0,i=left;j<=right-left;j++,i++){
        A[i]=B[j];
    }
    
}

void MergerSort(long int*A,long int left,long int right){
    long int center=0;
    if(left>=right){
        return ;
    }
    center=(left+right)/2;
//這種先進行第一個遞歸，直至最後，沒進行一次就相當於建立一層平台，當進行完後再返回上一層，執行下一個語句
    MergerSort(A,left,center);
    MergerSort(A,center+1,right);
    Merge(A,left,center,right);
}

這個就是merge sort 的排序過程：

 

個人覺得遞歸部分的代碼不是很好理解，其餘部分都還可以

時間複雜度：

 

VirMach 便宜 VPS

QNews

QNews