关于排序（直接插入排序、选择排序、冒泡排序、归并排序、快速排序）

总结了一下关于排序的知识，理解比以前更深了～

#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 ;
}