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

前言：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(begin<end){  //i和j没相遇之前比较各数据与基准值大小
            int base = array[begin];  //取第一个值为基准值
            int i = begin;  //左标记为i
            int j = end;    //右标记为j
            
            //一趟排序，找到比基准值大的在基准值右，比基准值小的在基准值左
            while(i<j){
                //从右往左扫描
                while(i<j && array[j]>base){ //从右往左扫，如果元素比基准值大
                    j--;  //则右边标记--，直到找到第一个比基准值小的，停止扫描
                }
                if(i<j){
                    array[i]=array[j];  //交换右扫描第一个比基准值小的数
                    i++;  //i标记右移一位
                }
                //从左往右扫描
                while(i<j && array[i]<base){//从左往右扫，如果元素比基准值小
                    i++;  //则左标记++，直到找到第一个比基准值大的，停止扫描
                }
                if(i<j){
                    array[j]=array[i];  //交换左扫描第一个比基准值大的数
                    j--;  //j标记左移一位
                }
            }  //此时基准值左右两侧相对有序
            
            array[i] = base;  //此时i为中间位置k
            
            quicksort(array,begin,i-1);  //左侧按照快排思路，递归
            
            quicksort(array,i+1,end);    //右侧按照快排思路，递归
        }
    }    
}

测试代码

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数据结构与算法——插入排序

码字不易，如对您有帮助，欢迎点赞收藏打赏^_^