vlambda博客
学习文章列表

Java实现快速排序

1、排序算法简介
下面看一下七种内排序(待排序数据放在内存)算法的分类。
插入排序类
  • 直接插入排序

  • 希尔排序

选择排序类
  • 简单选择排序

  • 堆排序

交换排序类
  • 冒泡排序

  • 快速排序

归并排序类
  • 归并排序


根据算法的简单性进行分类:

  • 简单算法:冒泡、简单选择、直接插入

  • 改进算法:希尔、堆、归并、快速


排序算法的性能主要受三个方面影响:

  • 时间性能

  • 辅助空间

  • 算法的复杂性


七种排序算法的各种指标对比如下图所示。


这七种排序算法,应该说没有一种是绝对占优的。冒泡排序逻辑最简单,这个相信大家都会,而堆排序我也写过一篇文章了专门介绍 

本文介绍的快速排序算法,可以认为是最慢的冒泡排序的升级。


2、Java实现快速排序的代码

快速排序算法的思想以及代码的注释都在下面,大家可以直接将代码copy到本地方便学习。


package com.bobo.sort;

/**
 * 快速排序思想:
 * 1、从数组中选取一个元素作为基准值(一般是第一个),将待排序的数组分成左右两部分,左边的部分小于基准值,右边的部分大于基准值;
 * 2、使用左右两个指针向中间移动(可以约定右指针先移动),左边的指针移到到比基准值大的下标时停下,右边的指针移动到比基准小的下标时停下,
 * 然后双方交换数组元素,继续向左、向右移动;
 * 3、当左右指针重合时,有两种情况:
 * 基准值大于重合处元素:将基准值与重合处元素交换,一轮结束,以重合处下标为分界线,分成左右两部分,递归排序;
 * 基准值小于等于重合处元素:将基准值与重合处上一个元素交换,一轮结束,以重合处上一个下标为分界线,分成左右两部分,递归排序;
 */

public class QuickSort {
    /**
     * 用于验证待排序序列,避免出现数组下标越界异常
     */

    public static boolean valid(int[] array,int base,int low,int high){
        // 避免出现数组下标越界异常
        if(base>low || base>high || low>high){
            return false;
        }
        //只有一个元素的情况:base=low=high
        if(base == low && low == high){
            return false;
        }
        //只有两个元素的情况:base<low=high
        if(base < low && low == high){
            //只有两个元素时,直接比较交换,无需走快排
            if(array[base] > array[high]){
                int temp = array[base];
                array[base] = array[high];
                array[high] = temp;
            }
            return false;
        }
        //三个及三个以上元素的情况:base<low<high
        return true;
    }

    /**
     * 快速排序
     * @param array 待排序数组
     * @param base 基准值下标
     * @param low low下标
     * @param high high下标
     */

    public static void qSort(int[] array,int base,int low,int high){
        if(!valid(array,base,low,high)){
            return;
        }
        int i=low,j=high;
        for (;;){
            // 右指针移动
            while (array[j] >= array[base] && j>i){
                j--;
            }
            // 左指针移动
            while (array[i] <= array[base] && j>i){
                i++;
            }
            // 左右指针重合时,走if
            if(j==i){
                if(array[i] < array[base]){
                    // 基准值大于重合处元素时,走if;将基准值与重合处元素交换
                    int temp = array[base];
                    array[base] = array[i];
                    array[i] = temp;
                    // 分成左右两半,递归排序
                    qSort(array,base,low,i-1);
                    qSort(array,i+1,i+2,high);
                }else if(array[i] >= array[base]){
                    // 基准值小于等于重合处元素,走else;将基准值与重合处上一个元素交换
                    int temp = array[base];
                    array[base] = array[i-1];
                    array[i-1] = temp;
                    // 分成左右两半,递归排序
                    qSort(array,base,low,i-2);
                    qSort(array,i,i+1,high);
                }
                // 一轮结束,return
                return;
            }else{
                // 左右指针没重合时,走else;交换左右指针对应的元素
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] array = new int[]{-419,-419,452,451,267,-205,-114,82,-323,0};
        qSort(array,0,1,array.length-1);
        for (int i : array) {
            System.out.println(i);
        }

    }
}


为了确保代码的正确性,我专门找了力扣的一道题做验证,详情请见力扣的912题-排序数组,https://leetcode-cn.com/problems/sort-an-array/。

学习快速排序然后写代码花了一个小时,从第一次运行到通过这期间改bug也花了一个小时,幸好最终是ok的。