資料結構與算法二 排序

• 希爾排序
• • 原理——分組
  • • 代碼實作
• 快速排序
• • 原理——大數在基準數右邊，小數在基準數左邊
  • • 代碼實作
• KMP算法
• • 原理

希爾排序

原理——分組

希爾排序在數組中采用跳躍式分組的政策，通過某個增量将數組元素劃分為若幹組，然後分組進行插入排序，随後逐漸縮小增量，繼續按組進行插入排序操作，直至增量為1。

希爾排序的基本步驟，在此我們選擇增量gap=length/2，縮小增量繼續以gap = gap/2的方式，這種增量選擇我們可以用一個序列來表示，{n/2,(n/2)/2…1}，稱為增量序列。

代碼實作

/*
功能：實作希爾排序
@param: data：待排序的資料的位址
		length：資料的長度
*/
int shell_sort(int *data, int length) {

    int gap = 0; //分組的跨度
    int i = 0, j = 0;

    for (gap = length / 2; gap >= 1;gap /= 2) { // 分組的次數

        for(i = gap; i < length; i ++) { // 每組周遊 

            int temp = data[i];
            for (j = i - gap; j >= 0 && temp < data[j];j = j - gap) { //組内排序

                data[j+gap] = data[j];

            }

            data[j+gap] = temp;
        }

    }
    return 0;
}
           

參考_希爾排序

快速排序

原理——大數在基準數右邊，小數在基準數左邊

任意選取一個資料（通常選用數組的第一個數）作為關鍵資料，然後将所有比它小的數都放到它左邊，所有比它大的數都放到它右邊，這個過程稱為一趟快速排序。（設兩個訓示标志: i 指向起始位置，j 指向末尾，來幫助尋找大數和小數）

代碼實作

/*
功能：實作快速排序
參數： data：待排序資料的位址
	  left：左标志，通常也設為基準值，找比基準值大的數
	  right：右标志, 找比基準值小的數
*/
int sort(int *data, int left, int right) { //每一次遞歸， 每調用一次， 确定一個值得正确位置

    if (left >= right) return 0;

    int i = left;
    int j = right;
    int key = data[left];

    while (i < j) { //

        while (i < j && key < data[j]) { // 
            j --;
        }
        data[i] = data[j];

        while (i < j && key >= data[i]) {
            i ++;
        }
        data[j] = data[i];
    }
    // i == j
    data[i] = key;

    //
    sort(data, left, i-1);
    sort(data, i+1, right);

}
           

KMP算法

解決的問題：在一個字元串(n)中尋找一個子串(m)第一個位置。

原理