手撕经典排序算法

直接插入排序

第一个结点默认已序，从第二个结点开始，即i=1。每次使用一个tmp报错第i个结点，然后依次将tmp与第[i-1 ~ 0]的元素进行比较，如果tmp小于其元素，则依次后移。直到找打插入位置。

void InsertionSort(vector<int> &data){
    for(int i = 1;i<data.size();++i){
        int tmp = data[i];
        for(int j = i;j>0&&tmp<data[j-1];--j){
            data[j]=data[j-1]; //向后覆盖
        }
        data[j]=tmp;
    }
}

折半插入排序（稳定的）

思路与直接插入相同，只是查找插入位置的方法不同，这里使用折半查找法查找插入点。查找到之后，一次性将所有元素后移以为，然后插入元素。
这里有个疑问：为什么取low<=high？

void InsertionSort(vector<int> &data){
    for(int i = 1;i<data.size();++i){
        int tmp = data[i];
        int low = 0,high=i-1;
        while(low<=high){//为什么取等号？
            int mid = (low+high)/2;
            if(data[mid]>tmp) high=mid-1;
            else low=mid+1;
        }

        for(j = i-1;j>=high+1;--j){
            data[j+1]=data[j];
        }
        data[high+i]=tmp;
    }
}

希尔排序（不稳定）?

希尔排序是直接插入排序的优化版

void ShellSort(vector<int> &data){
    int len = data.size();
    for(int dk = len/2;dk>=1;dk=dk/2){
        for(int i = dk+1;i<n;++i){
            if(data[i]<data[i-dk]){
                int tmp = data[i];
                for(int j = i-dk;j>=0&&tmp<data[j];j-=dk){
                    data[j+dk] = data[j];
                }
                data[j+dk] = tmp;
            }
        }
    }
}

冒泡排序

i从0开始到n-2;
j从n-1开始到i+1,运行条件为j>i或者flag = false
遇到data[j]<data[j-1]不断交换，每一趟都能过把最元素放到最终的位置

void BubbleSort(vector<int> &data){
    bool flag = true;
    for(int i = 0;i<data.size()-1 && flag;++i){ //若flag为false，停止，表示上一趟没有交换
        for(int j = data.size()-1,flag=false;j>i;--j){
            if(data[j]<data[j-1]){
                swap(data[i],data[j-1]);//小的往前移动，每次最小的都能过到最后的位置
                flag = true; //只要有交换，就设置成true
            }
        }
    }
}

快速排序

#python实现
def quik_sort(data):
    if len(num)<2: //包含[],[x]的情况
        return data
    else:
        pivot = data[0]
        less = [x for x in data[1:] if x <=pivot]
        greater = [x for x in data[1:] if x >pivot]
        return quik_sort(less)+pivot+quik_sort(greater)

#C++实现
//划分（主要）
int Partition(vector<int> &data,int low,int high){
    int pivot = data[low];
    while(low<high){
        while(low<high&&data[high]>=pivot) --high;
        data[low]=data[high];//此时low空出来了
        while(low<high&&data[low]<=pivot) ++low;
        data[high]=data[low];//此时high空出来了
    }
    data[low] = pivot; //排序
    return low;
}

void QuikSort(vector<int> &data,int low,int high){
    if(low<high){
        int pivot_pos = Partition(data,low,high);
        QuikSort(data,pivot_pos+1,high);
        QuikSort(data,low,pivot_pos-1);
    }
}

简单选择排序

void SelectSort(vector<int> &data){
    for(int i = 0;i<n-1;++i){
        int min = i;
        for(int j = i;j<n;j++){
            if(data[j]<data[min])
                min = j;
        }
        if(i!=min) swap(data[i],data[min]);
    }
}

归并排序

void Merge(vector<int> &data,int left,int mid,int right){
    auto beg = data.begin();
    vector<int> Left(beg+left,beg+m); //开辟一个辅助空间，存储左边的元素
    int i = 0; //index of Left
    int j = m,k = 0;
    while(i<Left.size()&&j<=right){
        if(Left[i] <= data[j]) data[k++] = Left[i++];
        else data[k++] = data[j++];
    }
    while(i<Left.size()) data[k++] = data[i++];
}

void MergeSort(vector<int> &data,int left,int right){
    if(left<right){
        int mid = left+(right-1)/2;
        MergeSort(data,left,mid);
        MergeSort(data,mid+1,right);
        Merge(data,left,mid,right);
    }
}

堆排序

void Heapify(vector<int> &data,int n,int i){
    int largest = i;
    int left = 2*i+1;  //左孩子
    int right = 2*i+2; //右孩子

    if(left<n && data[right]>data[largest]){ //左孩子与父节点比较大小，取大
        largest = left;
    } 
    if(right<n && data[right]>data[largest]){ //右孩子与父节点比较大小，取大
        largest = right;
    }

    if(largest != i) {
        swap(data[largest],data[i]); //交换使得父节点最大
        Heapify(data,n,largest); //递归建堆
    }
}

void HeapSort(vector<int> &data){
    int len = data.size();
    //建初始堆
    for(int i = len/2-1;i>=0;i--){//从最后一个父节点往前建立堆
        Heapify(data,len,i);
    }
    //堆排序
    for(int j = n-1;j>=0;--j){
        data[j] = data[0]; //排序
        Heapify(data,j,0);
    }
}

基数排序（来自力扣）

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。排序过程是将所有待比较数值统一为同样的数位长度，数位较短的数前面补零，然后从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

int getMax(int arr[], int n) 
{ 
    int mx = arr[0]; 
    for (int i = 1; i < n; i++) 
        if (arr[i] > mx) 
            mx = arr[i]; 
    return mx; 
} 

void countSort(int arr[], int n, int exp) 
{ 
    int output[n]; 
    int i, count[10] = {0}; 
  
    for (i = 0; i < n; i++) 
        count[ (arr[i]/exp)%10 ]++; 
  
    for (i = 1; i < 10; i++) 
        count[i] += count[i - 1]; 
  
    for (i = n - 1; i >= 0; i--) 
    { 
        output[count[ (arr[i]/exp)%10 ] - 1] = arr[i]; 
        count[ (arr[i]/exp)%10 ]--; 
    } 
  
    for (i = 0; i < n; i++) 
        arr[i] = output[i]; 
} 
  
void radixsort(int arr[], int n) 
{ 
    int m = getMax(arr, n); 
    for (int exp = 1; m/exp > 0; exp *= 10) 
        countSort(arr, n, exp); 
}