十大排序(知识篇)--纯手工代码

//
//冒泡排序
//
#include <bits/stdc++.h>
using namespace  std;
void bubbleSort(int arr[],int len){
   bool flag = false;
   for(int i=0;i<len-1;i++){
       flag = false;
       for(int j=0;j<len-i-1;j++){
           if(arr[j] > arr[j+1]){
               swap(arr[j],arr[j+1]);
               flag = true;
           }
       }
       if(!flag){
           break;
       }
   }
}

//
// 计数排序
//
#include <bits/stdc++.h>
using namespace std;
void countingSort(int arr[],int len){
    int maxn = 0;
    for(int i=0;i<len;i++){maxn = max(maxn,arr[i]);}
    int t = maxn;
    int *cen = new int[maxn+10];
    for(int i=0;i<=maxn;i++){cen[i] = 0;}
    for(int i=0;i<len;i++){cen[arr[i]]++;}
    for(int i=1;i<=maxn;i++){cen[i] += cen[i-1];}
    int *ans = new int[len];
    for(int i=0;i<len;i++){
        ans[cen[arr[i]]-1] = arr[i];
        cen[arr[i]]--;
    }
    for(int i=0;i<len;i++){
        arr[i] = ans[i];
    }
    delete []ans;
    delete []cen;
}

//堆排序
#include <bits/stdc++.h>
using namespace std;
int heapSize = 0;
int left(int x){
    if(2*x+1 >= heapSize) return -1;
    return 2*x+1;
}
int right(int x){
    if(2*x+2 >= heapSize) return -1;
    return 2*x+2;
}
void minHeapify(int arr[],int x){
    int L = left(x);
    int R = right(x);
    int mann = x;
    if(L != -1 && arr[L] > arr[mann]){mann = L;}
    if(R != -1 && arr[R] > arr[mann]){mann = R;}
    if(mann != x){
        swap(arr[x],arr[mann]);
        x = mann;
        minHeapify(arr,x);
    }
}
void Delete(int arr[]){
    swap(arr[heapSize-1],arr[0]);
    heapSize--;
    minHeapify(arr,0);
}
void heapSort(int arr[],int len){
    //建立大顶堆
    heapSize = len;
    for(int i=(len-1)/2;i>=0;i--){
        minHeapify(arr,i);
    }
    //从堆中取结点
    for(int i=0;i<len;i++){
        Delete(arr);
    }
}

//
// 直接插入排序
//
#include <bits/stdc++.h>
using namespace std;
void insertSort(int arr[],int len){
    for(int i=1;i<len-1;i++){
        int j   =  i-1;
        int key =  arr[i];
        while(j>=0 && arr[j] > key){
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
}

//
// 归并排序
//
#include <bits/stdc++.h>
using namespace std;
void merge(int arr[],int l,int r){
    int mid = (l+r)/2;
    int nL  =  mid-l+1;
    int nR  =  r-mid;
    //创建两个行的数组存放
    int *L = new int[nL];
    int *R = new int[nR];
    for(int i=0;i<nL;i++){L[i]=arr[l+i];}
    for(int i=0;i<nR;i++){R[i]=arr[i+mid+1];}
    int i=0,j=0;        //分别指向L和R
    for(int k=l;k<=r;k++){
        if(j>=nR || (i<nL && L[i]<=R[j])){
            arr[k] = L[i++];
        }else{
            arr[k] = R[j++];
        }
    }
}
void mergeSort(int arr[],int l,int r){
    if(l < r){
        int mid = (l+r)/2;
        mergeSort(arr,l,mid);
        mergeSort(arr,mid+1,r);
        merge(arr,l,r);
    }
}

//
// 鸽巢排序
//
#include <bits/stdc++.h>
using namespace std;
void pigeonSort(int arr[],int len){
    int k = 0;
    for(int i=0;i<len;i++){k = max(k,arr[i]);}
    int *cen = new int[k+10];
    for(int i=0;i<=k;i++){cen[i]=0;}
    for(int i=0;i<len;i++){cen[arr[i]]++;}
    int j=0;
    for(int i=0;i<=k;i++){
        while(cen[i]){
            arr[j++] = i;
            cen[i]--;
        }
    }
    delete []cen;
}

//
//两种随机快排
//
#include <bits/stdc++.h>
using namespace std;
int partition(int arr[],int l,int r){
    int rd = l+rand()%(r-l);
    swap(arr[l],arr[rd]);
    int key = arr[rd];
    int i=l;
    for(int j=l;j<r;j++){
        if(arr[j] < key){
            swap(arr[i],arr[j]);
            i++;
        }
    }
    swap(arr[i],arr[r]);
    return i;
}
int partition2(int arr[],int l, int r){
    int ld = l+rand()%(r-l);
    swap(arr[l],arr[ld]);
    int key = arr[l];
    while(l < r){
        while(l<r && arr[l] <= key){l++;}
        arr[r] = arr[l];
        while(l<r && arr[r] > key){r--;}
        arr[l] = arr[r];
    }
    arr[l] = key;
    return l;
}
void quicksort(int arr[],int l,int r){
    if(l < r){
        int mid = partition2(arr,l,r);
        quicksort(arr,l,mid-1);
        quicksort(arr,mid+1,r);
    }
}

//
// 基数排序
//
#include <bits/stdc++.h>
using namespace std;
void redixSort(int arr[],int len){
    int maxn = 0;
    for(int i=0;i<len;i++){maxn = max(arr[i],maxn);}
    int t = maxn;
    int d = 0;
    while(t){t/=10;d++;}
    int mod = 10;
    for(int k=0;k<d;k++){
        queue<int> Bucket[10];
        for(int i=0;i<len;i++){
            Bucket[(arr[i]%mod) / (mod/10)].push(arr[i]);
        }
        int j=0;
        for(int i=0;i<10;i++){
            while(!Bucket[i].empty()){
                arr[j++] = Bucket[i].front();
                Bucket[i].pop();
            }
        }
        mod *= 10;
    }
}

//
// 选择排序
//
#include <bits/stdc++.h>
using namespace  std;
void selectSort(int arr[],int len){
    for(int i=0;i<len-1;i++){
        int minx = i;
        for(int j=i+1;j<len;j++){
            if(arr[j] < arr[minx]){minx = j;}
        }
        swap(arr[i],arr[minx]);
    }
}

//
// 希尔排序
//
#include <bits/stdc++.h>
using namespace std;
void shellSort(int arr[],int len){
    int gap =  len/2;
    while(gap >= 1){
       //做一个直接插入
       for(int i=gap;i<len;i++){
            int j = i - gap;
            int key = arr[i];
            while(j>=0 && arr[j] > key){
                arr[j+gap] = arr[j];
                j=j-gap;
            }
            arr[j+gap] = key;
       }
       gap = gap/2;
    }
}