冒泡排序和快速排序

温故知新，算法的思想虽然理解，但代码长时间不写就生疏了

对于数组nums长度为n，升序排序

冒泡排序

冒泡排序就是进行n轮排序，每轮都会找出未排序的最大值，并将其放到排好序的数前面（比他大的数在之前的轮已经排好序），进行n轮后，将数全部排序。每一轮中会将大的数往右移动，将最大的数移动到最右边
例如
nums = { 5,3,7,6,4,1,0,2,9,10,8 }
第一轮排完序之后，变为
3 5 6 4 1 0 2 7 9 8 10，其中5 7 10都往右移动，最终最大的数10移动到最后的位置，完成10的排序
第二轮后变为
3 5 4 1 0 2 6 7 8 9 10，其中6 9往右移动，当前最大为完成排序的数9，移动到已经排完序的10前面，完成排序
然后依次排完8，7，6…
最终完成排序

快速排序

快速排序是对冒泡排序的一种改进。
快排每都会从数组nums中选取一个key值，将当前数组分为两个部分，一部分为小于key的数，另外一部分为大于key值的数，拍完一次之后，key值就完成了排序，然后再分别对key旁边的两部分进行排序。通常key值选取数组中的第一个值
例
nums = { 5,3,7,6,4,1,0,2,9,10,8 }
第一次快排的key = nums[0]key 为5。将小于5的数放在5的左边，大于等于5的数放在右边。这里就涉及到算法的实现了。这里使用i = 0, j = n - 1来分别指向第一个和最后一个数，然后由于nums[i] == key，而i的位置应该放一个小于key的数，因此从右向左寻找j 使得nums[j] < key然后交换nums[i] 和 nums[j]。
第一次交换完，数组为
2 3 7 6 4 1 0 5 9 10 8，可以看到key值5与2进行了交换，此时i = 0, j = 7且j右边的数都大于key

交换完之后，此时nums[j] == key，且由于j是从右向左寻找，因此nums[j] 右边的数一定都是大于等于key的。此时还需要判断j的左边是否还有大于key的数，因此需要从左向右寻找i 使得nums[i] >= key，然后交换。
第二次交换完后
2 3 5 6 4 1 0 7 9 10 8，可以看到key值5与7发生了交换，此时i = 1, j = 7，且j右边的数都大于等于key，i左边的数小于key。
然后循环处理，直到key的左边全为小于key的数，key的右边全为大于等于key的数。一次快排完成。

完成一次快排后，把数组分成了三部分，一部分为key左边全部小于key值的数，一部分为key（此时key已经排好序），还有一部分为key右边大于等于key值的数。接下来需要在对左右两个部分进行快排，然后一直递归，直到全部排完

代码

#include 
#include 
using namespace std;

// 快速排序
void quickSort(vector<int>& nums, int l, int r)
{
    if (l + 1 >= r)
        return;
    int key = nums[l];
    int i = l;
    int j = r - 1;
    while (i < j)
    {
        while (nums[j] >= key && j > i)
            j--;
        swap(nums[i], nums[j]);

        //for (int k = l; k < r; k++)
        //    cout << nums[k] << " ";
        //cout << endl;

        while (nums[i] < key && i < j)
            i++;
        swap(nums[i], nums[j]);

        //for (int k = l; k < r; k++)
        //    cout << nums[k] << " ";
        //cout << endl;
    }
    // 左边
    quickSort(nums, l, i);
    // 右边，这里起点为i + 1，因为i为key，而且此时已经排好序，因此需要从key的右边开始排序
    quickSort(nums, i + 1, r);
}

// 冒泡排序
void bubbleSort(vector<int> nums)
{
    int n = nums.size();
    for (int i = 0; i < n; i++)
    {
        for (int j = 1; j < n; j++)
        {
            if (nums[j] < nums[j - 1])
                swap(nums[j], nums[j - 1]);
        }

        //for (auto item : nums)
        //    cout << item << " ";
        //cout << endl;
    }
    //for (auto item : nums)
    //    cout << item << " ";
    //cout << endl;
}

int main()
{
    vector<int> nums = { 5,3,7,6,4,1,0,2,9,10,8 };
    for (auto item : nums)
        cout << item << " ";
    cout << endl;

    quickSort(nums, 0, nums.size());
    //bubbleSort(nums);

    for (auto item : nums)
        cout << item << " ";
    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
62
63
64
65
66
67
68
69
70
71
72
73
74