這里主要指內(nèi)部排序，一共是8大算法，5個(gè)大類(lèi)。其中插入、選擇、交換分別包含一樸素算法和一改進(jìn)算法。除了基數(shù)排序外，其余四大類(lèi)都是比較排序。各算法思想在前面幾章中已基本講解，本篇主要是代碼實(shí)現(xiàn)。

插入排序

直接插入排序

#include <iostream>
using namespace std;

void print(int a[], int n)
{
    for (int i = 0; i < n; i ++)
        cout<<a[i]<<" ";
    cout<<endl;
}

void insertsort(int a[], int n)
{
    int i, j;
    for (i = 1; i < n; i ++)      //遍歷1～n的元素，檢查前面是否有更大的數(shù)。因?yàn)槭菑那巴蟊闅v的，所以前1～(i - 1)已經(jīng)有序。
    {
        if (a[i] < a[i - 1])
        {
            int tmp = a[i];
            for (j = i - 1; a[j] > tmp && j >= 0; j --)      //從后往前向后移
            {
                a[j + 1] = a[j];
            }
            a[j + 1] = tmp;
        }
    }
}

int main()
{
    int a[10] = {2,0,3,9,7,4,8,5,6,1};
    insertsort(a, 10);
    print(a, 10);
    return 0;
}

希爾排序

#include <iostream>
using namespace std;

void print(int a[], int n)
{
    for (int i = 0; i < n; i ++)
        cout<<a[i]<<" ";
    cout<<endl;
}
//希爾排序又叫縮小增量排序，在插入排序的基礎(chǔ)上分組排序，用增量dk控制排序間隔。
void insertsort(int a[], int n, int dk)
{
    int i, j;
    for (i = dk; i < n; i ++)        //以dk為間隔排序的一趟插入排序
    {
        if (a[i] < a[i - dk])
        {
            int tmp = a[i];
            for (j = i - dk; a[j] > tmp && j >= 0; j -= dk)
            {
                a[j + dk] = a[j];
            }
            a[j + dk] = tmp;
        }
    }
}

void shellsort(int a[], int n)
{
    int dk = n / 2;
    while(dk >= 1)           //從一半元素開(kāi)始，一直到增量為1
    {
        insertsort(a, n, dk);
        dk /= 2;
    }
}

int main()
{
    int a[10] = {2,0,3,9,7,4,8,5,6,1};
    shellsort(a, 10);
    print(a, 10);
    return 0;
}

至于希爾排序?yàn)槭裁茨芡ㄟ^(guò)增量分組的形式改進(jìn)插入排序：大概是排序的本質(zhì)就是消除逆序數(shù)，對(duì)于隨機(jī)數(shù)組逆序數(shù)是O(N^2) ，采用“交換相鄰元素”的辦法來(lái)消除逆序，每次正好只消除一個(gè)，因此必須執(zhí)行O(N^2) 的交換次數(shù)，故插入、冒泡的復(fù)雜度要到O(N^2)。而交換相隔比較遠(yuǎn)的元素，可以使一次交換能消除一個(gè)以上的逆序，從而提高效率。

選擇排序

簡(jiǎn)單選擇排序

#include<algorithm>
#include<iostream>
#include<vector>
#define ll long long
using namespace std;

void print(int a[], int n)
{
    for (int i = 0; i < n; i ++)
        cout<<a[i]<<" ";
    cout<<endl;
}

void selectsort(int a[], int n)
{
    int mini, mx;   //稍作改進(jìn)，每一趟中同時(shí)找最大最小值，這樣一趟可以到位兩個(gè)元素，故外層循環(huán)不超過(guò)n/2趟
    for (int i = 0; i < n/2; i ++)
    {
        mx = i, mini = i;
        for (int j = i + 1; j < n - i; j ++)            //1 ~ i與(n - i) ~ (n-1)的最小、最大值部分已到位
        {
            if (a[j] < a[mini])
                mini = j;
            if (a[j] > a[mx])
                mx = j;
        }
        swap(a[i], a[mini]);
        swap(a[n - 1 - i], a[mx]);
    }
}

int main()
{
    int a[10] = {0,9,3,7,4,6,2,8,5,1};
    selectsort(a, 10);
    print(a, 10);
    return 0;
}

堆排序

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
using namespace std;

void print(int a[], int n)
{
    int i;
    for (i = 0; i < n; i ++)
        cout<<a[i]<<" ";
    cout<<endl;
}

//下標(biāo)從0開(kāi)始
int Parent(int i)
{
    return (i - 1) / 2;
}

int Left(int i)
{
    return i * 2 + 1;
}

int Right(int i)
{
    return i * 2 + 2;
}

//遞歸調(diào)整位于i的元素
void MaxHeapify(int a [], int n, int i)
{
    int l = Left(i);
    int r = Right(i);
    int largest = 0;
    if (l <= (n - 1) && a[l] > a[i])
        largest = l;
    else
        largest = i;
    if (r <= (n - 1) && a[r] > a[largest])
        largest = r;
    if ( largest != i)
    {
        swap(a[i], a[largest]);
        MaxHeapify(a, n, largest);
    }
}

void BuildMaxHeap(int a[], int n)
{
    int i;
    for (i = n / 2 - 1; i >= 0; i --)
        MaxHeapify(a, n, i);
}

void HeapSort(int a[], int n)
{
    int i;
    BuildMaxHeap(a, n);
    for (i = n - 1; i >= 1; i --)
    {
        swap(a[0], a[i]);
        MaxHeapify(a, --n, 0);
    }
}

int main()
{
    int a[10] = {1,0,4,2,9,5,3,8,6,7};
    HeapSort(a, 10);
    print(a, 10);
    return 0;
}

交換排序

冒泡排序

改進(jìn)處在于設(shè)標(biāo)記pos記錄每趟排序后最后一次進(jìn)行交換的位置，pos之后的記錄都已交換到位，每趟排序只要掃描到pos即可。

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;

void print(int a[], int n)
{
    for (int i = 0; i < n; i ++)
        cout<<a[i]<<" ";
    cout<<endl;
}

void bubblesort(int a[], int n)
{
    int pos;
    for (int i = n - 1; i > 0;)
    {
        pos = 0;
        for (int j = 0; j < i; j ++)
            if (a[j] > a[j + 1])
            {
                pos = j;
                swap(a[j], a[j + 1]);
            }
        i = pos;
    }
}

int main()
{
    int a[10] = {0,9,3,7,4,6,2,8,5,1};
    bubblesort(a, 10);
    print(a, 10);
    return 0;
}

每趟排序中正反向兩遍掃描一次得到本趟最大最小兩個(gè)最終值，使排序趟數(shù)減少一半。

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;

void print(int a[], int n)
{
    for (int i = 0; i < n; i ++)
        cout<<a[i]<<" ";
    cout<<endl;
}

void bubblesort(int a[], int n)
{
    int low = 0, high = n - 1;
    while(low < high)
    {
        for (int j = low; j < high; j ++)
            if (a[j] > a[j + 1])
            swap(a[j], a[j + 1]);
        high --;

        for (int j = high; j > low; j --)
            if (a[j] < a[j - 1])
            swap(a[j], a[j - 1]);
        low ++;
    }
}

int main()
{
    int a[10] = {0,9,3,7,4,6,2,8,5,1};
    bubblesort(a, 10);
    print(a, 10);
    return 0;
}

快速排序

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;

void print(int a[], int n)
{
    for (int i = 0; i < n; i ++)
        cout<<a[i]<<" ";
    cout<<endl;
}

int part(int a[], int low, int high)
{
    int privote = a[low];
    while(low < high)
    {
        while(low < high && privote <= a[high]) high --;
        swap(a[low], a[high]);

        while(low < high && privote >= a[low]) low ++;
        swap(a[low], a[high]);
    }
    return low;
}

void quicksort(int a[], int low, int high)
{
    if (low < high)
    {
        int privotloc = part(a, low, high);
        quicksort(a, low, privotloc - 1);
        quicksort(a, privotloc + 1, high);
    }
}

int main()
{
    int a[10] = {0,9,3,7,4,6,2,8,5,1};
    quicksort(a, 0, 9);
    print(a, 10);
    return 0;
}

改進(jìn)：先只對(duì)長(zhǎng)度大于k的子序列遞歸調(diào)用快排，使原序列基本有序，然后再用插入排序。實(shí)踐表明k 取為 8左右時(shí)性能最佳。

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;

void print(int a[], int n)
{
    for (int i = 0; i < n; i ++)
        cout<<a[i]<<" ";
    cout<<endl;
}

int part(int a[], int low, int high)
{
    int privote = a[low];
    while(low < high)
    {
        while(low < high && privote <= a[high]) high --;
        swap(a[low], a[high]);

        while(low < high && privote >= a[low]) low ++;
        swap(a[low], a[high]);
    }
    return low;
}

void qsort_improve(int a[], int low, int high, int k)
{
    if (high - low > k)
    {
        int privotloc = part(a, low, high);
        qsort_improve(a, low, privotloc - 1, k);
        qsort_improve(a, privotloc + 1, high, k);
    }
}

void quicksort(int a[], int n, int k)
{
    qsort_improve(a, 0, n - 1, k);
    
    int i, j;
    for (i = 1; i < n; i ++)
    {
        if (a[i] < a[i - 1])
        {
            int t = a[i];
            for (j = i - 1; j >=0 && t < a[j]; j --)
                a[j + 1] = a[j];
                
            a[j + 1] = t;
        }
    }
}

int main()
{
    int a[10] = {0,9,3,7,4,6,2,8,5,1};
    quicksort(a, 10, 4);
    print(a, 10);
    return 0;
}

歸并排序

第二章已經(jīng)實(shí)現(xiàn)過(guò)基本的歸并排序，這里主要實(shí)現(xiàn)原地歸并排序。主要就是以下兩幅圖的過(guò)程，與原歸并排序區(qū)別在于Merge函數(shù)中用到輔助函數(shù)convert，將 j 所指的大于 i 所指的部分交換。

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;

void print(int a[], int n)
{
    for (int i = 0; i < n; i ++)
        cout<<a[i]<<" ";
    cout<<endl;
}

//用異或?qū)崿F(xiàn)交換數(shù)組中的兩數(shù)
void swapp(int a[], int x, int y)
{
    a[x] ^= a[y];
    a[y] ^= a[x];
    a[x] ^= a[y];
}
//將數(shù)組 l ～ r 間的元素轉(zhuǎn)置
void Reverse(int a[], int l, int r)
{
    while (l < r)
        swap(a[l ++], a[r --]);
}
//整體交換l ~ mid 和 mid ～ r 部分
void convert(int a[], int l, int mid, int r)
{
    Reverse(a, l, mid);
    Reverse(a, mid + 1, r);
    Reverse(a, l, r);
}

void Merge(int a[], int l, int mid, int r)
{
    int i = l;
    int j = mid + 1;
    while (i < j && j <= r)
    {
        while (i < j && a[i] <= a[j])
            i ++;
        int index = j;
        while (j <= r && a[j] < a[i])
            j ++;
        convert(a, i, index - 1, j - 1);
        i += j - index;
    }
}

void mergesort(int a[], int l, int r)
{
    if (l < r)
    {
        int mid = (l + r) / 2;
        mergesort(a, l, mid);
        mergesort(a, mid + 1, r);
        Merge(a, l, mid, r);
    }
}

int main()
{
    int a[10] = {0,9,3,7,4,6,2,8,5,1};
    mergesort(a, 0, 9);
    print(a, 10);
    return 0;
}

基數(shù)排序

例如對(duì)10個(gè)三位數(shù)排序，先按各位從小到大排，再十位再百位，每次排序可調(diào)用桶排序。