說明

本文參考極客時間—王爭·數(shù)據(jù)結(jié)構(gòu)與算法之美。

個人覺得王爭講得很好，圖也很形象。

這里很多字都沒有打進來，我覺得配合圖片和代碼，應該可以了解這個思想了。

如果有需要，大家可以去聽一聽。

大綱

冒泡排序

void bubbleSort(int *a, int n)
{
    if(n <= 1) return;
    for(int i = 0; i < n; i++){
        bool flag = false;   //flag是判斷是否無序的標志位
        for(int j = 0; j < n-i-1; j++){
            if( a[j] > a[j+1] ){
                swap( a[j] , a[j+1] );
                flag = true;
            }
        }
        if(!flag) break;
    }
}

圖解

第一次冒泡

冒泡過程：

img

插入排序

插入的過程與冒泡的不一樣，插入進行的是比較-幅值，冒泡進行的是比較-交換。

因此插入的效率比冒泡要高。

void insertSort(int *a, int n)
{
    if( n <= 1) return;
    for(int i = 1; i < n; i++){
        int value = a[i];   //value是當前待插入的數(shù)
        int j = i-1;
        for(；j >= 0; j--){  //j是遍歷value前面的數(shù)
            if( a[j] > value ){
                a[j+1] = a[j];
            }
        }
        a[j+1] = value;
    }
}

圖解

插入過程

選擇排序

選擇排序算法的實現(xiàn)思路有點類似插入排序，也分已排序區(qū)間和未排區(qū)間。但是選擇排序每次會從未排序區(qū)間中找到最小的元素，將其放到已排序區(qū)間的末尾。

圖解

選擇排序過程

快速排序

快速排序用的是分治思想，因此可以用遞歸算法來實現(xiàn)。

int partition(int *a, int p, int r)
{
    int pivot = a[r];   //value可以選取得盡量隨機
    int i = p;
    for(int j = p; j < r; j++){
        if( a[j] < value ){
            swap( a[i] , a[j] );
            i++;
        }
    }
    swap( a[i] , a[r] );
    return i;
}

void quickSort(int *a, int p, int r)
{
    if( p >= r) return;
    int q;
    q = partition(a,p,r);
    quickSort(a,p,q-1);
    quickSort(a,q+1,r);
}

圖解

partition函數(shù)過程

歸并排序

void merge(int *a, int p, int r, int q)
{
    int *tmp = new int[r-p+1];
    int i = p;
    int j = q + 1;
    int k = 0;
    while( i <= q && j <= r){
        if( a[i] <= a[j])
            tmp[k++] = a[i++];
        else
            tmp[k++] = a[j++];
    }
    int start = j;
    int end = r;
    if(i <= q){
        start = i;
        end = q;
    }
    while( start <= end )
        tmp[k++] = a[start++];
    for(int n = 0; n < r-p+1; n++)
        a[p+n] = tmp[n];
    delete[] tmp;
}

void mergeSort(int *a, int p, int r)
{
    if( p >= r) return;
    int q = (p+r)/2;
    mergeSort(a,p,q);
    mergeSort(a,q+1,r);
    
}

圖解

思路

merge函數(shù)過程

（持續(xù)更新中......）

參考資料

極客時間-王爭·數(shù)據(jù)結(jié)構(gòu)與算法之美https://time.geekbang.org/column/article/0?cid=126