Cara menggunakan algoritma quicksort dalam C++

Cara menggunakan algoritma isihan pantas dalam C++

Algoritma isihan pantas ialah algoritma pengisihan yang biasa digunakan item yang hendak diisih. Urutan itu dibahagikan secara berterusan kepada dua urutan, lebih kecil dan lebih besar, dan kemudian urutan itu diisih secara rekursif, dan akhirnya keseluruhan urutan disusun. Artikel ini akan memperkenalkan cara menggunakan algoritma isihan pantas dalam C++ dan memberikan contoh kod khusus.

Idea pelaksanaan algoritma isihan pantas adalah seperti berikut:

1. Pilih pangsi elemen rujukan, yang boleh menjadi sebarang elemen dalam jujukan. Biasanya elemen pertama atau terakhir dipilih sebagai asas.
2. Letakkan elemen dalam urutan yang lebih kecil daripada pangsi di sebelah kiri pangsi, dan elemen yang lebih besar daripada pangsi diletakkan di sebelah kanan.
3. Cepat susun urutan kiri dan kanan secara rekursif.

Berikut ialah contoh kod menggunakan C++ untuk melaksanakan algoritma isihan pantas:

#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;
}

Selepas menjalankan kod di atas, anda akan mendapat output berikut: # 🎜🎜#

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

Ringkasan:

Atas ialah kandungan terperinci Cara menggunakan algoritma quicksort dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!