不同的場景使用不同的排序算法本身沒有好壞之分。

（Ps:所有算法均自己測試通過沒有bug,如果小伙伴們有疑問請隨時留言提問~~~）
當(dāng)面試官問上面我說的那個問題的時候要首先考慮清楚面試官要干什么者祖？比如：
可以反問面試官：

• 有沒有大量的重復(fù)值盅安？-->計數(shù)排序
• 是否大部分?jǐn)?shù)據(jù)距離他們 的正確位置很近？是否近乎有序淋纲？-->插入排序
• 是否數(shù)據(jù)的取值范圍非常有限？比如學(xué)生成績排序。-->計數(shù)排序
• 是否需要穩(wěn)定鳞陨？-->優(yōu)先考慮歸并
• 是否使用鏈表存儲？-->鏈表歸并排序或者鏈表快速排序（關(guān)于鏈表的排序近期會有更新）
• 數(shù)據(jù)的大小是否可以裝載到內(nèi)存中瞻惋？-->外排序

/**
 *  冒泡排序：
 *
 *  時間復(fù)雜度：
 *      O(n)^2
 *  空間復(fù)雜度：
 *      O(1)
 *  穩(wěn)定性：
 *      穩(wěn)定
 *
 *  以升序情況下為例：
 *  1.首先指針指向數(shù)組中的第一個元素厦滤，讓當(dāng)前元素和他后一個元素做比較，
 *      如果比后一個元素大的話歼狼，交換兩個元素的位置掏导。
 *  2.指針向后挪動一個單位，繼續(xù)重復(fù)上面的的步驟羽峰，直到指針走到數(shù)組長度減一的位置趟咆，
 *        那個此時數(shù)組中的最大值就是數(shù)組中的最后一個元素，
 *  3.數(shù)組的長度減一梅屉，繼續(xù)重復(fù)上面的動作值纱，直到數(shù)組的長度為1的時候結(jié)束。
 *
 *  缺點：
 *      可能在數(shù)組長度不到1的時候坯汤，序列就已經(jīng)有序了虐唠，所以，
 *      增加一個標(biāo)志位惰聂，如果在發(fā)生交換疆偿，更改標(biāo)志位，
 *      一次排序后搓幌，判斷標(biāo)志位是否更改杆故，如果沒有更改代表排序已經(jīng)完成
 */
void bubble_sort(int arr[], int len){
    int flag = 1;
    for (int i = 0;flag && i < len - 1; i++){
        flag = 0;
        for (int j = i; j < len-1-i; j++){
            if (arr[j]>arr[j + 1]){
                flag = 1;
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

/**
 *  插入排序：
 *
 *  時間復(fù)雜度：
 *      O(n)^2
 *  空間復(fù)雜度：
 *      O(1)
 *  穩(wěn)定性：
 *      穩(wěn)定
 *  
 *  是升序情況為例：
 *  將數(shù)組分成有序和無序兩部分，每次從無序的數(shù)組中取出一個元素插入到有序的那部分中
 * 
 */

void insert_sort(int data[], int len){
    for (int i = 0; i < len - 1; i++){
        int temp = data[i + 1];
        int j = i;
        while (j >= 0 && data[j]>temp){
            data[j + 1] = data[j];
            j--;
        }
        data[j + 1] = temp;
    }
}

/**
*   選擇排序：
*
*   時間復(fù)雜度：
*       O(n)^2
*   空間復(fù)雜度：
*       O(1)
*   穩(wěn)定性：
*       不穩(wěn)定
*
*   是升序情況為例：
*   它的工作原理是每一次從待排序的數(shù)據(jù)元素中選出最懈瘸睢（或最大）的一個元素处铛，
*   存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完
*/
void select_sort(int data[], int len){
    int min;
    for (int i = 0; i < len-1; i++){
        int min = i;
        for (int j = i + 1; j < len; j++){
            if (data[min]>data[j]){
                min = j;
            }
        }
        if (min != i){
            int temp = data[i];
            data[i] = data[min];
            data[min] = temp;
        }
    }
}
/**
 *  歸并排序：
 *
 *  時間復(fù)雜度：
 *      O(n log n)
 *  空間復(fù)雜度：
 *      O（n)
 *  穩(wěn)定性：
 *      穩(wěn)定
 *
 *  該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用。
 *  將已有序的子序列合并撤蟆，得到完全有序的序列篙贸；
 *  即先使每個子序列有序，再使子序列段間有序枫疆。若將兩個有序表合并成一個有序表
 */

void array_merge(int data[], int low, int mid, int high){
    int len = high - low;
    int *p = (int*)malloc(sizeof(int)*len);
    int i = low, j = mid, k = 0;
    while (i < mid&&j < high){
        if (data[i] < data[j]){
            p[k++] = data[i++];
        }
        else{
            p[k++] = data[j++];
        }
    }
    while (i < mid){
        p[k++] = data[i++];
    }
    while (j < high){
        p[k++] = data[j++];
    }
    for (int i = 0, j = low; i < k; i++){
        data[j++] = p[i];
    }
    free(p);
}
void merge_sort(int data[], int low, int high){
    if (NULL == data || low < 0 || high <= 0||low>=high){
        return;
    }
    if (high - low == 1){
        return;
    }
    int mid = (high + low) / 2;
    merge_sort(data, low, mid);
    merge_sort(data, mid , high);
    array_merge(data, low, mid, high);
}

/**
 *
 *  快速排序：
 *
 *  時間復(fù)雜度：
 *      O(n log n)
 *  空間復(fù)雜度：
 *      O（n)
 *  穩(wěn)定性：
 *      不穩(wěn)定
 *
 *  首先確定一個基準(zhǔn)值爵川，通過比較和交換，使得基準(zhǔn)值左邊的數(shù)字都比基準(zhǔn)值小
 *  基準(zhǔn)值右邊的數(shù)都比基準(zhǔn)值大息楔，然后以基準(zhǔn)值為分割點寝贡，分成三部分，分別進(jìn)行左遞歸和右遞歸進(jìn)行排序值依。
 *
 *
 *  缺點：
 *  傳統(tǒng)基準(zhǔn)值的選定時每次參照順序表的第一個元素作為基準(zhǔn)值圃泡，
 *  但是如果數(shù)組為有序的情況下，會大大降低排序效率愿险，退化成冒泡排序時間復(fù)雜度升為O(n^2)
 *  解決方案就是三數(shù)取中颇蜡。
 *
 *
 *  優(yōu)化1：
 *      當(dāng)待排序序列的長度分割到一定大小后，使用插入排序
 *  原因：
 *      對于很小和部分有序的數(shù)組辆亏，快排不如插排好风秤。
 *      當(dāng)待排序序列的長度分割到一定大小后，繼續(xù)分割的效率比插入排序要差扮叨，此時可以使用插排而不是快排缤弦。
 *
 *  優(yōu)化2：
 *      在一次分割結(jié)束后，可以把與Key相等的元素聚在一起彻磁，繼續(xù)下次分割時辰晕，不用再對與key相等元素分割
 *      在一次劃分后壳咕，把與key相等的元素聚在一起微王，能減少迭代次數(shù)判呕，效率會提高不少
 *      具體過程：在處理過程中，會有兩個步驟
 *      第一步磁浇，在劃分過程中斋陪，把與key相等元素放入數(shù)組的兩端
 *      第二步，劃分結(jié)束后扯夭，把與key相等的元素移到樞軸周圍
 */

void swap(int *a, int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
}
//三數(shù)取中：先找到一個最大值放到data[len-1]的位置鳍贾，
//之后mid值通過data[low]和data[mid]確定
int midAndSwap(int data[], int low, int high){
    if (NULL == data || low < 0 || high <= 0){
        return 0;
    }
    int mid = (high - low) / 2 + low;
    if (data[low]>data[high - 1]){
        swap(&data[low], &data[high - 1]);
    }
    if (data[mid] > data[high - 1]){
        swap(&data[mid], &data[high - 1]);
    }
    if (data[low] < data[mid]){
        swap(&data[low], &data[mid]);
    }
    return data[low];
}
void insertSort(int data[], int len){
    for (int i = 0; i < len - 1; i++){
        int temp = data[i + 1];
        int j = i;
        while (j >= 0 && data[j]>temp){
            data[j + 1] = data[j];
            j--;
        }
        data[j + 1] = temp;
    }
}

void quickSort(int data[], int low, int high){
    //轉(zhuǎn)換成插入排序數(shù)組的長度為（5<len<15）
    if ((high - low) < 2){
        insertSort(data + low, high - low);
        return;
    }

    int left = low;
    int right = high - 1;

    int leftCopy = left;
    int rightCopy = right;

    int key = midAndSwap(data, low, high);
    while (left < right){
        for (; left < high&&data[left] <= key; left++){
            if (key == data[left]){
                swap(&data[left], &data[leftCopy]);
                leftCopy++;
            }
        }
        for (; right >= left&&data[right] >= key; right--){
            if (key == data[right]){
                swap(&data[right], &data[rightCopy]);
                rightCopy--;
            }
        }
        if (left < right){
            int temp = data[left];
            data[left] = data[right];
            data[right] = temp;
        }
    }
    //將樞紐元素移動到中間位置
    left = right;
    while (leftCopy - low){
        swap(&data[--leftCopy], &data[left--]);
    }
    if (right - left){
        right++;
    }
    while (high - 1 - rightCopy){
        swap(&data[++rightCopy], &data[right++]);
    }
    quickSort(data, low, left + 1);
    quickSort(data, right, high);
}


/**
 *  堆排序
 *
 *  時間復(fù)雜度：
 *    O(n log n)
 *  空間復(fù)雜度：
 *    O（1)
 *  穩(wěn)定性：
 *    不穩(wěn)定
 *
 *  堆排序的基本思想是：將待排序序列構(gòu)造成一個小根堆，此時交洗，整個序列的最小值就是堆頂?shù)母?jié)點。
 *  將其與末尾元素進(jìn)行交換橡淑，此時末尾就為最小值构拳。
 *  然后將剩余n-1個元素重新構(gòu)造成一個堆，這樣會得到n個元素的次小值。
 *  如此反復(fù)執(zhí)行置森，便能得到一個有序序列了斗埂。
 *  
 *  參考博客：https://www.cnblogs.com/chengxiao/p/6129630.html
 */
void heap_sort(int data[], int len){
    if (data == NULL || len <= 0){

    }
    int pa, tag , end = len;
    //end-1解釋： 在數(shù)組中只剩下一個元素的時候不用比較
    while (end - 1){
        tag = 1;
        while (tag){
            pa = end / 2;
            tag = 0;
            while (pa){
                if (data[pa] < data[2 * pa]){
                    swap(&data[pa], &data[2 * pa]);
                    tag = 1;
                }
                if (2 * pa + 1 <= end&&data[pa] < data[2 * pa + 1]){
                    swap(&data[pa], &data[2 * pa + 1]);
                    tag = 1;
                }
                pa--;
            }
        }
        swap(&data[1], &data[end--]);
    }
}

/**
 *  計數(shù)排序：
 *  
 *  時間復(fù)雜度：
 *      O(n)
 *  空間復(fù)雜度：
 *      O（1)
 *  穩(wěn)定性：
 *      不穩(wěn)定
 *  
 *  適合數(shù)據(jù)特別集中的情況。
 *  這里以升序凫海，且數(shù)據(jù)范圍在0-100之間的數(shù)
 *  根據(jù)獲得的數(shù)據(jù)表的范圍呛凶，分割成不同的100個桶，
 *  然后直接統(tǒng)計數(shù)據(jù)在桶上的頻次行贪，然后順序遍歷桶就可以得到已經(jīng)排好序的數(shù)據(jù)表漾稀。
 *      
 */
void count_sort(int data[], int len){
    if (NULL == data || len <= 0){
        return;
    }
    int table[100] = { 0 };
    for (int i = 0; i < len; i++){
        table[data[i]]++;
    }
    int index = 0;
    for (int i = 0; i < 100; i++){
        while (table[i]){
            data[index++] = i;
            table[i]--;
        }
    }
}
/*
    希爾排序：

    時間復(fù)雜度：
        O(n)
    空間復(fù)雜度：
        O(1)
    穩(wěn)定性：
        不穩(wěn)定

    比較相隔較遠(yuǎn)距離（稱為增量）的數(shù)，使得數(shù)移動時能跨過多個元素建瘫，
    則進(jìn)行一次比較就可能消除多個元素交換崭捍。
    算法先將要排序的一組數(shù)按某個增量d分成若干組，每組中記錄的下標(biāo)相差d.對每組中全部元素進(jìn)行排序啰脚，
    然后再用一個較小的增量對它進(jìn)行殷蛇，在每組中再進(jìn)行排序。
    當(dāng)增量減到1時橄浓，整個要排序的數(shù)被分成一組粒梦，排序完成。
*/

/**
 *  外排序
 *
 *  基本要點：
 *      外部排序顧名思義是對外部存儲空間中數(shù)據(jù)的排序荸实，那為什么不能像選擇排序谍倦、插入排序、快速排序那樣也直接進(jìn)行排序呢泪勒？
 *      原因是外部存儲的數(shù)據(jù)量可能是非常大的昼蛀，而計算機(jī)的內(nèi)存大小要遠(yuǎn)遠(yuǎn)小于外存，計算機(jī)一下子讀不了那么多數(shù)據(jù)圆存，
 *      無法一次性對它們進(jìn)行排序叼旋，這就是外部排序產(chǎn)生的原因。
 *  基本思想：
 *      1.  我們這里借助歸并排序的思想
 *      假設(shè)我的一個文件中有10000個數(shù)據(jù)沦辙，而我的內(nèi)存每次只能讀2000個數(shù)據(jù)夫植，那我先對文件預(yù)處理一下，將原文件切割成5個小文件油讯，
 *      每個文件中有2000個有序數(shù)據(jù)（在讀入內(nèi)存2000個數(shù)據(jù)后详民，對數(shù)據(jù)排序后再寫入到新文件中）。
 *      2.  然后我們開始進(jìn)行文件合并（這里采用2-路歸并）陌兑。先分別打開兩個文件沈跨，分別讀取文件的第一行數(shù)據(jù)，
 *      把數(shù)據(jù)較小的寫入到一個新文件中兔综，然后把數(shù)據(jù)較小的文件再往下讀一行饿凛，直到兩個文件中的數(shù)據(jù)全部有序地寫到新文件中為止狞玛，
 *      這樣原先5個2000個數(shù)據(jù)的文件變?yōu)?個4000個數(shù)據(jù)和1個2000個數(shù)據(jù)的文件。
 *      3.  重復(fù)步驟2涧窒，再次合并變?yōu)?個8000個數(shù)據(jù)和1個2000個數(shù)據(jù)的文件心肪，
 *      再次合并變?yōu)?個10000個數(shù)據(jù)的文件。排序完成纠吴，原先有10000個數(shù)據(jù)的文件變得有序硬鞍。
 *
 */