快速排序

最近在全面学习数据结构，常用算法记录：快速排序，即交换排序的一种，是对冒泡排序的一种改进，是一种不稳定排序。
平均时间复杂度：$O(nlogn)$
最坏时间复杂度（退化至冒泡排序）：$O(n^2)$

#include <iostream>

using namespace std;

//快速排序
void quickSort(int arr[], int low, int high);
void quickSort_another(int *arr, int left, int right);
//划分函数
int partition(int arr[], int low, int high);

int main()
{
    int arr[] = {5, 2, 4, 6, 1, 3};
    quickSort(arr, 0, 5);
    for(auto cur:arr)
        cout << cur << " ";
    cout << endl;
    quickSort_another(arr, 0, 5);
    for(auto cur:arr)
        cout << cur << " ";
    return 0;
}

int partition(int arr[], int low, int high)
{
    int pivot = arr[low];   //第一个元素作为基准
    while(low < high)   //low == high时结束
    {
        while(low < high && arr[high] >= pivot)
            --high;
        arr[low] = arr[high];   //此时arr[high]小于基准元素
        while (low < high && arr[low] <= pivot)
            ++low;
        arr[high] = arr[low];   //此时arr[low]大于基准元素
    }
    arr[low] = pivot;   //此时low == high
    return low;     //返回基准元素的下标
}
void quickSort(int arr[], int low, int high)
{
    if(low < high)
    {
        int pivot_pos = partition(arr, low, high);
        quickSort(arr, low, pivot_pos - 1);     //对基准元素左边的数组进行快速排序
        quickSort(arr, pivot_pos + 1, high);    //对基准元素右边的数组进行快速排序
    }
}

//写法二
void quickSort_another(int *arr, int left, int right)
{
    if (left >= right)
        return;
    int pivot = arr[left];
    int i = left + 1, j = right;
    while (i <= j)
    {
        while (i <= right && arr[i] < pivot)
            i++;
        while (j >= left && arr[j] > pivot)
            j--;
        if (i <= j)
        {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }
    arr[left] = arr[j];
    arr[j] = pivot;
    quickSort_another(arr, left, j - 1);
    quickSort_another(arr, j + 1, right);
}

版权属于：字节星球/肥柴之家 （转载请联系作者授权）
原文链接：https://www.bytecho.net/archives/2075.html
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。