• 堆排序（實(shí)現(xiàn)難易：???）

① 將序列生成堆，調(diào)整成最大堆
② 彈出堆頂，生成新序列，重復(fù) ① 。

• 快速排序（實(shí)現(xiàn)難易：???）

（a）先移動(dòng) j 找到 <= low 的數(shù)，再移動(dòng) i 找到>= low 的數(shù)：
① 若 i < j ，兩者交換，繼續(xù)移動(dòng)。 ② 若 i >= j，j 與 low 交換。
（b）交換后數(shù)列劃分，分別令各子數(shù)列第一個(gè)數(shù)為 low，重復(fù)（a）。

• 歸并排序（實(shí)現(xiàn)難易：???）

• 希爾排序（實(shí)現(xiàn)難易：??）

• 直接插入排序（實(shí)現(xiàn)難易：?）

將下標(biāo) 1~n-1 的數(shù)依次插入準(zhǔn)序數(shù)列。

• 簡(jiǎn)單選擇排序（實(shí)現(xiàn)難易：?）

將下標(biāo) j=i+1~n-1 的最小數(shù)依次放在 i=0~n-2。

• 冒泡排序（實(shí)現(xiàn)難易：?）

將下標(biāo) i=n-1~1 的數(shù)從后往前兩兩相鄰數(shù) j=i-1~0 比較，若反序則交換。

• 哈希排序（實(shí)現(xiàn)難易：?）

運(yùn)用一個(gè)數(shù)組來記錄每個(gè)數(shù)出次數(shù)，也就是將序列和數(shù)組的下標(biāo)進(jìn)行對(duì)應(yīng)，從而實(shí)現(xiàn)排序。

#include <iostream>
#include <stdlib.h>
using namespace std;

//1、直接插入排序
void InsertSort(int key[], int n){
    int i,j;                                
    for(i=1; i<n; i++){             //遍歷第 2~n-1 個(gè)元素
        int insert = key[i]; 
        for(j=i-1; j>=0; j--){
            if(insert < key[j])
                key[j+1] = key[j];
            else break;
        }
        key[j+1] = insert;          
    }
}

//2、簡(jiǎn)單選擇排序
void SelectSort(int key[], int n){
    int small,i,j;
    for(i=0; i<n-1; i++){           //遍歷第 1~n-1 個(gè)元素 
        small = i; 
        for(j=i+1; j<n; j++){       //遍歷第 i+1~n 個(gè)元素
            if(key[j] < key[small]) 
                small = j;
        }
        if(small != i)                         
            swap(key[i], key[small]);  
    }
}

//3、冒泡排序
void BubbleSort(int key[], int n){
    int i,j;                    
    for(i=n-1; i>0; i--){           //遍歷第 2~n 個(gè)元素
        bool isSwap = false;   
        for(j=0; j<i; j++){         //遍歷第 1~i 個(gè)元素
            if(key[j] > key[j+1]){
                swap(key[j],key[j+1]);
                isSwap = true;
            }
        }
        if(!isSwap) break;     
    }
}

//4、快速排序 
int Partition(int key[], int low,int high){
    int i = low,j = high + 1;
    int flag = key[low];            //當(dāng)前分割元素
    do{
        do i++;
        while(key[i] < flag);      
        do j--;
        while(key[j] > flag);     
        if(i < j)
            swap(key[i], key[j]);    
    }while(i < j);
    swap(key[low], key[j]);
    return j;                       //下一個(gè)分割元素 
}

void QuickSort(int key[], int low, int high){   
    int k;
    if(low < high){                            
        k = Partition(key,low,high);
        QuickSort(key,low,k-1);
        QuickSort(key,k+1,high);
    }
}

void QuickSort(int key[], int n){                 
    QuickSort(key,0,n-1);
}

//5、歸并排序
void _merge(int key[], int low, int mid, int high) { //合并
    for (int i = 0; i < mid; i++) { 
        for (int j = mid; j < high; j++) {
            if (key[i] > key[j]) 
                swap(key[i], key[j]);
        }
    }
}

void MergeSort(int key[], int low, int high) {
    if (low < high) {
        int length = high - low;
        if (length == 1) {
            if (key[low] > key[high])
                swap(key[low],key[high]);
        }
        for (int i=length/2; i>0; i=i/2) {  //分治 
            MergeSort(key, low, low + i);
            MergeSort(key, high - i, high);
            _merge(key, low, i, high);      //i為有序序列長(zhǎng)度 
        }
    }
}

//6、堆排序
void AdjustDown(int heap[], int current, int border){
    int tmp = heap[current];
    while (2*current+1<=border){
        int child = 2*current+1;            //左孩子 
        if (child+1<=border && heap[child]<heap[child+1])
            child++;
        if (heap[child] > heap[current]) {
            heap[current] = heap[child];
            heap[child] = tmp;
        }
        else break;
        current=child;
    }
}

void HeapSort(int heap[],int n){
    for(int i=(n-2)/2; i>=0; i--)           //初始調(diào)整 
        AdjustDown(heap,i,n-1);
    for(int j=n-1; j>0; j--){
        swap(heap[0],heap[j]);              //交換 
        AdjustDown(heap, 0, j-1);           //調(diào)整 
    }
}


//7、希爾排序 
void shell(int arr[], int n, int start, int gap) {
    for (int j = start + gap; j < n; j += gap) {
        int i = j - gap;
        int tmp = arr[j];
        while (i >= start && arr[i] > tmp) {
            arr[i + gap] = arr[i];
            i -= gap;
        }
        arr[i + gap] = tmp;
    }
}
void ShellSort(int arr[], int n) {
    if (n <= 1) 
        return;
    for (int gap=n/2; gap>=1; gap/=2) {
        for (int i=0; i<gap; i++) 
            shell(arr, n, i, gap);
    }
}

//8、哈希排序 
void HashSort(int key[], int n){
    int hash_map[n] = {0};   
    for (int i = 0; i < n; i++){
        hash_map[key[i]]++;
    }   
    for (int i = 0; i < n; i++){  
        for (int j = 0; j < hash_map[i]; j++)
            printf("%d ", i);
    } 
}

//產(chǎn)生隨機(jī)序列 
void Init(int key[], int n){
    cout<<"\n\n隨機(jī)序列：";
    for(int i=0; i<n; i++){
        key[i] = rand()%20;
        cout<<key[i]<<" ";
    }
} 

//輸出有序序列 
void output(int key[], int n){
    for(int i=0; i<n; i++)
        cout<<key[i]<<" ";
}

int main(){
    int key[500000], n; 
    cout<<"\n隨機(jī)序列長(zhǎng)度：";              cin>>n;     
    Init(key,n);                            InsertSort(key,n); 
    cout<<"\n\n直接插入排序：";                output(key,n);     
    Init(key,n);                            SelectSort(key,n); 
    cout<<"\n\n簡(jiǎn)單選擇排序：";                output(key,n);
    Init(key,n);                            BubbleSort(key,n); 
    cout<<"\n\n冒泡排序：";                  output(key,n); 
    Init(key,n);                            QuickSort(key,n); 
    cout<<"\n\n快速排序：";                  output(key,n);    
    Init(key,n);                            MergeSort(key,0,n-1);
    cout<<"\n\n歸并排序：";                  output(key,n);     
    Init(key,n);                            HeapSort(key,n); 
    cout<<"\n\n堆排序：";                   output(key,n);   
    Init(key,n);                            ShellSort(key,n); 
    cout<<"\n\n希爾排序：";                  output(key,n);
    Init(key,n);                            
    cout<<"\n\n哈希排序：";                  HashSort(key,n); 
    cout<<"\n\n";
    return 0;
}