關于排序（直接插入排序、選擇排序、冒泡排序、歸并排序、快速排序）

關于排序（直接插入排序、選擇排序、冒泡排序、歸并排序、快速排序）

總結了一下關于排序的知識，理解比以前更深了～

#include<bits/stdc++.h>
using namespace std ;
//注意：陣列下標都是從1開始的！
//所有排序都是升序排序

void Insert_Sort(int a[] ,int n){//直接插入排序（i前面是已經排好序的了）
    for(int i =2 ;i <= n; i++ ){
        a[0] = a[i] ;//哨兵，記錄當前的值，防止越界
        int j ;
        for(j = i-1 ;a[j]>a[0] ;j--){//后移動
            a[j+1] = a[j];
        }
        a[j+1] = a[0] ;
    }
}
void Insert_Sort2(int a[] ,int n){//直接插入排序的優化——折半插入排序
    for(int i = 2;i<= n ;i++ ){//折半是在已經排好的序列折半
        a[0] = a[i] ;
        int low = 1 , high = i -1 ;
        while (low <= high){
            int mid = (high + low )/ 2 ;
            if(a[mid ] > a[0 ]){//a[0]在左邊
                high = mid - 1 ;
            }else{//a[0]在右邊
                low = mid + 1 ;
            }
        }
        for(int j = i-1 ;j >=high+1 ;j-- ){//元素后移動
            a[j+1] = a[j];
        }
        a[high + 1 ] = a[0];
    }
}

void Select_Sort(int a[],int n){//選擇排序（在這每次選擇的是最小值的下標），每次能確定一個數的位置
    for(int i = 1 ;i<= n ;i++ ){
        int min = i ;
        for(int j = i+1 ;j<=n ;j++ ){
            if(a[min] > a[j]){
                min = j ;
            }
        }
        if(min != i ){
            swap(a[min], a[i]);
        }

    }
}

void Bubble_Sort(int a[] ,int n){//冒泡排序，后面往前冒泡，每次能確定一個數的位置
    int flag = 1 ;//做小小的優化————當某一輪，沒有進行交換的時候，說明排序以及排好了（自行模擬）
    for(int i = 1 ;i <=n && flag; i++ ){
        flag= 0 ;
        for(int j = n-1 ;j>=i ;j -- ){
            if(a[j+1] < a[j]){
                flag = 1 ;
                swap(a[j+1], a[j]);
            }
        }
    }
}

int b[100 ];//歸并排序需要一個輔助陣列，一般是 2路歸并
void Merge_OP(int a[] ,int low ,int mid ,int high ){//歸并排序，low->mid , mid+1 -> high 兩部分
    int i = low ,j =mid+1 ,k = low ;//k是移動輔助陣列的下標
    while (i <= mid && j<= high ){
        if(a[i] < a[j]){
            b[k++] = a[i++ ];
        }else {
            b[k++ ] = a[j++];
        }
    }
    while (i <= mid){   // 注意有 " = "
        b[k++ ] = a[i++ ];
    }
    while (j <= high) {
        b[k++] = a[j++ ];
    }
    for(i = low ;i <= high ;i++ ){
        a[i] = b[i ];
    }
    
}
void Merge_Sort(int a[] ,int low ,int high ){//歸并也是遞回，先排，在合并
    if(low < high ){
        int mid = (low + high )/2;
        Merge_Sort(a , low ,mid );
        Merge_Sort(a , mid+1 , high);
        
        Merge_OP(a,low ,mid ,high);
        
    }
}

//大哥大 —— 快速排序，在這里寫兩種方式
//快排1
int Partition1(int a[],int low ,int high ){//第一種，取第一個數作為樞紐
    int pivort_key = a[low ];
    int i = low ,j = high ;
    
    while (i<j ){
        while (i < j && a[j] > pivort_key){//后面找比樞紐小的，換到前面
            j-- ;
        }
        a[i] = a[j] ;//這里也可以用swap交換，但是這樣直接賦值的時間復雜度要低（算是個優化，減少了比對次數）
        while (i < j && a[i] < pivort_key ){//前面找比樞紐大的，換到后面
            i ++ ;
        }
        a[j] = a[i];
    }
    a[i] = pivort_key;//最終確認樞紐的值（注意，如果前面用的swap，這里就不用賦值了）
    
    return i ;//每輪確定一個數的位置(pivort_key)，他左邊的定比他小，右邊的定比他大
}
void Quick_Sort1(int a[] ,int low ,int high ){//先分為兩邊，在排序（區分歸并）
    if(low < high ){//不管什么時候，遞回先寫遞回邊界
        int pivort = Partition1(a, low , high);
        
        Quick_Sort1(a, low , pivort -1 );
        Quick_Sort1(a, pivort + 1 , high );
    }
}
//快排2
//快速排序——亂數做種子
int Partition2(int a[] ,int low ,int high ){
    srand((unsigned)time(NULL));//取系統時間作為亂數的種子
    int m = low + rand() %(high - low +1 );//注意取余
    swap(a[m], a[low ]);//將樞紐元素交換到最左邊位置
    int i = low ;
    for(int j = i+1 ;j <= high ;j++  ){//去后面找，比樞紐小的，換到前面，也就是說，i位置左邊的數，定小于樞紐
        if(a[j] < a[low ]){
            swap(a[++i], a[j]);//作用同下面兩行
//            i++ ;
//            swap(a[i], a[j]);
        }
    }
    swap(a[i], a[low ]);//j走完了，說明陣列中沒有比當前樞紐值小的數了，此時i的位置就是樞紐應該的位置，交換
    return i ;
}
void Quick_Sort2(int a[] ,int low ,int high ){//遞回部分無變化
    if(low < high ){
        int pivort = Partition2(a, low , high);
        
        Quick_Sort1(a, low , pivort -1 );
        Quick_Sort1(a, pivort + 1 , high );
    }
}


void Print(int a[],int n){//列印
    for(int i = 1 ;i<= n ;i++ ){
        cout << a[i] <<" ";
    }
    cout << endl;
}

int main(){
    int a[] = {0,1,3,2,9,5,6,7,4,8};//0沒用，排序都是從下標為1開始的
    cout << "待排序序列：" ;
    Print(a, sizeof(a)/4 -1 );
    
//    cout << "直接插入排序：" ;
//    Insert_Sort(a, sizeof(a)/4 -1 );//長度要-1
//    Print(a,sizeof(a)/4 -1 );
    
//    cout << "折半插入排序：" ;
//    Insert_Sort2(a, sizeof(a)/4 -1 );//長度要-1
//    Print(a,sizeof(a)/4 -1 );
    
//    cout << "選擇排序：" ;
//    Select_Sort(a, sizeof(a)/4 -1 );//長度要-1
//    Print(a,sizeof(a)/4 -1 );
    
//    cout << "冒泡排序：" ;
//    Bubble_Sort(a, sizeof(a)/4 -1 );//長度要-1
//    Print(a,sizeof(a)/4 -1 );
    
//    cout << "歸并排序：" ;
//    Merge_Sort(a, 1, sizeof(a)/4 -1 );//長度要-1
//    Print(a,sizeof(a)/4 -1 );
    
//    cout << "快速排序1：" ;
//    Quick_Sort1(a, 1, sizeof(a)/4 -1 );//長度要-1
//    Print(a,sizeof(a)/4 -1 );
//
//    cout << "快速排序2：" ;
//    Quick_Sort2(a, 1, sizeof(a)/4 -1 );//長度要-1
//    Print(a,sizeof(a)/4 -1 );

    return  0 ;
}