Java数据结构与算法——快速排序

Panda 发布于2019-08-16 11:12 / 1183人阅读

摘要：快排是一种不稳定的排序算法，在经过排序后，等值的元素的相对位置可能发生改变。

声明：码字不易，转载请注明出处，欢迎文章下方讨论交流。

前言：Java数据结构与算法专题会不定时更新，欢迎各位读者监督。本篇文章介绍排序算法中最常用也是面试中最容易考到的排序算法——快排，包括快排的思想和原理、java快排代码、快排的特点性能和快排的适用场景。

0、其他排序算法索引(待更)

java数据结构与算法——桶排序
java数据结构与算法——插入排序

1、快速排序思想及原理

事实上，快速排序是堆冒泡排序的一种改进。

它的基本思想是：通过一趟排序将要排序的数据分割为两部分，第一部分所有数据比第二部分的所有数据小，按照这种思路将两部分数据再次分别进行快速排序，可以使用递归完成，最终使得整个数据序列有序。

具体来讲，在待排数据中找一个基准数据（通常取第一个数），接下来将待排数据中比基准数据小的放在待排数据的左侧，将比待排数据中比基准数据大的放在待排数据右侧。此时，左右两个分区的元素相对有序，接着采用上述思路继续对左右两个分区继续排序，直到各分区只有一个元素位置。这里用到了一个典型的分治思想。下面举例说明：

待排序列依次为47、29、71、99、78、19、24、47。为了区分两个47，将后面的47下面增加一个下划线。

步骤：
1、选取一个基准数，一般选第0个元素47。
2、将比基准数小的移动到左侧，比基准数大的移动到右侧，相等的不移动，此时基准数位置为K。
3、对左右两侧重复步骤1和步骤2，直到左右侧细分到只有一个元素。

快排的难点也就是在第2步，怎么移动各个数据？
<1> 首先从数列的右边开始往左找，设下标为i，也就是i--操作，找到第一个比基准数小的值，让他与基准数交换；
<2> 接着开始从左往右找，设下标为j，也就是j++，找到第一个比基准数大的值，让他与基准数交换位置；
<3> 重复1和2，直到i和j相遇时结束，最后基准值所在位置为k。

2、java快排代码

public class QuickSort {
    private int[] array;
    public QuickSort(int[] array){
        this.array = array;
    }
    
    public void printSort(){
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }
    
    public void sort(){
        quicksort(array,0,array.length -1);
    }
    
    private void quicksort(int[] array,int begin,int end){
        if(beginbase){ //从右往左扫，如果元素比基准值大
                    j--;  //则右边标记--，直到找到第一个比基准值小的，停止扫描
                }
                if(i
测试代码
public class SortTest {
    public static void main(String[] args) {
        teseQuickSort();
    }

    private static void teseQuickSort(){
        int[] array = {3,5,7,3,8,9,6,1,0};
        QuickSort qs = new QuickSort(array);
        qs.sort();
        qs.printSort();
    }
}
3、快排的特点及性能
快排是在冒泡排序之上改进而来的，冒泡排序每次只能交换相邻的两个元素，而快排则是跳跃式的交换，交换距离很大，总的比较次数和交换次数少了很多，速度也快了很多。
快排的平均时间复杂度为O(nlogn)，事实上，大多数情况下，排序速度要快于这个时间复杂度。快排实际上是采用的一种分而治之的思想，把问题分解为一个个的小问题去逐一解决，最终在把结果组合起来。
快排因为递归调用，所以空间复杂度为O(logn)。
快排是一种不稳定的排序算法，在经过排序后，等值的元素的相对位置可能发生改变。
快排基本上被认为是相同数量级中所有排序算法中平均性能最好的。
4、快排的适用场景
快排由于相对简单而且性能不错，所以快排适用于几乎绝大多数场合。
其他排序算法索引(待更)
java数据结构与算法——桶排序
java数据结构与算法——插入排序
码字不易，如对您有帮助，欢迎点赞收藏打赏^_^

GPU云服务器云服务器快速排序算法最好的快速排序算法最快速的排序算法 java快速排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/71079.html

Java面试题：稳定和不稳定排序算法之间的区别-MergeSort与QuickSort

摘要：稳定与不稳定算法示例以下图片解释了稳定和不稳定的排序是如何工作的这就是稳定和不稳定排序算法之间的区别。稳定排序算法的一些常见示例是合并排序，插入排序和冒泡排序。 showImg(https://segmentfault.com/img/remote/1460000018913243); 来源 | 愿码(ChainDesk.CN)内容编辑愿码Slogan | 连接每个程序员的故事网...

wanghui 2019-08-16 16:46 评论0 收藏0
七大排序算法总结(java)

摘要：前面介绍了七大算法的思想与实现步骤，下面来做一个归总。直到无序区中的数为零，结束排序。步骤以从小到大为例，排序数组大小为。比较完以后则排序结束。堆排序思想堆排序是采用树的形式的数据结构来进行排序的，其中每一个堆都是完全二叉树。前面介绍了七大算法的思想与实现步骤，下面来做一个归总。排序方法平均复杂度最坏复杂度最好复杂度辅助空间稳定性直接选择排序 O(n^2...

cartoon 2019-08-14 14:09 评论0 收藏0
Java数据结构与算法——插入排序

摘要：当序列本身有序时，插入排序的时间复杂度为。因为此时的分区内数据往往是近似有序的，所以使用快排并不一定优于插入排序。声明：码字不易，转载请注明出处，欢迎文章下方讨论交流。前言：Java数据结构与算法专题会不定时更新，欢迎各位读者监督。本篇文章介绍排序算法中插入排序算法，包括插入排序的思路，适用场景，性能分析，java代码等 0、其他排序算法索引(待更) java数据结构与算法——快速...

骞讳护 2019-08-15 15:19 评论0 收藏0
跳槽季如何快速全面复习面试题

摘要：排序算法和集合工具类排序算法和集合工具类。面试官总是问排序算法也不是在难为你，而是在考察你的编程功底。你首先要理解多线程不仅仅是和那么简单，整个并发包下面的工具都是在为多线程服务。去年的这个时候楼主通过两个月的复习拿到了阿里巴巴的 offer，有一些运气，也有一些心得，借着跳槽季来临特此分享出来。简单梳理一下我的复习思路，同时也希望和大家一起交流讨论，一起学习，如果不对之处欢迎指正一...

keke 2019-08-16 14:25 评论0 收藏0
Java排序算法之——快速排序

摘要：代码片段语言组织能力有限，直接上代码排序算法之快速排序参数为需要排序的数组参数为数组的起始下角标即参数为数组的最后下角标即经过一轮排序，已经将数组分为左右两部分进行递归排序总结快速排序的精髓在于分治思想，分而治之，它的时间复杂度为。算法简述所谓快速排序算法是基于交换排序和递归思想的，它的速度的确如名字所示——快！并且这种一算一般被用作数量级比较大的数据当中，在大数据中有着很重要的地...

Yangyang 2019-08-14 12:19 评论0 收藏0