C++实现快速排序算法

快速排序算法时最常用的排序算法之一，时间复杂度为O(nlog(n))~O(n^2)，最差的时候就是排序的原始数据和要求正好相反，如需要正序的结果，而原始数据恰好是逆序的过程。

但是快速排序占用的空间少，一般情况下时间复杂度和归并排序差不多。

以下为快速排序算法的代码实现。

void swap(vector<int> &arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

void quick_sort(vector<int> &arr, int left, int right) {
    if (left >= right) return;
    if (left < 0 || right >= arr.size())
        return;
    int i = left;
    int j = right;
    while (i < j) {
        while (arr[j] >= arr[left] && i < j) {
            j--;
        }
        while (arr[i] <= arr[left] && i < j) {
            i++;
        }
        if (i < j) {
        	//因为已经互换了arr中位置i和位置j里面的元素值，所以上面的两个while循环能执行下去
            swap(arr, i, j);
        }
    }
    swap(arr, left, i);

    quick_sort(arr, left, i - 1);
    quick_sort(arr, i + 1, right);
}

vector<int> getLeastNumbers(vector<int> &arr, int k) {
    quick_sort(arr, 0, arr.size() - 1);
}

以上便是C++实现快速排序的过程了，如果对您有帮助，请点👍支持一下🙂。