用到的部分函數(shù)

#include "pch.h"
#include<iostream>
#include<string>
#include<vector>
using namespace std;
void swap(vector<int> &arr, int x,int y) 
{
    arr[x] += arr[y];
    arr[y] = arr[x] - arr[y];
    arr[x] -= arr[y];
}
void printVector(vector<int> arr) 
{
    for (int i = 0; i < arr.size(); i++) 
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}
int getMaxValue(const vector<int> &arr)
{
    int max = INT_MIN;
    for (auto val : arr)
    {
        if (val > max)
            max = val;
    }
    return max;
}

一、冒泡排序

/*
冒泡排序 時間復雜度：O(N^2) 　　穩(wěn)定性：穩(wěn)定
依次比較相鄰兩元素，若前一元素大于后一元素則交換之，直至最后一個元素即為最大；
然后重新從首元素開始重復同樣的操作，直至倒數(shù)第二個元素即為次大元素；依次類推。
如同水中的氣泡，依次將最大或最小元素氣泡浮出水面。
1 0 4 2 3
0 1 4 2 3 i=5 j=1
0 1 4 2 3 i=5 j=2
0 1 2 4 3 i=5 j=3
0 1 2 3 4 i=5 j=4
*/
void bubbleSort(vector<int> &arr, int begin, int end) 
{
    bool loop = true;
    for (int i = end; i >begin && loop; i--) 
    {
        loop = false;
        for (int j = begin + 1; j < i; ++j) 
        {
            if (arr[j] < arr[j - 1]) 
            {
                loop = true;
                swap(arr, j, j - 1);
            }
        }
    }
    printVector(arr);
}

二、選擇排序

/*
選擇排序 時間復雜度：O(N^2) 　　穩(wěn)定性：不穩(wěn)定
首先初始化最小元素索引值為首元素，依次遍歷待排序數(shù)列，
若遇到小于該最小索引位置處的元素則刷新最小索引為該較小元素的位置，
直至遇到尾元素，結束一次遍歷，并將最小索引處元素與首元素交換；
然后，初始化最小索引值為第二個待排序數(shù)列元素位置，同樣的操作，可得到數(shù)列第二個元素即為次小元素；
以此類推。
1 0 4 2 3
0 1 4 2 3 i=0 j=1
0 1 4 2 3 i=0 j=2
0 1 4 2 3 i=0 j=3
0 1 4 2 3 i=0 j=4
0 1 4 2 3 i=1 j=2
0 1 4 2 3 i=1 j=3
0 1 4 2 3 i=1 j=4
0 1 2 4 3 i=2 j=3
0 1 2 4 3 i=2 j=4
0 1 2 3 4 i=3 j=4
0 1 2 3 4 i=4 j=4
*/
void selectSort(vector<int> &arr,int begin,int end) 
{
    
    for (int i = begin ; i < end; i++) 
    {
        int min_index = i;
        for (int j = i + 1; j < end; j++) 
        {
            if (arr[j] < arr[min_index]) 
            {
                min_index = j;
            }
        }
        if(i!=min_index)
            swap(arr, i, min_index);
    }
    printVector(arr);
}

三、快速排序

/*
快速排序 時間復雜度：O(NlogN) 　　穩(wěn)定性：不穩(wěn)定
（類似于選擇排序的定位思想）選一基準元素，依次將剩余元素中小于該基準元素的值放置其左側，
大于等于該基準元素的值放置其右側；然后，取基準元素的前半部分和后半部分分別進行同樣的處理；
以此類推，直至各子序列剩余一個元素時，即排序完成（類比二叉樹的思想，from up to down）
*/
void quickSort(vector<int> &arr, int begin, int end) 
{
    if (begin >= end - 1)
        return;
    int left_index = begin;
    int right_index = end - 1;
    int root = arr[left_index];
    while (left_index < right_index) 
    {
        while (left_index < right_index) 
        {
            printVector(arr);
            if (arr[right_index] < root) 
            {
                arr[left_index++] = arr[right_index];
                break;
            }
            --right_index;
        }


        while (left_index < right_index)
        {
            printVector(arr);
            if (arr[left_index] >= root)
            {
                arr[right_index--] = arr[left_index];
                break;
            }
            ++left_index;
        }
        
    }
    
    arr[left_index] = root;
    quickSort(arr, begin, left_index);
    quickSort(arr, right_index + 1, end);
    printVector(arr);
}

四、插入排序

/*
插入排序 時間復雜度：O(N2) 　　穩(wěn)定性：穩(wěn)定
數(shù)列前面部分看為有序，依次將后面的無序數(shù)列元素插入到前面的有序數(shù)列中，
初始狀態(tài)有序數(shù)列僅有一個元素，即首元素。在將無序數(shù)列元素插入有序數(shù)列的過程中，
采用了逆序遍歷有序數(shù)列，相較于順序遍歷會稍顯繁瑣，但當數(shù)列本身已近排序狀態(tài)效率會更高。
1 0 4 2 3
0 1 4 2 3
*/
void insertSort(vector<int> &arr,int begin,int end) 
{
    for (int i = begin + 1; i < end; i++) 
    {
        int j = i - 1;//有序元素段尾從0開始，后面遞增長度1
        for (; j >= begin; --j)//這一層for是為了找到數(shù)組中有序的那一段,從0開始
            if (arr[j] <= arr[i])
                break;
        if (j != i - 1)
        {
            int tmp = arr[i];
            for (int k = i; k > j + 1; --k)
                arr[k] = arr[k - 1];
            arr[j + 1] = tmp;
        }
        printVector(arr);
    }
    
}

五、桶排序

/*
桶排序
實現(xiàn)線性排序，但當元素間值得大小有較大差距時會帶來內(nèi)存空間的較大浪費。
首先，找出待排序列中得最大元素max，申請內(nèi)存大小為max + 1的桶（數(shù)組）并初始化為0；
然后，遍歷排序數(shù)列，并依次將每個元素作為下標的桶元素值自增1；
最后，遍歷桶元素，并依次將值非0的元素下標值載入排序數(shù)列（桶元素>1表明有值大小相等的元素，
此時依次將他們載入排序數(shù)列），遍歷完成，排序數(shù)列便為有序數(shù)列。
*/
void bucketSort(vector<int> &arr, int begin, int end)
{
    int max = getMaxValue(arr);
    
    int *pArr = new int[max + 1];
    memset(pArr, 0, (max + 1)*sizeof(int));
    for(auto const i:arr)
    {
        ++pArr[i];
    }
    for (int i = 0, j = 0; i <= max; ++i)
    {
        while (pArr[i]--)
            arr[j++] = i;
        
    }
    delete[] pArr;
    printVector(arr);
}

六、希爾排序

/*
希爾排序
插入排序的改進版。為了減少數(shù)據(jù)的移動次數(shù)，在初始序列較大時取較大的步長，通常取序列長度的一半，
此時只有兩個元素比較，交換一次；之后步長依次減半直至步長為1，即為插入排序，由于此時序列已接近有序，
故插入元素時數(shù)據(jù)移動的次數(shù)會相對較少，效率得到了提高。
*/
void shellSort(vector<int> &arr, int bgn, int end)
{
    for (int step = (end - bgn) / 2; step > 0; step /= 2)
    {
        for (int i = bgn; i < step; ++i)
        {
            /*
            * 以下，insertSort的變異
            */
            for (int j = i + step; j < end; j += step)
            {
                int k = j - step;
                for (; k >= i; k -= step)
                    if (arr[k] <= arr[j])
                        break;
                if (k != j - step)
                {
                    int tmp = arr[j];
                    for (int m = j; m > k + step; m -= step)
                        arr[m] = arr[m - step];
                    arr[k + step] = tmp;
                }
            }
        }
    }
}

七、歸并排序

/*
歸并排序 - 采用了分治和遞歸的思想，遞歸&分治-排序整個數(shù)列如同排序兩個有序數(shù)列，
依次執(zhí)行這個過程直至排序末端的兩個元素，再依次向上層輸送排序好的兩個子列進行排序直至整個數(shù)列有序
（類比二叉樹的思想，from down to up）。
*/
void mergeSortInOrder(vector<int> &arr, int bgn, int mid, int end)
{
    int *pBuf = new int[end - bgn];
    int *pTemp = pBuf;
    int lindex = bgn;
    int rindex = mid;

    while ((lindex < mid) && (rindex < end))
        *(pTemp++) = (arr[lindex] < arr[rindex]) ? arr[lindex++] : arr[rindex++];

    while (lindex < mid)
        *pTemp++ = arr[lindex++];
    while (rindex < end)
        *pTemp++ = arr[rindex++];

    //pTemp -> arr
    pTemp = pBuf;
    for (int i = bgn; i < end; i++)
        arr[i] = *pTemp++;

    delete[]pBuf;
}
//UpToDown To DownToUp
void mergeSort(vector<int> &arr, int bgn, int end)
{
    //數(shù)組arr空or僅有一個元素則退出
    if (bgn >= end - 1)
        return;

    int mid = (bgn + end) / 2;
    mergeSort(arr, bgn, mid);
    mergeSort(arr, mid, end);
    mergeSortInOrder(arr, bgn, mid, end);
}

八、堆排序

/*
堆排序 - 時間復雜度：O(NlogN) 　　穩(wěn)定性：不穩(wěn)定
堆排序的思想借助于二叉堆中的最大堆得以實現(xiàn)。
首先，將待排序數(shù)列抽象為二叉樹，并構造出最大堆；然后，
依次將最大元素（即根節(jié)點元素）與待排序數(shù)列的最后一個元素交換（即二叉樹最深層最右邊的葉子結點元素）；
每次遍歷，刷新最后一個元素的位置（自減1），直至其與首元素相交，即完成排序。
*/
/*堆排序*/
//根節(jié)點元素自頂向下移動到合適的位置以構成最大堆
void downToMaxHeap(vector<int> &arr, int bgn, int end)
{
    int child;
    int parent = bgn;

    /*假根節(jié)點向下移動至合適的位置 --整個堆排序的核心代碼塊*/
    while ((child = parent * 2 + 1) < end)
    {
        if ((child < end - 1) && (arr[child] < arr[child + 1]))
            ++child;    //右孩子節(jié)點
        if (arr[child] > arr[parent])
            swap(arr, child, parent);
        else
            break;
        parent = child;
    }
}
//將數(shù)組構造為最大堆
void buildMaxHeap(vector<int> &arr, int bgn, int end)
{
    if (bgn >= end - 1)
        return;

    int parent = end / 2 - 1;
    while (parent >= 0)
    {
        downToMaxHeap(arr, parent, end);
        --parent;
    }
}
//堆排序
void heapSort(vector<int> &arr, int bgn, int end)
{
    //構造最大堆
    buildMaxHeap(arr, bgn, end);

    while (end > 1)
    {
        swap(arr,0, --end);
        downToMaxHeap(arr, 0, end);
    }
}

九、基數(shù)排序

/*
基數(shù)排序 - 時間復雜度：O(x*N) 　　穩(wěn)定性：穩(wěn)定
桶排序的改進版，桶的大小固定為10，減少了內(nèi)存空間的開銷。
首先，找出待排序列中得最大元素max，并依次按max的低位到高位對所有元素排序；
桶元素10個元素的大小即為待排序數(shù)列元素對應數(shù)值為相等元素的個數(shù)，即每次遍歷待排序數(shù)列，
桶將其按對應數(shù)值位大小分為了10個層級，桶內(nèi)元素值得和為待排序數(shù)列元素個數(shù)。
*/
/*基數(shù)排序*/
//1. 計數(shù)排序，按整形數(shù)值單位進行排序
void countSort(vector<int> &arr, int exp)
{
    int bucket[10] = { 0 };
    int arrSize = arr.size();
    int *pTemp = new int[arrSize];
    memset(pTemp, 0, arrSize * sizeof(int));

    //統(tǒng)計單位exp各數(shù)值計數(shù)值
    for (auto const val : arr)
        ++bucket[(val / exp) % 10];

    //計數(shù)分層
    for (int i = 1; i < 10; ++i)
        bucket[i] += bucket[i - 1];

    //按exp位大小用數(shù)組arr元素填充pTemp
    for (int i = arrSize - 1; i >= 0; --i)
        pTemp[--bucket[(arr[i] / exp) % 10]] = arr[i];
    /*bugs*/
#if 0
    //bug1: bucket各層次的計數(shù)值沒遍歷一次相應自減1
    for (auto const val : arr)
        pTemp[bucket[(val / exp) % 10] - 1] = val;
    //bug2: arr數(shù)組元素每次排序時，下標應從大到小遍歷，否則無法實現(xiàn)排序
    for (auto const val : arr)
        pTemp[--bucket[(val / exp) % 10]] = val;
#endif

    //pTemp -> arr
    for (int i = 0; i < arrSize; ++i)
        arr[i] = pTemp[i];
    delete[]pTemp;
}
//2. 合并各單位計數(shù)排序結果
void radixSort(vector<int> &arr)
{
    int max = getMaxValue(arr);
    for (int exp = 1; max / exp != 0; exp *= 10)
        countSort(arr, exp);
}