top
友情提示
测试消息
确定
友情提示

处理中,请稍后...

排序算法:交换排序之快速排序
快速排序是一种二叉树结构的交换排序算法。

快速排序的基本思想:取数据集中的一个元素作为比较标准(一般取第一个元素),调整数据集合中元素的位置,使排在标准元素之前的元素都小于标准元素,排在标准元素之后的元素都大于标准元素。这样一次之后,数据集合被分为了以标准元素为中心的两个子集,左边的子集关键字值都小于标准元素,位于标准元素右边的子集则大于标准元素。之后对分出来的子集采样同样的算法进行处理。递归算法的结束条件是集合上界小标大于或等于集合下界下标,也是就下述算法中的 low >= high。

C语言实现及测试
#include <stdio.h>
/**
 * 快速排序:升序
 * @param data 待排序集合
 * @param low  集合低位下标
 * @param high 集合高位下标
 *
 * 注: 此处为方便演示,依旧只是进行简单的 int数组 排序
 */
void quickSortAsc(int data[], int low, int high){
    int i = low, j = high;
    //取data[low] 为比较标准
    int temp = data[low]; 

    while(i < j){
        while(i < j && temp < data[j]){ //在数组右端扫描
            j--;
        }
        //执行完上个循化之后如果 i<j 依旧成立则 temp < data[j], 将 j 所在位置元素替换到 i 位置
        if(i < j){ 
            data[i] = data[j];
            i++;
        }

        while(i < j && temp > data[i]){ //在数组左端扫描
            i++;
        }
        // i < j 说明 temp > data[i], 将 i 所在位置元素替换到 j 位置
        if(i < j){ 
            data[j] = data[i];
            j--;
        }
    }//while 循环之后 i 和 j 相等

    //将判断标准重新放入数组
    //经过上述循环之后, data[i] 左侧的元素均小于(或等于:不稳定) data[i], 右侧均大于(或等于:不稳定) data[i]
    data[i] = temp;
    //对左端子集合进行递归
    if(low < i){
        quickSortAsc(data, low, i-1);
    }
    //对右端子集合进行递归
    if(j < high){
        quickSortAsc(data, j+1, high);
    }
}

int main(int argc, char const *argv[]){
    
    int i = 0;
    int a[] = {65, 34, 25, 87, 12, 38, 56, 46, 14, 77, 92, 23};
    int n = 12;
    quickSortAsc(a, 0, n-1);

    for(i = 0; i < n; i++){
        printf("%d ", a[i]);
    }

    return 0;
}

分析
快速排序算法的时间复杂度和个次标准数据的值的关系很大。如果每次选取的标准元素都能够均分两个子集合,这样的快速排序过程是一个完全二叉树,每个“分叉节点”都是 “各自所属的递归过程” 的标准元素值。这时的分解次数等于完全二叉树的深度。每次的排序过程无论怎么划分,最终比较次数都接近 n-1 次,所以最好的情况下,快速排序算法的时间复杂度为 O(nlbn)。

最坏的情况是数据集合已经排好序,此时分解过程构成一棵二叉退化树,说白了就是单分支树,树的深度为n, 此时时间复杂度为O(n2)

一般情况下,标准元素值的分布是随机的,集合的分解次数构成一棵一般的二叉树,深度近似于 lbn, 所以,快速排序的平均时间复杂度为 O(nlbn)。

总结
快速排序是一种不稳定的排序算法,这一点可以从其排序过程中轻松看出,或者最简单的假设一个所有元素值都相等的数据,用快速排序的思想很明显排序后值相等的元素位置发生了交换。快速排序每个人写法可能有细微差别,但思想是一致的。以上只是我个人见解,若您有不同看法,欢迎留言评论。您还可以查看系列文章,点击文章下方标签即可。

【原创内容,转载请注明出处】
 
标签
排序
算法
交换排序
快速排序
QuickSort
上一篇:排序算法:交换排序之冒泡排序
下一篇:经典数据结构之二叉树
文章阅读完了, 快到评论区留下你的看法吧!
Email:
验证码:
昵 称 :
评论列表
热门标签
今日倒计时
小时 分钟
年少不识曲中意,再听已是曲中人
加油吧骚年
文章分类
最新文章
浏览排行
最新留言
[2018/11/27]博客该更新了
[2018/10/25]网站链接以便更 www.qiuyegen.com
[2018/04/07]太难找了,找到了
[2018/03/21]Entry fileTemplates//Singleton.java.ft not found in C:/Dev/android-studio/lib/resources_en.jar 该错误对我们使用AS没有影响吗?为什么复制保存后重新创建一个新的之后这个错误又出现了?
[2018/01/23]815cce30b85eb6b7ee7930c09135fcf7好漂亮的博客空间啊
[2018/01/06]好漂亮的博客.......
[2017/12/26]试试水
[2017/12/21] 博主可以分享一下这个源码不, 很喜欢这个博客
[2017/11/20]你加我友链了????
[2017/11/20]你的alert 很不友好哈
Copyright © 2018 DevSONG . All rights reserved. 有疑问或者建议? 留言给我或者E-mail me
滇ICP备17002307号-3