洛谷 P1177 快速排序

Question

洛谷P1177 快速排序

#include<iostream>
#include<cstdlib>
#include<ctime>

using namespace std;

int num[100010],n;

int get_mid(int left,int right){
    int pivot=rand()%(right-left+1)+left;
    swap(num[pivot],num[left]);
    int temp=num[left];    
    while(left<right){
        while(left<right && num[left]<=temp) left++;
        swap(num[left],num[right]);
        while(left<right && num[right]>temp) right--;
        swap(num[left],num[right]);
    }
    num[left]=temp;
    return left;
}

void quick_sort(int left,int right){
    if(left<right){
        int pos=get_mid(left,right);
        quick_sort(left,pos-1);
        quick_sort(pos+1,right);
    }
}

int main(){
    srand((unsigned)time(NULL));
    cin>>n;
    for(int i=1;i<=n;i++) cin>>num[i];
    quick_sort(0,n);
    for(int i=1;i<=n;i++) cout<<num[i]<<' ';
}

/*
    8
    1 5 7 4 6 3 2 8
*/

Answer 1

C/C++实现快速排序（两种方式）_你的代码没bug的博客-CSDN博客_c++快速排序 介绍快速排序是对冒泡排序算法的一种改进，快速排序算法通过多次比较和交换来实现排序。流程如下：（图片来自百度） 实现以下有两种实现方式，说是两种，其实就是在交换元素时具体细节上有点不同罢了。方式一int Partition(int A[],int low,int high){int pivot=A[low];//第一个元素作为基准while(low<high){while(low<high && A[high]>=pivot) hig https://blog.csdn.net/weixin_44915226/article/details/119535259