文档章节

快速排序

此鱼不得水
 此鱼不得水
发布于 2016/03/17 13:27
字数 505
阅读 40
收藏 0

快速排序也属于一种交换排序算法,排序的过程中不停地有元素交换,但是因为其在均匀分布的数据中有比较良好的排序效果,因此被广泛利用。

private static int getMiddle(int[] array, int low, int high) {
    int temp = array[low];
    while (low < high) {
        while (low < high && array[high] >= temp) {
            high--;
        }
        array[low] = array[high];
        while (low < high && array[low] <= temp) {
            low++;
        }
        array[high] = array[low];
    }
    //此时low=high,所以这个时候还应该把原来的值附到中间值去
    array[low] = temp;
    return low;
}

private static void quickSort(int[] array, int low, int high) {
    //此处递归调用即可
    if (low < high) {
        int middle = getMiddle(array, low, high);
        quickSort(array, low, middle - 1);
        quickSort(array, middle + 1, high);
    }
}

public static void sort(int[] array) {
    if (array == null || array.length <= 1) {
        return;
    }
    quickSort(array, 0, array.length - 1);
}

快排的思路就不介绍了,满大街都有讲快排的。这里给出的代码是我觉得比较优化的实现方案,实现方案也比较简单。

其中就是每一次getMiddle之后然后折半递归,最终求得排序结果。

最优时间复杂度:O(nlogn)

平均时间复杂度:O(nlogn)

最坏时间复杂度:O(n^2),快排在对有序数组进行排序时候因为每次都是涉及到全部的交换操作,所以复杂度退化为n^2,所以在面对基本有序的排序算法选择时候,一般会选择堆排或者归并排序算法。

平均空间复杂度:O(nlogn),针对快排的空间负复杂度,或许有的人会有这样的疑问:快排不是每次只借助了一个空间吗?不应该是O(1) 吗?

就空间复杂度来说,主要是递归造成的栈空间的使用,最好情况,递归树的深度为log2n,其空间复杂度也就为O(logn),最坏情况,需要进行n‐1递归调用,其空间复杂度为O(n),平均情况,空间复杂度也为O(logn)。



© 著作权归作者所有

上一篇: 堆排序
下一篇: 希尔排序
此鱼不得水
粉丝 3
博文 41
码字总数 23991
作品 0
洛阳
私信 提问

暂无文章

秒杀系统思路

业务分析 技术挑战 请求响应要快:无论成功失败,需要尽快返回给用户 架构设计   前端:静态化   站点层:限制请求数   服务层:乐观锁写缓存   数据库CAP:读写高可用,一致性,扩容...

雷开你的门
6分钟前
4
0
最全的教育行业大数据解决方案,个个针对痛点

大数据的悄然兴起也带动了教育行业的革新,移动教育、云课堂等的出现,使得教育行业再次成为了可以中长期保持高景气的行业。然而,初涉数据领域的教育行业同时也面临着相当大的难题,还需要更...

朕想上头条
10分钟前
3
0
预约模块设计分析

1.预约功能描述: 预约是小程序中常见的一种商品管理系统,商家可根据商品或服务的特性,灵活设置预约细节,为用户提供线上预约服务,如场地预约,商品预定等,实现高效经营。 预约场景: ...

鱼煎
13分钟前
3
0
阿里云日志服务构建网站实时分析大盘实战

场景分析 挖掘数据价值是当前企业级网站共同面临的问题。买买网是一个电商平台网站,每天拥有大量的用户访问和购买记录。为了引导用户直接消费,提升购买率和转化率,不同的用户类别需要推荐...

阿里云官方博客
14分钟前
2
0
TL665xF-EasyEVM开发板硬件处理器、NAND FLASH、RAM

广州创龙结合TI KeyStone系列多核架构TMS320C665x及Xilinx Artix-7系列FPGA设计的TL665xF-EasyEVM开发板是一款DSP+FPGA高速大数据采集处理平台,其底板采用沉金无铅工艺的6层板设计,适用于高...

Tronlong创龙
18分钟前
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部