簡單排序

資料結構與算法的遊戲從簡單排序開始
- 選擇排序
- 冒泡排序
- 插入排序
- 希爾排序
- 簡單排序性能PK賽

資料結構與算法的遊戲從簡單排序開始

簡單排序是排序算法中基礎的部分，這部分算法都是屬于O(n2)的算法，雖然從數量級上看時間消耗要比後續的O(nlog(n))級别的算法要慢，但實際表現卻不見得；特别是優化過後的插入排序，在對基本有序序列的排序的時耗很低，甚至可以超越Onlog(n)級别的算法；怎麼實作呢，我們逐個來看看(各排序耗時PK在最後)~~

選擇排序

選擇排序的主體實作思路：從數組的第一個成員開始逐個周遊，找到最小那個放到第一個位置，以此類推；

// 選擇排序
// 這裡設定了泛型(如對泛型不了解，可以簡單了解為int)
template<typename DT>
void selectSort(DT arr[], int n) {
    for(int i=0; i<n; i++) {
        int minIndex = i;
        for(int j=i; j<n; j++) {
            if(arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        swap(arr[i], arr[minIndex]);
    }
}

簡單排序的優化實作：一次性找到最大和最小值

// 選擇排序
template<typename DT>
void selectSort(DT arr[], int n) {
	// 設定初始左邊界和右邊界
    int left = 0;
    int right = n-1;
    // left < right說明序列還有成員未排序，循環
    while(left < right) {
        int minIndex = left;
        int maxIndex = right;
//      先将目前判斷的頭尾兩個值的大小設定好
        if(arr[minIndex] > arr[maxIndex]) {
            swap(arr[minIndex],arr[maxIndex]);
        }
//      一次周遊擷取目前最大或最小值，目前左右邊界為未排序區間，
        for(int i=left+1;i<right;i++) {
            if(arr[i] < arr[minIndex]) {
                minIndex = i;
            } else if(arr[i] > arr[maxIndex]) {
                maxIndex = i;
            }
        }
        swap(arr[minIndex],arr[left]);
        swap(arr[maxIndex],arr[right]);

        left++;
        right--;
    }
}

冒泡排序

冒泡排序的主體實作思路：從第一個數組成員開始，從左到右兩兩比較，如果出現前面的成員資料比後面的小則交換資料，周遊一次就能在右邊界處放置最大值，然後右邊界減1，繼續周遊直到數組有序；這裡有一個小技巧，就是設定一個标記，如果在一次周遊中沒有進行一次資料交換，說明序列已有序，那麼就可以通過這個标記判斷是否在一次周遊中有出現資料交換了，具體實作滑鼠滾起來；

//冒泡排序法
template <typename T>
void bubbleSort(T arr[], int n) {
    // 設定标記
    bool swapped;
    //  如果一次循環過程中，沒有一次成員資料交換，說明序列已有序
    do {
        swapped = false;
        for (int i = 0; i < n-1; i++) {
            if (arr[i] > arr[i + 1]) {
                swap(arr[i], arr[i + 1]);
                swapped = true;
            }
        }
    // 标記是否改為true，判斷是否需要繼續循環排序
    }while(swapped);
}

冒泡排序的優化實作：記錄上一次排序最後出現有成員資料交換的位置作為右邊界，因為右邊界後續的序列已有序

//冒泡排序法
template <typename T>
void bubbleSort(T arr[], int n) {
    //  bool swapped;
    //  将bool swapped優化為int lastSwapped，記錄最後一次交換的位置，而不是記錄是否有交換
    //	在交換的過程中，可能隻在中間進行了交換，這樣就說明後面的序列已經有序，不用再比較了
    int lastSwapped;
    do {
        //swapped = false;
        lastSwapped = 0;
        for (int i = 0; i < n-1; i++) {
            if (arr[i] > arr[i + 1]) {
                swap(arr[i], arr[i + 1]);
                lastSwapped = i+1;
            }
        }
        //	更新右邊界，有邊界往後序列已有序
        n = lastSwapped;
    }while(lastSwapped > 0);
}

插入排序

插入排序的主體實作思路：來來來，打牌！這就是一個打牌排序法，打牌的時候，一般習慣就是把同花色的牌放一起，而且會從左到右按序拿着，回想一下這個過程，會發現是摸一張就将這張插入到該在的位置；插入排序也就是從左到右周遊，一邊周遊，一邊将右邊周遊到序列成員插入到左邊已經排好序的序列中

//插入排序法
template <typename T>
void insertSort(T arr[], int n) {
	//	i作為右邊待排序的序列成員，j作為左邊已有序的序列的右邊界
    for(int i=1;i<n;i++) {
    	//	插入過程，從左邊序列的右邊開始比較，左邊比右邊大就交換
        for(int j=i;j>0;j--) {
            if(arr[j] < arr[j-1]) {
                swap(arr[j],arr[j-1]);
            } else {
                break;
            }
        }
    }
}

插入排序的優化實作：基礎版的插入排序實作起來很簡單，但是有一個弊端，試想一下打牌的時候，為了把新摸的牌放到這牌該在的位置，會不會在手中的牌從右到左一個個位置插過來，直到這個牌到位了呢？那是一個連想想都覺得尴尬的舉動，是以實際實作時大可減少這些不必要的資料交換，這就使得插入排序的效率得到了質的飛躍，在面對基本有序的序列時，插入排序甚至幹掉了複雜的O(nlog(n))級别的算法；

//插入排序法
template <typename T>
void insertSort(T arr[], int n) {
    for(int i=1;i<n;i++) {
//      改成每次插入比較時，隻将較大的值往後挪，而插入的值先記着，找到位置再插入
		//	記錄需插入序列成員
        T candidate = arr[i];
//      注意這裡j要在外面聲明，如果在for裡面聲明j隻在for内部可見
        int j;
        // if-else可以整合到for循環中，後續希爾排序有類似整合
        for(j=i;j>0;j--) {
        	// 需插入資料不是目前最大值時，不再交換，而是讓目前對比的大數後移
            if(arr[j-1] > candidate) {
                arr[j] = arr[j-1];
            //	需插入資料已經找到位置了，跳出循環
            } else {
                break;
            }
        }
        //	将資料插入
        arr[j] = candidate;
    }
}

希爾排序

希爾排序的主體實作思路：插入算法的黃金馬甲，以低耗時的周遊查詢次數換取更為耗時的資料指派次數的減少；前面的三種排序，序列中一個成員要到有序的位置必須進行逐個比較，比較後，如果發現位置要變，則必定會出現資料的交換或至少是指派(挪位)；然而如果知道最後一個(或靠後)資料是最小的(或幾乎最小的)，那麼最好的做法肯定就是直接跳過和中間序列成員的比較，将後面這個成員跳到前面去比較，這樣就減少了很多不必要的挪位；希爾算法就是通過先以大間隔進行比較，讓遠離有序位置的成員跳躍性地進行比較到所需位置的附近，從大間隔的比較然後逐漸到間隔為1的比較，進而達到序列有序；這個過程雖然增加了查詢次數，但是因為查詢比指派耗時要低很多，是以實際意義很大；但需要注意的時候在面對基本有序序列時，插入排序仍然最優，因為面對基本有序序列，插入排序的機制讓插入排序隻需比較，很少指派，而希爾排序增加的查詢時間在這個時候就不夠給力了，那基本有序到什麼程度呢，我肯定不會告訴你大概時100000個資料中隻有200個資料未排好序時，超過了時還是希爾牛；

// 希爾排序法
template<typename T>
void shellSort(T arr[], int n) {
    // 計算 increment sequence: 2, 4, 8, 16, 32, 64, 128...
    int D = 2;
    while( D < n/2 ) {
        D *= 2;
    }
    while(D >= 1) {
        // 開始插入排序，對每個資料逐個按D個間隔進行排序，對于0到D的資料，在下面的for循環中考慮進去了
        for(int i=1;i<n;i++) {
            T candidate = arr[i];
            int j;
            //	差別與正常的插入排序，這裡比較插入時不是直接以1的間隔比較，而是按D的區間進行比較
            for(j=i;j>=D && candidate<arr[j-D];j-=D) {
                arr[j] = arr[j-D];
            }
            arr[j] = candidate;
        }
        D /= 2;
    }
}

希爾排序的優化實作：希爾排序本身已經優化後的，但是大神的世界沒有足夠優化的說法，之前用于增加排序間隔的序列時随意用2的幂次來擷取的(也可以自己搞個什麼序列)，但是随便搞的序列有個問題，就是可能會導緻重複查詢，如在8的間隔時已經對比過第4個和第12個序列成員了，到了4的間隔時，會對比第4個，第8個，第12個序列成員，這樣通過第8個成員，第4個和第12個又比了一次，Sedgewick增量序列則很好地解決了這個問題；

簡單排序(C++)-- 資料結構與算法的遊戲開始資料結構與算法的遊戲從簡單排序開始

// 希爾排序法
template<typename T>
void shellSort(T arr[], int n) {
	//	Sedgewick序列，值示範了17個，适用于最多100萬個資料的序列
    int SedgewickSeq[17] = {1,5,19,41,109,209,505,929,2161,3905,8929,16001,36289,64769,146305,260609,587521};
    int index = 16;
    //while(D >= 1) {
    while(index >= 0) {
        int D = SedgewickSeq[index];
        // 開始插入排序，對每個資料逐個按D個間隔進行排序，對于0到D的資料，在下面的for循環中考慮進去了
        for(int i=1;i<n;i++) {
            T candidate = arr[i];
            int j;
            for(j=i;j>=D && candidate<arr[j-D];j-=D) {
                arr[j] = arr[j-D];
            }
            arr[j] = candidate;
        }
        //D /= 3;
        index--;
    }
}

簡單排序性能PK賽

比賽規則：

對10萬個資料進行排序；
分随機數序列和基本有序序列兩場比賽；
基本有序序列的未有序資料數量是200個；
所有排序法均已優化；
從上到下是選擇排序、冒泡排序、插入排序、希爾排序；

随機數序列：
selectSort:5.686
bubbleSort:34.211
insertSort:5.556
shellSort:0.019
基本有序序列：
selectSort:5.711
bubbleSort:0.975
insertSort:0.005
shellSort:0.006

比賽結果：

無論序列怎麼變，希爾基本完勝，除了在基本有序上稍遜插入排序一點點；
原始三大簡單排序優化後的插入排序最優；
選擇排序在随機數序列上表現突出，冒泡排序則在基本有序上可圈可點；
插入排序無論是在查詢還是指派的次數上都少于另外兩種原始簡單排序；選擇排序不管是否基本有序都要進行那麼多的查詢，是以耗時穩定；冒泡排序資料交換很多，查詢較少，是以對随機序列略顯乏力，對基本有序序列因資料交換大量減少，性能大幅提升；
比賽結果供菜鳥參考，大神點評；

簡單排序(C++)-- 資料結構與算法的遊戲開始資料結構與算法的遊戲從簡單排序開始

簡單排序

資料結構與算法的遊戲從簡單排序開始

選擇排序

冒泡排序

插入排序

希爾排序

簡單排序性能PK賽

繼續閱讀

極大似然法(ML)與最大期望法(EM)

shell排序基本思想及其複雜度分析

C++ 第十五周報告1--《冒泡法排序》

[轉]九大排序算法——C語言實作及詳解

C++實作簡單順序表

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述

Linux裝置模型（中）之上層容器

hdu7108哈希