说在前头：本人为大二在读学生，书写文章的目的是为了对自己掌握的知识和技术进行一定的记录，同时乐于与大家一起分享，因本人资历尚浅，能力有限，文章难免存在一些错漏之处，还请阅读此文章的大牛们见谅与斧正。若在阅读时有任何的问题，也可通过评论提出，本人将根据自身能力对问题进行一定的解答。
前言
快速排序（Quicksort）是对冒泡排序算法的一种改进，其算法的时间复杂度为O(Nlog2N)，算法效率较高。但算法不够稳定，当数据顺序较为整齐时，效率将会降低，最坏的情况会达到O(N2)。
01—算法思想
快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：设定一个基准的分界值（一般取最后一个或最后一个），通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。（下图所示是第一轮排序的流程展示图）
当基准点选用最左侧的数据45时，45需要与最右侧的数据进行对比，若最右侧的数据小于45时，则该数据需要与45发生位置的互换，否则无需做任何操作，如上图第一行的情况。
当基准点45经过位置的互换来到最右侧时，此时需要与最左侧未比较过的数据进行比较，若左侧的数据大于45则需要与45发生位置的互换，否则无需做任何操作，如上图第二行。
如此一直往复，直到基准点45的左侧所有数据都小于45，右侧都大于45时，该轮排序才结束（如上图最后一行）。此时只是一轮排序的结束，算法并未结束，因为45左右两侧的数据并未完成排序，我们还需要对左右两侧的数组再次进行快速排序，直到所有的数据都有序为止。
02—具体实现代码
Fast.java
package com.bosen.fast;
/**
* <p>快速排序</p>
* @author Bosen 2021/5/29 22:26
*/
public class Fast {
/*
* 待排序的数组
*/
private int[] array;
private static int count = 0;
public Fast(int[] array) {
this.array = array;
}
/*
* 执行排序
*/
public void sort() {
display("初始状态：");
recursiveSort(0, array.length-1);
}
/*
* 使用递归的方式
*/
public void recursiveSort(int low, int high) {
if (low >= high) return;
int tempLow = low;
int tempHigh = high;
int standard = array[low]; // 第一个元素为基准点
while (low < high) {
while (low < high && array[high] >= standard) {
high--;
}
swap(low, high);
while (low < high && array[low] <= standard) {
low++;
}
swap(low, high);
}
display("第"+(++count)+"轮排序：");
recursiveSort(tempLow, low-1);
recursiveSort(low+1, tempHigh);
}
/*
* 交换数据位置
*/
public void swap(int low, int high) {
int temp = array[high];
array[high] = array[low];
array[low] = temp;
}
/*
* 打印排序情况
*/
public void display(String msg) {
System.out.print(msg);
for (int i : array) {
System.out.print("\t"+i);
}
System.out.println();
}
}
Test.java
package com.bosen.fast;
public class Test {
public static void main(String[] args) {
int[] array = {45, 12, 23, 34, 78, 21, 98, 11};
Fast fast = new Fast(array);
fast.sort();
}
}
输出结果：
总结
此篇章节，主要介绍了快速排序算法的算法思想，并通过具体代码来体现。在下一篇中，我们将来讲述希尔排序算法，感兴趣的小伙伴们可以先点个关注哦！
👇扫描二维码关注