C++のクイックソート関数の使い方は？

1年 ago
蓮, 翼
1 minute

C++のクイックソート関数は、次の手順を使って利用することができます。

  1. #include
  2. 配列や開始インデックス、終了インデックスを引数に取るクイックソート関数を定義する。
  3. クイックソート関数の中で、基準要素を選択します（通常、配列の最初の要素を選択します）。
  4. 始点インデックスを指す1つのポインターと終点インデックスを指すもう1つのポインターを設定します。
  5. 基準要素よりも小さい要素は左に、大きい要素は右に配置する。
  6. 基準要素の左側のサブ配列と右側のサブ配列をソートするために、クイックソート関数を再帰的に呼び出す。
  7. クイックソートの関数を呼び出して、配列をソートする。

快速ソート関数を使用する例コードが以下に示されています。

#include <iostream>

// 快速排序函数
void quickSort(int arr[], int start, int end) {
    if (start < end) {
        int pivot = arr[start]; // 基准元素
        int i = start; // 左指针
        int j = end; // 右指针

        while (i < j) {
            // 从右往左找到比基准元素小的元素
            while (i < j && arr[j] >= pivot) {
                j--;
            }
            if (i < j) {
                arr[i] = arr[j];
                i++;
            }

            // 从左往右找到比基准元素大的元素
            while (i < j && arr[i] <= pivot) {
                i++;
            }
            if (i < j) {
                arr[j] = arr[i];
                j--;
            }
        }

        arr[i] = pivot; // 将基准元素放到正确的位置

        // 递归调用快速排序函数
        quickSort(arr, start, i - 1); // 对左边的子数组进行排序
        quickSort(arr, i + 1, end); // 对右边的子数组进行排序
    }
}

int main() {
    int arr[] = {5, 2, 8, 3, 1, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    std::cout << "原始数组：";
    for (int i = 0; i < n; ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    quickSort(arr, 0, n - 1); // 调用快速排序函数

    std::cout << "排序后的数组：";
    for (int i = 0; i < n; ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

結果を出力します。

原始数组：5 2 8 3 1 6 
排序后的数组：1 2 3 5 6 8

上記の例では、配列をクイックソートするための quickSort 関数を定義しました。そして、main 関数でその関数を呼び出し、ソートされた配列を出力します。

bannerAds