快速排序

作者: admin
标签: 分而治之
更新: 8/8/2019, 11:27:34 PM
#include <iostream>

using namespace std;
int arr[100];
void partition(int low, int hi, int& pivot){
    int i, j;
    int temp;
    temp = arr[low];
    j = low;
    for(i = low+1;i<=hi;i++)    //从枢纽点后第一个数开始比较
        if(arr[i]<temp){        //遇到比枢纽点小的
            j++;                //指针j向后移动
            swap(arr[i], arr[j]);//并交换这两个元素
        }                       //循环完毕
    pivot = j;                  //快排递归需要的分割元素
    swap(arr[low], arr[pivot]); //枢纽点就位,j就是猜测点应该呆的位置
}
void quicksort(int low, int hi){
    int pivot;
    if(hi > low){
        partition(low, hi, pivot);
        quicksort(low, pivot-1);//排序枢纽点左侧
        quicksort(pivot+1, hi); //排序枢纽点右侧
    }
}
int main(int argc, char const *argv[]){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&arr[i]);
    quicksort(0, n-1);
    for (int i = 0; i < n; ++i) {
        cout <<arr[i];
    }
    return 0;
}
删除
修改
点击登陆评论