快速排序 | Quick sort

时间复杂度

$$ O(nlogn) $$

#include <iostream>
using namespace std;

void print_array(int* arr, int size) {
    //打印数组
    cout << "array1={ ";
    for (int i = 0; i < size; ++i) {
        cout << arr[i] << " ";
    }
    cout << "}" << endl;
}

void swap(int &a, int &b) {
    //交换两个变量
    int temp = b;
    b = a;
    a = temp;
}

void quick_sort(int* arr, int leftIndex,int rightIndex) {
    //快速排序
    int left = leftIndex;
    int right = rightIndex;
    if (left >= right) {
        return;
    }
    int temp = arr[leftIndex];
    while (left < right) {
        while (arr[left] <= temp && left < right)
        {    
            left++;
        }
        while (arr[right] >= temp && left < right) {
            right--;
        }
        if (left < right) {
            swap(arr[left],arr[right]);
        }
    }
    
    swap(arr[leftIndex], arr[left]);
    quick_sort(arr, leftIndex, left - 1);
    quick_sort(arr, left + 1, rightIndex);
}

int main() {
    //数组基本信息
    int array1[] = { 2,1,5,3,6,8,1,4};
    int sizeArray = sizeof(array1) / sizeof(array1[0]);

    //排序前的数组
    print_array(array1, sizeArray);

    //排序
    quick_sort(array1,0,sizeArray-1);

    //排序后的数组
    print_array(array1, sizeArray);
    
    return 0;
}