第 7 章　排序

7.1　搜尋與串列驗証

「因為不同的應用可以使用相同的串列，故鍵值欄位也是根據不同的應用而定。舉例而言，如果我們有一電話號碼串列，如果要找到電話號碼 456-1023，電話號碼欄即為鍵值。反之，如果想要找出 Joan Smith 是否在目錄中，姓名欄即為鍵值。」

7.1.2　循序搜尋 (Sequential Search)

#define MAX_SIZE 1000 /*maximum size of list plus one*/
typedef struct {
        int key;
        /* other fields */
        } element;
element list[MAX_SIZE];

int seqsearch(int list[], int searchnum, int n)
{
/*search an array, list, that has n numbers. Return i, if
list[i] = searchnum.  Return -1, if searchnum is not in
the list */
   int i;
   list[n] = searchnum;
   for (i = 0; list[i] != searchnum; i++)
      ;
   return ((i < n ) ? i : -1);
}

程式 7.1：循序搜尋 —— 注意 list[n] = searchnum; 這個哨兵寫法（第 2 章 2.6.2 節已出現過）

7.1.3　二分搜尋 (Binary Search)

「循序搜尋對於鍵值欄的順序不做任何假設，與這不同的是，二分搜尋假設串列依鍵值大小排列，使得 $\texttt{list[0].key} \le \texttt{list[1].key} \le \cdots \le \texttt{list[n-1].key}$。」

7.1.4　串列驗証

驗証過程辨識並印出三種錯誤：

1. 鍵值為 list1[i].key 的記錄存在第一個串列中，但在第二個串列（list2）中沒有相同鍵值的記錄。
2. 鍵值為 list2[j].key 的記錄存在第二個串列中，但在第一個串列（list1）中沒有相同鍵值的記錄。
3. list1[i].key = list2[j].key，但兩個記錄中至少有一個其他欄位相同。

7.2　定義

穩定性 (stable)

內部排序 vs 外部排序

7.3　插入排序 (Insertion Sort)

void insertion_sort(element list[], int n)
/* perform a insertion sort on the list */
{
   int i,j;
   element next;
   for (i = 1; i < n; i++) {
      next = list[i];
      for (j = i-1; j >= 0 && next.key < list[j].key; j--)
         list[j+1] = list[j];
      list[j+1] = next;
   }
}

程式 7.5：insertion_sort ——「因每次的插入保持插入後的序列順序排列，我們可以在 $n-1$ 次插入後排好 $n$ 個記錄。」

LOO：一個更精確的分析

7.4　快排 (Quick Sort)

所以，若鍵值 $K_i$ 放在位置 $S(i)$，則對於 $j \lt S(i)$，$K_j \le K_{S(i)}$，且 $j \gt S(i)$，$K_j \ge K_{S(i)}$。故，當這個位置決定了以後，原始檔案被分成兩個子檔，一個包含記錄 $R_0, \ldots, R_{S(i)-1}$，另一個包含記錄 $R_{S(i)+1}, \ldots, R_{n-1}$。因為在最後排好的序列中，在第一個子檔上的所有記錄會出現在 $S(i)$ 的左邊，第二個子檔則在 $S(i)$ 的右邊，這兩個子檔可以獨自排序。

void quicksort(element list[], int left, int right)
/* sort list[left], ... , list[right] into nondecreasing
order on the key field. list[left].key is arbitrarily
chosen as the pivot key.  It is assumed that
list[left].key <= list[right+1].key. */
{
   int pivot,i,j;
   element temp;
   if (left < right) {
      i = left;    j = right + 1;
      pivot = list[left].key;
      do {
      /* search for keys from the left and right sublists,
      swapping out-of-order elements until the left and
      right boundaries cross or meet */
         do
            i++;
         while (list[i].key < pivot);
         do
            j--;
         while (list[j].key > pivot);
         if (i < j)
            SWAP(list[i],list[j],temp);
      } while (i < j);
      SWAP(list[left],list[j],temp);
      quicksort(list,left,j-1);
      quicksort(list,j+1,right);
   }
}

程式 7.6：quicksort 函數（Hoare 的快排演算法之遞迴版本）

分析 quicksort

7.5　最佳的排序時間

7.6　合併排序 (Merge Sort)

7.6.1　合併

「在探討將 $n$ 個記錄排序的合併排序演算法之前，讓我們先瞭解如何將兩個已排序的串列合併來形成一個排序串列。」第一個是程式 7.7，「它很簡單並使用額外的 $O(n)$ 空間」。它將已排好的串列 $(\texttt{list}[i], \ldots, \texttt{list}[m])$ 和 $(\texttt{list}[m+1], \ldots, \texttt{list}[n])$ 合併成一個排好順序的串列 $(\texttt{sorted}[i], \ldots, \texttt{sorted}[n])$。

7.6.2　迴路式合併排序

void merge_pass(element list[], element sorted[], int n,
                                        int length)
{
/* perform one pass of the merge sort.  It merges adjacent
pairs of subfiles from list into sorted.  n is the
number of elements in the list. length is the length of the
subfile */
   int i,j;
   for (i = 0; i <= n - 2 * length; i += 2 * length)
      merge(list,sorted,i,i + length - 1,i + 2 * length - 1);
   if (i + length < n)
      merge(list,sorted,i,i + length - 1,n - 1);
   else
      for (j = i; j < n; j++)
         sorted[j] = list[j];
}

程式 7.9：merge_pass

7.6.3　遞迴式合併排序

int listmerge(element list[], int first, int second)
/* merge lists pointed to by first and second */
{
   int start = n;
   while (first != -1 && second != -1)
      if (list[first].key <= list[second].key) {
      /* key in first list is lower, link this element to
      start and change start to point to first */
         list[start].link = first;
         start = first;
         first = list[first].link;
      }
      else {
      /* key in second list is lower, link this element into
      the partially sorted list */
         list[start].link = second;
         start = second;
         second = list[second].link;
      }
   /* move remainder */
   if (first == -1)
      list[start].link = second;
   else
      list[start].link = first;
   return list[n].link; /* start of the new list */
}

程式 7.12：合併鏈結串列 —— 不移動任何記錄，只重接 link 欄位

7.7　累堆排序 (Heap Sort)

void adjust(element list[], int root, int n)
/* adjust the binary tree to establish the heap */
{
   int child,rootkey;
   element temp;
   temp = list[root];
   rootkey = list[root].key;
   child = 2 * root;           /* left child */
   while (child <= n) {
      if ((child < n) &&
      (list[child].key < list[child+1].key))
         child++;
      if (rootkey > list[child].key) /* compare root and
                                        max. child */
         break;
      else {
         list[child / 2] = list[child]; /* move to parent */
         child *= 2;
      }
   }
   list[child/2] = temp;
}

程式 7.13：調整一個最大累堆

void heapsort(element list[], int n)
/* perform a heapsort on the array */
{
   int i,j;
   element temp;

   for (i = n/2; i > 0; i--)
      adjust(list,i,n);
   for (i = n-1; i > 0; i--) {
      SWAP(list[1],list[i+1],temp);
      adjust(list,1,i);
   }
}

程式 7.14：累堆排序

7.8　基底排序 (Radix Sort)

「到目前為止，我們假設要排序的記錄只有一個鍵值。現在，讓我們考慮一些記錄有數個鍵值的排序問題。這些鍵值標記為 $K^0, K^1, \ldots, K^{r-1}$，其中 $K^0$ 為最重要的鍵值，$K^{r-1}$ 為最不重要的鍵值。」

#define MAX_DIGIT 3 /* numbers between 0 and 999*/
#define RADIX_SIZE 10
typedef struct list_node *list_pointer;
typedef struct list_node {
        int key[MAX_DIGIT];
        list_pointer link;
        };

list_pointer radix_sort(list_pointer ptr)
/*Radix Sort using a linked list */
{
   list_pointer front[RADIX_SIZE], rear [RADIX_SIZE];
   int i, j, digit;
   for (i = MAX_DIGIT-1; i >= 0; i--) {
      for (j = 0; j < RADIX_SIZE; j++)
         front[j] = rear[j] = NULL;
      while (ptr) {
         digit = ptr->key[i];
         if (!front[digit])
            front[digit] = ptr;
         else
            rear[digit]->link = ptr;
         rear[digit] = ptr;
         ptr = ptr->link;
      }
      /* reestablish the linked list for the next pass */
      ptr = NULL;
      for (j = RADIX_SIZE-1; j >= 0; j--)
         if (front[j]) {
            rear[j]->link = ptr;   ptr = front[j];
         }
   }
   return ptr;
}

程式 7.15：LSD 基底排序 —— 注意 for (i = MAX_DIGIT-1; i >= 0; i--)，從最低位數開始

7.9　串列和表格排序

7.10　內部排序摘要

圖 7.26：排序方法之平均時間（粗體為該列最快者）

7.11　外部排序

k-路合併與緩衝區

行程產生與輸家樹

if (tree[winner].data.key < last_key_out)
   tree[winner].data.run = current_run + 1;   /* 屬於下一個行程 */
else
   tree[winner].data.run = current_run;       /* 仍屬於本行程 */

if (tree[loser].data.run < winner-run ||
   (tree[loser].data.run == winner-run &&
    tree[loser].data.key < tree[winner].data.key)) { ... }

最佳合併模式與 Huffman 演算法

typedef struct tree_node *tree_pointer;
typedef struct tree_node {
        tree_pointer left_child;
        int          weight;
        tree_pointer right_child;
);
tree_pointer tree;
int n;

本章重點回顧