王道408---冒泡排序、快速排序、直接插入排序、希尔排序、二路归并排序、简单选择排序代码实现以及时间复杂度

// 时间复杂度: O(n^2)
// 空间复杂度: O(1)
// 稳定排序算法

#include <stdio.h>
#include <iostream>
using namespace std;
int arr[16];

void debug(){
    for(int i=1;i<16;i++){
        printf("%d ",arr[i]);
    }
    puts("");
}

void bubbleSort(int S[],int n){
    // 这是我自己常写的
    // for(int i=0;i<n-1;i++){
    //     for(int j=i+1;j<n;j++){
    //         if(S[j] < S[i]){
    //             int tmp = S[j];
    //             S[j] = S[i];
    //             S[i] = tmp;
    //         }
    //     }
    // }

    // 王道 408 书上的定义是这样的  
    for(int i=0;i<n-1;i++){
        bool flag = false;
        for(int j=n-1;j>i;j--){
            if(S[j-1] > S[j]){          
                swap(S[j-1],S[j]);
                flag = true;
            }
        }
        if(!flag)           // 当一轮循环后没有发生交换则说明已经排序成功，直接退出即可
            return ;
    }
}
int main(){
    
    for(int i=1;i<16;i++){
        arr[i] = 16-i;
    }    
    bubbleSort(arr,16);
    debug();
    return 0;
}

// 稳定性: 不稳定
// 时间复杂度: O(nlog2n) ~ O(n^2)   平均O(nlog2n)
// 空间复杂度: O(log2n) ~ O(n)      平均O(log2n)
#include <stdio.h>
int arr[16];

void debug(){
    for(int i=1;i<16;i++){
        printf("%d ",arr[i]);
    }
    puts("");
}


void quickSort(int S[],int low,int height){
    if(low >= height) return ;
    printf("%d %d\n",low,height);

    int pivot = S[low+height>>1];   // 枢轴点  
    int left = low;
    int right = height;
    while(left < right){
        while(S[right] > pivot) right--;        // 这里不要写 <= 号,不然当pivot与left或right相等时，就一直死循环了
        while(S[left] < pivot) left++;              
        if(left < right ){
            int tmp = S[left];S[left] = S[right];S[right] = tmp;
        } 
    }

    // printf("%d %d\n",left,right);
    quickSort(S,low,right);
    quickSort(S,right+1,height);
}


// 下面是王道408书上给的排序算法,与上面略有不同
void quickSort408(int S[],int low,int high){
    if(low >= high) return ;

    int pivot = S[low]; // 枢轴   // 以 low 为初值
    int left = low,right = high;
    while(left<right){
        while(left < right && S[right] > pivot) --right;   // 以low 为初始值，我们需要先覆盖 S[low] 所以这里先减 right
        S[left] = S[right];
        while(left < right && S[left] < pivot) ++left;
        S[right] = S[left];
    }
    S[left] = pivot;             //因为是先从 right 开始的，所以第一个被覆盖的数一定是S[low]，即pivot 这时我们需要补上pivot
    quickSort408(S,low,left-1);
    quickSort408(S,left+1,high);
}

int main(){
    
    for(int i=1;i<16;i++){
        arr[i] = 16-i;
    }    
    quickSort408(arr,0,15);
    debug();
    return 0;
}

// 每遍历到一个元素，就拿这个元素一直向左比较，直到比左边元素小或者直到数组下标为0时终止
// 算法时间复杂度 : O(n) ~ O(n^2)  平均来看是O(n^2)
// 算法时间复杂度 : O(1)
// 算法稳定


#include <stdio.h>
int arr[16];




// 从小到大排序
void dirInsSort(int S[],int n){     // 对 下标为[1,15]的数组排序
    int i,j;
    for(i=2;i<n;i++){           // 遍历
        if(S[i] < S[i-1]){          // 当前这个数大于前面数时，不用管，因为符合从小到大 // 当前这个数小于前面数时:
            S[0] = S[i];            // 用S[0]只不过搜索方便存放数据，起一个中介作用
            for(j=i-1;S[0] < S[j];j--){    // S[0] 相当于哨兵
                S[j+1] = S[j];              // 向后移
            }
            S[j+1] = S[0];                  
        }
    }
}

void debug(){
    for(int i=1;i<16;i++){
        printf("%d ",arr[i]);
    }
    puts("");
}
int main(){

    for(int i=1;i<16;i++){
        arr[i] = 16-i;
    }    
    dirInsSort(arr,16);
    debug();
    return 0;
}

// 算法思路:
// 分步长的插入排序，第一轮选择步长 dk1 , 则对 (1,1+dk1*1,1+dk1*2 ..) 、 (2,2+dk1*1,2+dk1*2 ..)、等不同的组组内进行直接插入排序
// 第二论选择步长 dk2(dk2必须小于dk1，一般选为 dk1的 一半)，进行分组(1,1+dk2*1,1+dk2*2 ..) 、 (2,2+dk2*1,2+dk2*2 ..) 组内进行排序
// ...
// 直到选择的步长为1时，其组内排序即为最后的排序结果


// 时间复杂度: O(n) ~ O(n^2)  平均 O(n*log^2(n)) 或 O(n^1.5)
#include <stdio.h>
int arr[16];

void debug(){
    for(int i=1;i<16;i++){
        printf("%d ",arr[i]);
    }
    puts("");
}

void shellSort(int S[],int n){
    int dk,i,j;
    for(dk = n/2;dk>=1;dk/=2){          // 选择每一轮的步长
        
        for(i=dk+1;i<n;i++){
            if(S[i] < S[i-dk]){
                S[0] = S[i];
                for(j=i-dk;S[0] < S[j] && j>0;j-=dk){           //这时的S[0]就做不了哨兵的
                    S[j+dk] = S[j];
                }
                S[j+dk] = S[0];
            }
        }
    }    
}

int main(){

    for(int i=1;i<16;i++){
        arr[i] = 16-i;
    }    
    shellSort(arr,16);
    debug();
    return 0;
}

// 稳定性: 稳定算法
// 时间复杂度: O(nlog2n)
// 空间复杂度: O(n)

#include <stdio.h>
int arr[16];

void debug(){
    for(int i=1;i<16;i++){
        printf("%d ",arr[i]);
    }
    puts("");
}


// 算法本质就是分治后，把两个有序表合并为一个有序表
int B[20];
void Merge(int S[],int low,int mid,int high){           // 把S[low..mid] 和 S[mid+1..high] 两个有序表 合并为一个有序表
    int i,j,k;
    for(k=low;k<=high;k++)
        B[k] = S[k];
    for(i=low,j=mid+1,k=i;i<=mid && j<=high;k++){
        if(B[i] <= B[j])
            S[k] = B[i++];
        else
            S[k] = B[j++];
    }
    while(i<=mid) S[k++] = B[i++];          // 当一方到头，另一方还未检测完，复制
    while(j<=high) S[k++] = B[j++];         // 这俩while循环只会执行一个
}

void MergeSort(int S[],int low,int high){
    if(low >= high) return ;
    
    int mid = (low+high)/2;
    MergeSort(S,low,mid);
    MergeSort(S,mid+1,high);
    Merge(S,low,mid,high);
    
}

int main(){
    
    for(int i=1;i<16;i++){
        arr[i] = 16-i;
    }    
    MergeSort(arr,1,15);
    debug();
    return 0;
}

// 每次循环都取出剩余数组中最小的元素，并采用交换的策略使其交换出剩余数组(这也是该算法不稳定的源头)
// 稳定性: 不稳定
// 时间复杂度: 恒为O(n^2)
// 空间复杂度: O(1)
#include <stdio.h>
#include <iostream>
using namespace std;
int arr[16];

void debug(){
    for(int i=1;i<16;i++){
        printf("%d ",arr[i]);
    }
    puts("");
}


void simpleSelSort(int S[],int n){
    for(int i=0;i<n-1;i++){                     // 每次循环都取出剩余数组中最小的元素
        int min = i;
        for(int j=i+1;j<n;j++)
            if(S[j] < S[min]) min = j;  
        if(min != i) swap(S[i],S[min]);         // 简单选择排序的不稳定性就源于这个交换=> (2,2`,1) => (1,2`,2)  由于swap 把2与1的位置进行了交换，所以造成了简单排序的不稳定性   
    }
}


int main(){
    
    for(int i=1;i<16;i++){
        arr[i] = 16-i;
    }    
    simpleSelSort(arr,16);
    debug();
    return 0;
}