温习 6+2 种排序方式

• 堆排序（实现难易：⭐⭐⭐）

① 将序列生成堆，调整成最大堆
② 弹出堆顶，生成新序列，重复 ① 。

• 快速排序（实现难易：⭐⭐⭐）

（a）先移动 j 找到 <= low 的数，再移动 i 找到>= low 的数：
① 若 i < j ，两者交换，继续移动。 ② 若 i >= j，j 与 low 交换。
（b）交换后数列划分，分别令各子数列第一个数为 low，重复（a）。

• 归并排序（实现难易：⭐⭐⭐）

• 希尔排序（实现难易：⭐⭐）

• 直接插入排序（实现难易：⭐）

将下标 1~n-1 的数依次插入准序数列。

• 简单选择排序（实现难易：⭐）

将下标 j=i+1~n-1 的最小数依次放在 i=0~n-2。

• 冒泡排序（实现难易：⭐）

将下标 i=n-1~1 的数从后往前两两相邻数 j=i-1~0 比较，若反序则交换。

• 哈希排序（实现难易：⭐）

运用一个数组来记录每个数出次数，也就是将序列和数组的下标进行对应，从而实现排序。

#include 
#include 
using namespace std;

//1、直接插入排序
void InsertSort(int key[], int n){
    int i,j;                                
    for(i=1; i=0; j--){
            if(insert < key[j])
                key[j+1] = key[j];
            else break;
        }
        key[j+1] = insert;          
    }
}

//2、简单选择排序
void SelectSort(int key[], int n){
    int small,i,j;
    for(i=0; i0; i--){           //遍历第 2~n 个元素
        bool isSwap = false;   
        for(j=0; 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];            //当前分割元素
    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;                       //下一个分割元素 
}

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为有序序列长度 
        }
    }
}

//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[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--)           //初始调整 
        AdjustDown(heap,i,n-1);
    for(int j=n-1; j>0; j--){
        swap(heap[0],heap[j]);              //交换 
        AdjustDown(heap, 0, j-1);           //调整 
    }
}


//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>n;     
    Init(key,n);                            InsertSort(key,n); 
    cout<<"/n/n直接插入排序：";                output(key,n);     
    Init(key,n);                            SelectSort(key,n); 
    cout<<"/n/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;
}