冒泡排序

冒泡排序是比較簡(jiǎn)單的O(n2)級(jí)別的排序算法，思路是挨個(gè)比較鄰近的數(shù)值，然后交換位置，就像在水里的泡泡一樣，總能把最大的或者最小的交換到最上層。

/**
 * 冒泡排序
 */
template<typename T>
void bubble_sort(T arr[], int length)
{
    for (int i=0; i< length-1; i  ){

        for(int j=0; j< length-1-i; j  ){
            if (arr[j] > arr[j 1]){
                swap(arr[j], arr[j 1]);
            }
        }

    }
}

選擇排序

選擇排序的算法級(jí)別也是O(n2)，思路是從第一個(gè)索引開始，與剩下的進(jìn)行比較，并記錄最下的值的索引，依次比較下去。如果當(dāng)前索引和初始的索引不同，那么需要交換值。此時(shí)最小的元素排在了前面。然后依次類推。

/**
 *選擇排序
 */
template<typename T>
void select_sort(T arr[], int length){
    for (int i=0; i<length-1; i  ){
        int minIndex = i;
        for(int j = i 1; j<length; j  ){
            if(arr[minIndex] > arr[j]){
                minIndex = j;
            }
        }
        if(minIndex!=i){
            swap(arr[i], arr[minIndex]);
        }
    }
}

插入排序

插入排序，假設(shè)前面的數(shù)據(jù)是排列完整的，那么需要把當(dāng)前的值與它前面的依次比較，直到遇到大于的位置，然后插入到其中。一般實(shí)現(xiàn)的時(shí)候可以選擇依次交換位置，也可以進(jìn)行賦值。
具體實(shí)現(xiàn)如下：

/**
 * 插入排序  交換數(shù)值
 */
template <typename T>
void insert_sort(T arr[], int length){
    for(int i=0; i< length -1; i  ){
        for (int j = i 1; j>0 && (arr[j-1] > arr[j]); j--){
            //if (arr[j-1] > arr[j]){
                swap(arr[j-1], arr[j]);
           // }
        }
    }
}

可以對(duì)其進(jìn)行優(yōu)化，不需要每次都進(jìn)行交換鄰近，這樣勢(shì)必會(huì)浪費(fèi)空間和時(shí)間，可以賦值操作

template <typename T>
void insert_sort2(T arr[], int length){
    for(int i=1; i< length; i  ){
        T val = arr[i]; // 當(dāng)前元素的值
        int j;
        for(j=i; j>0 && val < arr[j-1]; j--){
            arr[j] = arr[j-1]; // 向前移動(dòng)
        }
        if(j!=i){
            arr[j] = val;
        }
    }
}

從代碼中也可以看出，插入排序?qū)Υ蟛糠峙藕玫男蛄惺呛芸斓摹?/p>

希爾排序

插入排序是采用1步長(zhǎng)進(jìn)行排序的，而希爾排序在插入排序的基礎(chǔ)上，先采用大步長(zhǎng)，只到1步長(zhǎng)為止，思想從整體上使得序列基本有序。

/**
 *希爾排序
 *
 */
template <typename T>
void shell_sort(T arr[], int length){
    int gap = 1;
    while (gap < length / 3) {
       gap = 3 * gap   1;
    }
    cout << "gap = " << gap << endl;
    // 間隔Gap 進(jìn)行插入排序
    while (gap>0) {
    	// 這里其實(shí)就是插入排序，只是以gap為間隔進(jìn)行排序
        for(int i = 0; i <length; i  = gap){
            for(int j= i   gap; j > 0 && (arr[j] < arr[j-gap]); j -= gap){
                 swap(arr[j], arr[j-gap]);
            }
        }
        gap = gap/3;
    }
}

歸并排序

就是不斷的把一個(gè)數(shù)組，對(duì)半分成兩份，只到最后不能再分，然后再向上進(jìn)行排序合并，典型的遞歸的思想

/**
 *歸并排序
 *  分為左右，然后排序，然后合并 開辟臨時(shí)內(nèi)存空間
 */
template <typename T>
void merge_sort(T arr[], int length){
    __merge_sort(arr, 0, length-1);
}

template <typename T>
void __merge_sort(T arr[], int l, int r){
    if (l >=r){
        return;
    }

    int mid = l   (r-l) /2;  //(r l)/2;
    __merge_sort(arr, l, mid);
    __merge_sort(arr, mid 1, r);

    // [l, mid] [mid 1, r]
    T * aux = new T[r-l 1];
    for(int i=l; i<=r; i  ){
        aux[i-l] = arr[i];
    }

    int i = l, j = mid 1;
    for(int k = l; k <= r; k  ){
        if (i > mid){
            arr[k] = aux[j-l]; // 復(fù)制剩下的右半邊
            j  ;
        }else if (j > r){
            arr[k] = aux[i-l]; // 復(fù)制剩下的左半邊
            i  ;
        }else if(aux[i-l] < aux[j-l]){
            arr[k] = aux[i-l]; // 復(fù)制左半邊
            i  ;
        }
        else{
            arr[k] = aux[j-l]; // 復(fù)制右半邊
            j  ;
        }
    }

    delete[] aux;

}

快速排序

快速排序的思想也是分而治之，首選需要選擇一個(gè)基本值，然后小于基本值的在數(shù)組的左半邊，大于的在右半邊，中間部分是基本值，然后依次在對(duì)基本值的左邊遞歸，對(duì)右半邊也遞歸。

/**
 *快速排序  需要選擇基準(zhǔn)的數(shù)據(jù)，默認(rèn)第一個(gè)，也可以隨機(jī)選擇
 */
template<typename T>
void quick_sort(T arr[], int length){
    __quick_sort(arr, 0, length-1);
}

template<typename T>
void __quick_sort(T arr[], int l, int r){
    if(l >= r)
    {
        return;
    }
    int index = __partition(arr, l, r);
    __quick_sort(arr, l, index-1);
    __quick_sort(arr, index 1, r);

}
template <typename T>
int __partition(T arr[], int l, int r){
    // 從兩端向內(nèi)
    //int index = rand()%(r-l 1) l;
    //swap(arr[l], arr[index]);
    T v = arr[l]; // 選擇第一個(gè)為基準(zhǔn)值，也可隨機(jī)選擇，然后交換再進(jìn)行
    int i = l   1, j = r;

    while( true ){
        // 注意這里的邊界, arr[i] < v, 不能是arr[i] <= v
        while( i <= r && arr[i] < v )
            i   ;

        // 注意這里的邊界, arr[j] > v, 不能是arr[j] >= v
        while( j >= l 1 && arr[j] > v )
            j --;

        if( i > j )
            break;

        swap( arr[i] , arr[j] );
        // 注意這里的交換完，需要都向前移動(dòng)一位
        i   ;
        j --;
    }

    swap(arr[l], arr[j]);
    return j;

堆排序

首先要了解什么是堆，堆其實(shí)就是一個(gè)二叉樹，分為大頂推和小頂推，由小到大排序，一般小頂推。小頂堆的父節(jié)點(diǎn)的值小于兩個(gè)孩子節(jié)點(diǎn)的值。具體可以去看堆的定義，這里就不多說了。

/**
 * 對(duì)元素組的堆排序
 */
template<typename T>
void heap_sort(T arr[], int length){
	// 構(gòu)建堆
    for(int i = (length-1)/2; i >= 0; i--){
        __siftDown(arr, length, i);
    }

    for(int i = length-1; i >= 0; i--){
        swap(arr[0], arr[i]);
        __siftDown(arr, i, 0);
    }
}
template<typename T>
void __siftDown(T arr[], int length, int k){

    while ( 2*k 1 < length) {

        int i = 2*k   1;
        if(i 1<length && arr[i] < arr[i 1]){
            i   ;
        }

        if(arr[k] >= arr[i])
            break;

        swap(arr[k], arr[i]);

        k = i;
    }
}

參考：https://www.runoob.com/w3cnote/ten-sorting-algorithm.html