掌握C++中的常用排序演算法

C 是一門廣泛應用於電腦程式設計中的程式語言，而排序演算法則是程式設計中常用的演算法之一。掌握排序演算法，能夠提升編寫高效程式的能力，提升程式設計技能。本文將介紹 C 中常用的排序演算法。

1. 冒泡排序

冒泡排序是一種基礎的排序演算法，它透過依序比較相鄰的元素，將較大的元素交換到序列的末尾，從而實現排序。具體來說，冒泡排序每一輪比較相鄰元素的大小，並將較大的元素向後交換，直到最後一個元素排好序為止。

C 程式碼如下：

void bubbleSort(int arr[], int n)
{
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j+1]) {
                // 交换元素
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

2. 選擇排序

#選擇排序是一種簡單的排序演算法，它每次選出未排序部分中最小的元素，並將其放到已排序部分的末尾，從而實現排序。具體來說，選擇排序每一輪選出最小的元素，並與目前位置的元素交換。

C 程式碼如下：

void selectionSort(int arr[], int n)
{
    int minIndex, temp;
    for (int i = 0; i < n - 1; i++) {
        minIndex = i; // 记录最小元素的位置
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                // 更新最小元素的位置
                minIndex = j;
            }
        }
        // 交换元素
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

3. 插入排序

#插入排序是一種簡單直覺的排序演算法，它透過將一個元素插入到已經在排好序的序列中，從而得到一個較長的排好序的序列。具體來說，插入排序每一輪將一個元素插入到已排好序的子數組中，並將其餘元素向後移動。

C 程式碼如下：

void insertionSort(int arr[], int n)
{
    int key, j;
    for (int i = 1; i < n; i++) {
        key = arr[i]; // 待插入的元素
        j = i - 1;
        // 将大于待插入元素的元素向后移动
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j--;
        }
        // 将待插入元素插入到正确的位置
        arr[j+1] = key;
    }
}

4. 快速排序

快速排序是一種高效的排序演算法，它透過選擇一個樞紐元素，將序列拆分成兩個部分，一部分小於樞紐元素，一部分大於樞紐元素，並對兩個子序列遞歸進行排序。具體來說，快速排序每一輪選擇一個樞紐元素，並將小於樞紐元素的元素放在樞紐元素左邊，大於樞紐元素的元素放在右邊。然後以相同的方式對左右兩個子序列遞歸進行排序。

C 程式碼如下：

void quickSort(int arr[], int left, int right)
{
    int i = left, j = right;
    int pivot = arr[(left + right) / 2]; // 选择枢纽元素
    while (i <= j) {
        // 找到左侧大于枢纽元素的元素
        while (arr[i] < pivot) {
            i++;
        }
        // 找到右侧小于枢纽元素的元素
        while (arr[j] > pivot) {
            j--;
        }
        // 交换左右元素
        if (i <= j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }
    // 递归排序左侧和右侧的子序列
    if (left < j) {
        quickSort(arr, left, j);
    }
    if (i < right) {
        quickSort(arr, i, right);
    }
}

5. 歸併排序

歸併排序是一種經典的分治思想的排序演算法，它將序列分成兩個子序列，分別對每個子序列進行排序，最後合併兩個有序子序列。具體來說，歸併排序先將序列拆分成兩個子序列，對兩個子序列分別遞歸進行排序，然後將兩個有序子序列合併成一個有序序列。

C 程式碼如下：

void merge(int arr[], int left, int mid, int right)
{
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];

    // 将数据拷贝到两个临时数组中
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    i = 0; // 左侧子数组的索引
    j = 0; // 右侧子数组的索引
    k = left; // 合并后的数组的索引
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    // 将左侧子数组的剩余元素拷贝到合并后的数组中
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    // 将右侧子数组的剩余元素拷贝到合并后的数组中
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int left, int right)
{
    if (left < right) {
        int mid = left + (right - left) / 2;
        // 递归排序左侧和右侧的子序列
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        // 合并两个有序子数组
        merge(arr, left, mid, right);
    }
}

以上就是 C 中常用的五種排序演算法。演算法雖然看起來枯燥乏味，但它們卻是程式設計的重要組成部分，透過學習排序演算法，我們可以提高程式設計的效率和品質。

以上是掌握C++中的常用排序演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！