如何使用C++中的快速排序演算法

如何使用C 中的快速排序演算法

快速排序演算法是一種常用的排序演算法，其核心思想是將待排序的序列不斷劃分成較小和較大的兩個子序列，然後遞歸地對子序列進行排序，最終使整個序列有序。本文將介紹如何在C 中使用快速排序演算法，並提供具體的程式碼範例。

快速排序演算法的實作想法如下：

1. 選擇一個基準元素pivot，可以是序列中的任一個元素。通常選擇第一個或最後一個元素作為基準。
2. 將序列中小於pivot的元素放在pivot的左邊，大於pivot的元素放在右邊。
3. 對左右兩個子序列分別遞歸地進行快速排序。

以下是使用C 實作快速排序演算法的程式碼範例：

#include <iostream>
using namespace std;

// 交换两个元素的值
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 快速排序的划分函数
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选择最后一个元素作为基准
    int i = (low - 1);  // i代表小于基准的元素的最右边界
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);  // 将小于基准的元素放在左边
        }
    }
    swap(&arr[i + 1], &arr[high]);  // 将基准元素放在合适的位置
    return (i + 1);
}

// 快速排序的递归函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);  // 划分数组
        quickSort(arr, low, pi - 1);  // 对左子数组进行递归排序
        quickSort(arr, pi + 1, high);  // 对右子数组进行递归排序
    }
}

// 打印数组
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "原始数组：";
    printArray(arr, n);
    quickSort(arr, 0, n - 1);
    cout << "排序后的数组：";
    printArray(arr, n);
    return 0;
}

運行上述程式碼後，將得到如下輸出結果：

原始数组：10 7 8 9 1 5 
排序后的数组：1 5 7 8 9 10 

這段程式碼實現了快速排序演算法，首先選擇最後一個元素作為基準，然後使用partition函數對陣列進行劃分，將小於基準的元素放在左邊，大於基準的元素放在右邊。然後將左右子數組分別進行遞歸排序，直到整個數組有序。

總結：
快速排序是一種高效率的排序演算法，它的平均時間複雜度為O(n log n)，使用C 實作快速排序演算法相對簡單。透過上述程式碼範例，你可以了解到快速排序演算法的基本原理和實作方式，同時也可以在實際應用中靈活運用。

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