C 語言排序演算法實作整理：泡沫排序、快速排序等

這裡提供各種排序演算法的 C 語言實作範例。

若要對一連串的元素（陣列）做排序的話，有很多種實作方式，常見的排序方法有：泡沫排序法（bubble sort）、插入排序法（insertion sort）、快速排序法（quick sort）等。

泡沫排序法

泡沫排序法是程式設計入門者常會使用的排序演算法，概念直覺、寫法也很簡單：

/* 泡沫排序法 */
void bubble_sort(int arr[], int n) {
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < i; ++j) {
      if (arr[j] > arr[i]) {
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
      }
    }
  }
}

插入排序法

插入演算法也是一種簡單的排序演算法，以下是它的實做程式碼：

/* 插入排序法 */
void insertion_sort(int arr[], int n) {
  for (int i = 0; i < n; i++) {
    int j = i;
    while (j > 0 && arr[j - 1] > arr[j]) {
      int temp = arr[j];
      arr[j] = arr[j - 1];
      arr[j - 1] = temp;
      j--;
    }
  }
}

快速排序法

快速排序法是效率比較高的排序演算法，以下是簡單的實做：

/* 快速排序法 */
void quick_sort(int arr[], int first_index, int last_index) {
  // 宣告索引變數
  int pivotIndex, temp, index_a, index_b;

  if (first_index < last_index) {
    // 以第一個元素作為基準
    pivotIndex = first_index;
    index_a = first_index;
    index_b = last_index;

    // 以遞增方式排序
    while (index_a < index_b) {
      while (arr[index_a] <= arr[pivotIndex] && index_a < last_index) {
        index_a++;
      }
      while (arr[index_b] > arr[pivotIndex]) {
        index_b--;
      }

      if (index_a < index_b) {
        // 交換元素
        temp = arr[index_a];
        arr[index_a] = arr[index_b];
        arr[index_b] = temp;
      }
    }

    // 交換基準元素與 index_b 元素
    temp = arr[pivotIndex];
    arr[pivotIndex] = arr[index_b];
    arr[index_b] = temp;

    // 遞迴呼叫快速排序法函數
    quick_sort(arr, first_index, index_b - 1);
    quick_sort(arr, index_b + 1, last_index);
  }
}

測試

以下是簡單的測試程式碼：

#include <stdio.h>
void output_arr(int arr[], int n) {
  for (int i = 0; i < n; ++i) { printf("%d ", arr[i]); }
  printf("\n");
}
int main() {
  int arr1[] = {3,2,1,7,6,5,9,8,7};
  int arr2[] = {3,2,1,7,6,5,9,8,7};
  int arr3[] = {3,2,1,7,6,5,9,8,7};

  bubble_sort(arr1, 9);
  insertion_sort(arr2, 9);
  quick_sort(arr3, 0, 8);

  output_arr(arr1, 9);
  output_arr(arr2, 9);
  output_arr(arr3, 9);

  return 0;
}

參考資料：eddyerburgh