简介

快速排序（Quicksort），计算机科学词汇，适用领域Pascal，c++等语言，是对 冒泡排序 算法的一种改进。

原理

设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它左边，所有比它大的数都放到它右边，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。

代码实现

 package com.zyp.sort;

import java.util.Arrays;

/**
 * 快速排序
 * @author zyp
 * @create 2022/2/10
 */public class QuickSort {
    public static void main(String[] args){
        int[] array = new int[]{3,9,2,7,6,5,4,1,8};
        sort(array, 0, array.length-1);
        System.out.println(Arrays.toString(array));


    }

    /**
     * 排序
     * @param array 待排序数组
     * @param left 左边下标
     * @param right 右边下标
     */    public static void sort(int[] array ,int left, int right){
        int l = left;
        int r = right;
        int base = array[l];
        while (l < r){
            //base的右边找到一个比base小的元素为止
            while(array[r] >= base && l<r){
                r--;
            }
            //就将右边的值覆盖左边的值
            array[l] = array[r];
            //base的左边找到一个比base大的元素为止
            while (array[l] <= base && l<r){
                l++;
            }
            //就将左边的值覆盖右边的值
            array[r] = array[l];
        }

        array[l] = base;
        if(left < l-1){
            sort(array, left, l-1);
        }
        if(right > r+1){
            sort(array, r+1, right);
        }
    }
}
  

代码分析

1.我们将待排序数组的第一个数作为一个对比数据

2.从右边开始，和对比数据比较，直到比对比数据小，此时将右边的这个数据复制到左边

3.然后从左边开始，和这个对比数据比较直到比对比数据大，此时将左边的数据复制到右边

4.当右边与左边查找的下表相等的时候，我们将这个对比数据放入对应的位置

5.然后将这个对比数据分为左、右两部分，每部分重复1、2、3、4步骤

动态图

帮助理解