排序算法——快速排序_快速排序 vector& data

实现代码：

//以第一个元素为主元
//如果以最后一个元素为主元，指针的初始化以及返回情况有些不同
int partition(vector<int> &data, int l, int r)
{
    int main = 0;
    int i = 0; //维护主元左边的值的指针
    int j = 0; //迭代器

    if(l >= r)
        return l;
    
    i = l;
    main = data[l];
    for(j = l+1; j <= r; j++)
    {
        if(data[j] <= main)
        {
            i++;
            swap(data[i],data[j]); //i，j如果（i++）之前是相邻的，那么其实是没有交换

        }

    }
    swap(data[i], data[l]);

    return i;
}

void quick_sort(vector<int> &data, int l, int r)
{
    if(l < r)
    {
        int q = partition(data, l, r);
        quick_sort(data, l, q - 1);
        quick_sort(data, q + 1, r);
    }
}

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