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

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

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

【原创内容,转载请注明出处】
 
It's
欢迎访问本站,欢迎留言、分享、点赞。愿您阅读愉快!
*转载请注明出处,严禁非法转载。
https://www.devsong.org
QQ留言 邮箱留言
头像
引用:
取消回复
提交
涂鸦
涂鸦
热门