快速排序

2021-02-07 02:16

阅读：607

标签：nlogn 快排 ring log pac div 复杂注意 while

#include 
#include string>
#include 
#include 
#include 
#include 
#include using namespace std;

int arr[105];

void quick_sort(int i,int j){
    int left = i;
    int right = j;
    int base = arr[i];  //记录基准元素

    if(left>right)
        return;

    while(i!=j){
        //必须先从右往左进行试探
        while(arr[j]>=base&&j!=i)
            j--;
        while(arr[i]base&&i!=j)
            i++;
        if(i!=j){
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    arr[left] = arr[i];
    arr[i] = base;
    quick_sort(i+1,right);
    quick_sort(left,i-1);
}

int main() {
    int n;
    scanf("%d",&n);
    for(int i=1;i)
        scanf("%d",&arr[i]);
    quick_sort(1,n);
    for(int i=1;i)
        printf("%d ",arr[i]);
    return 0;
}

注意：当需要排序的序列为正序或逆序的时候，每次快排只得到一个比上一次划分少一个记录的子序列

这时，快速排序的时间复杂度退化为O(n^2)，快速排序的平均复杂度为O(nlogn)

快速排序是不稳定的排序，反例：对 6 2 3 3 进行排序，不能保证后面两个3的相对位置不变

快速排序

标签：nlogn 快排 ring log pac div 复杂注意 while

原文地址：https://www.cnblogs.com/xiaoxb17/p/12780408.html

上一篇：基本算法思维——路灯问题

下一篇：第三章 python入门变量

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：快速排序
文章链接：http://soscw.com/index.php/essay/51974.html

亲，登录后才可以留言！

快速排序

评论

热门文章

推荐文章

最新文章

置顶文章