效率最高的排序算法是誰？快速排序，歸并排序，還是堆排序？

在計算機科學中，排序算法是一類常見且重要的算法，用于對一組資料按照某種規則進行排序。排序算法的效率通常由時間複雜度來衡量，時間複雜度描述了算法執行所需的計算資源随輸入規模的變化情況。本文将深入講解三種效率最高的排序算法：快速排序、歸并排序和堆排序，并附有相關的C語言代碼實作。

1. 快速排序（Quick Sort）

快速排序是一種分治法的排序算法，它通過選擇一個基準元素，将數組分成左右兩部分，使得左邊的元素都小于基準，右邊的元素都大于基準。然後對左右子數組遞歸地進行快速排序，直到子數組的大小為1。

快速排序的C語言代碼實作：

#include <stdio.h>

// 交換兩個元素的值
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 快速排序的分割函數
int partition(int arr[], int low, int high) {
    int pivot = arr[low]; // 選擇第一個元素作為基準
    while (low < high) {
        while (low < high && arr[high] >= pivot)
            high--;
        arr[low] = arr[high]; // 将比基準小的元素移到低端
        while (low < high && arr[low] <= pivot)
            low++;
        arr[high] = arr[low]; // 将比基準大的元素移到高端
    }
    arr[low] = pivot; // 基準元素歸位
    return low;
}

// 快速排序遞歸函數
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivotPos = partition(arr, low, high);
        quickSort(arr, low, pivotPos - 1); // 對左半部分進行快速排序
        quickSort(arr, pivotPos + 1, high); // 對右半部分進行快速排序
    }
}

// 快速排序接口函數
void quickSortWrapper(int arr[], int size) {
    quickSort(arr, 0, size - 1);
}

int main() {
    int arr[] = {10, 80, 30, 90, 40, 50, 70};
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("原始數組：");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }

    quickSortWrapper(arr, size);

    printf("\n排序後數組：");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}
           

快速排序原理講解：

快速排序是通過不斷地選擇基準元素，并将數組分割成兩個子數組，使得左邊的元素都小于基準，右邊的元素都大于基準，進而實作排序的。這個過程類似于"挖坑填數"的過程。快速排序的平均時間複雜度為O(n log n)，最壞情況下為O(n^2)（當選取的基準元素不平衡時）。快速排序是實際應用中最常用且性能優秀的排序算法。

2. 歸并排序（Merge Sort）

歸并排序也是一種分治法的排序算法。它将數組分成兩個子數組，分别對子數組進行歸并排序，然後将排好序的子數組合并成一個有序數組。

歸并排序的C語言代碼實作：

#include <stdio.h>

// 将兩個有序數組合并成一個有序數組
void merge(int arr[], int low, int mid, int high) {
    int n1 = mid - low + 1;
    int n2 = high - mid;

    int left[n1], right[n2];

    for (int i = 0; i < n1; i++)
        left[i] = arr[low + i];
    for (int j = 0; j < n2; j++)
        right[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = low;
    while (i < n1 && j < n2) {
        if (left[i] <= right[j]) {
            arr[k] = left[i];
            i++;
        } else {
            arr[k] = right[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = left[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = right[j];
        j++;
        k++;
    }
}

// 歸并排序遞歸函數
void mergeSort(int arr[], int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2;
        mergeSort(arr, low, mid); // 對左半部分進行歸并排序
        mergeSort(arr, mid + 1, high); // 對右半部分進行歸并排序
        merge(arr, low, mid, high); // 合并兩個有序子數組
    }
}

// 歸并排序接口函數
void mergeSortWrapper(int arr[], int size) {
    mergeSort(arr, 0, size - 1);
}

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("原始數組：");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }

    mergeSortWrapper(arr, size);

    printf("\n排序後數組：");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}
           

歸并排序原理講解：

歸并排序是通過不斷地将數組分成兩個子數組，并對子數組進行歸并排序，然後再将排好序的子數組合并成一個有序數組，進而實作排序的。這個過程類似于"分而治之"的思想。歸并排序的時間複雜度始終穩定為O(n log n)，無論最壞情況還是平均情況。雖然歸并排序在最壞情況下性能較快速排序略低，但是它具有穩定性和可預測性，是以在某些場景下被更廣泛地使用。

3. 堆排序（Heap Sort）

堆排序利用了堆這種資料結構的特性。它首先将待排序的數組建構成一個二叉堆，然後不斷地取出堆頂元素并調整堆結構，進而得到有序數組。

堆排序的C語言代碼實作：

#include <stdio.h>

// 交換兩個元素的值
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 調整堆，使其滿足堆性質
void heapify(int arr[], int size, int root) {
    int largest = root; // 初始化最大值為根節點
    int left = 2 * root + 1; // 左子節點索引
    int right = 2 * root + 2; // 右子節點索引

    // 如果左子節點大于根節點，将最大值設為左子節點
    if (left < size && arr[left] > arr[largest])
        largest = left;

    // 如果右子節點大于根節點，将最大值設為右子節點
    if (right < size && arr[right] > arr[largest])
        largest = right;

    // 如果最大值不是根節點，交換根節點和最大值，然後繼續調整堆
    if (largest != root) {
        swap(&arr[root], &arr[largest]);
        heapify(arr, size, largest);
    }
}

// 堆排序函數
void heapSort(int arr[], int size) {
    // 建構堆（從最後一個非葉子節點開始，直至根節點）
    for (int i = size / 2 - 1; i >= 0; i--)
        heapify(arr, size, i);

    // 從堆中取出元素，并不斷調整堆
    for (int i = size - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]); // 将堆頂元素（最大值）放到末尾
        heapify(arr, i, 0); // 調整堆，重新建構堆
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("原始數組：");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }

    heapSort(arr, size);

    printf("\n排序後數組：");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}
           

堆排序原理講解：

堆排序是通過不斷地建構堆、取出堆頂元素，并調整堆結構，進而實作排序的。堆排序利用了二叉堆這種資料結構的特性，它具有較高的執行效率。堆排序的時間複雜度始終穩定為O(n log n)，而且它的常數因子較小，使得它在實際中具有較高的執行效率。

4. 結論

雖然快速排序、歸并排序和堆排序都具有相同的時間複雜度，但是它們在實際中的性能會受到不同因素的影響。例如，快速排序在處理大規模資料時性能較好，但在資料集較小且基準選擇不當時可能表現較差；歸并排序适用于資料量較小且對穩定性要求較高的場景；堆排序适用于記憶體有限的情況下，或者需要同時排序多個資料集時。 是以，在實際應用中，選擇最适合特定場景和資料規模的排序算法是很重要的。要綜合考慮時間複雜度、空間複雜度以及算法的穩定性和可擴充性。