【快速排序介绍】

快速排序：高效的排序算法

快速排序基于分治策略，将一个大问题分解成小问题来排序一个数组。

快速排序的原理

快速排序的核心思想是选择一个基准元素（通常是数组中的第一个元素），然后将数组分成两个子数组：一个小于基准元素的子数组和一个大于基准元素的子数组。接下来，递归地对这两个子数组进行排序。

快速排序的步骤

1. 选择基准元素： 从数组中选择一个元素作为基准元素。

2. 分区过程： 将数组中的元素按照基准元素的大小分成两个子数组，小于基准的放在左边，大于基准的放在右边。

3. 递归排序： 递归地对左右两个子数组进行排序。

4. 合并结果： 将左子数组、基准元素和右子数组合并起来，得到排序后的数组。

示例代码

#include 
#include 

using namespace std;

// 快速排序函数
void quicksort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int pivot = arr[left]; // 选择第一个元素作为基准
        int i = left;
        int j = right;

        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, left, i - 1);
        quicksort(arr, i + 1, right);
    }
}

int main() {
    vector<int> myArray = {3, 6, 8, 10, 1, 2, 1};

    cout << "Original Array: ";
    for (int num : myArray) {
        cout << num << " ";
    }
    cout << endl;

    quicksort(myArray, 0, myArray.size() - 1);

    cout << "Sorted Array: ";
    for (int num : myArray) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61