在我使用 C++ 向量的快速排序实现中，分区函数是否与使用简单的交换方法相同？

Question

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

void quick_sort(vector<int> &a, int start, int end);
int partition(vector<int> &a, int start, int end);

int main(){
    vector<int> v = {7, 6, 5, 4, 3, 2, 1};
    int n(7);
    quick_sort(v, 0, n);
    for (auto& itr : v){
        cout << itr << ' ';
    }
    return 0;
}

void quick_sort(vector<int> &a, int start, int end){
    if (start < end){
        int index;
        index = partition(a, start, end);
        
        quick_sort(a, start, index - 1);
        quick_sort(a, index, end);
    }
}

int partition(vector<int> &a, int start, int end){
    int pivot, count(0);
    pivot = a[end - 1];
    for (int i = start; a[i] != pivot; i++){
        if (a[i] > pivot){
            a.insert(a.begin()+end, a[i]);
            a.erase(a.begin() + i);
            count++;
            i--;
        }
    }
    return end-count;
}

这里在分区函数中我使用了STL库中提供的插入和擦除函数。

分区函数的时间复杂度会不会大于O(n)（使用swap时的情况）？

根据我的说法，最坏的情况是当枢轴元素是最小元素时，所有 (n-1) 个元素都将被推到向量的末尾。

编辑：

int partition(vector<int> &a, int start, int end){
    int pivot;
    pivot = end - 1;
    for (int i = start; i < end; i++){
        if (a[i] > a[pivot] && i < pivot){
            swap(a[i], a[pivot]);
            pivot = i;
        }
        else if (a[i] < a[pivot] && i > pivot){
            swap(a[i], a[pivot]);
            pivot = i;
        }
    }
    return pivot + 1;
}

这个配分函数在 O(n) 时间内运行。

Answer 1

您在 end 之后移动每个元素执行 insert，在 i 之后移动每个元素执行 erase。这个版本比交换差很多。使用 std::swap，您只需触摸两个元素。

旁白：C++ 中的排序是 traditionally done with iterators，而不是索引，即

using iterator = std::vector<int>::iterator; 

void quick_sort(iterator start, iterator end);
iterator partition(iterator start, iterator end);

在我使用 C++ 向量的快速排序实现中，分区函数是否与使用简单的交换方法相同？

In my quicksort implementation using C++ vectors, is partition function same as using the trivial method of swaps?

c++

sorting

data-structures

stl

quicksort