定义

快速排序（Quicksort）是对冒泡排序算法的一种改进。

排序流程

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

首先设定一个分界值，通过该分界值将数组分成左右两部分。
将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

原理图

代码实现

package com.example.activiti.algorithm;
?
import java.util.Arrays;
?
/**
 * 快排算法
 */
public class QuickSort {
 ? ?public static void main(String[] args) {
 ? ? ? ?//待排序的数组
 ? ? ? ?int[] a = {6,2,5,7,1,8,9,3,4};
 ? ? ? ?//开始角标
 ? ? ? ?int start = 0;
 ? ? ? ?//结束角标
 ? ? ? ?int end = a.length - 1;
 ? ? ? ?int[] sortArray = quickSort01(a,start,end);
 ? ? ? ?System.out.println("-------------------------");
 ? ? ? ?System.out.println(Arrays.toString(sortArray));
 ?  }
?
 ? ?/**
 ? ? * 快速排序
 ? ? * @param a ? ?  待排序数组
 ? ? * @param start  (拆分数组)开始位置
 ? ? * @param end ?  (拆分数组)结束位置
 ? ? * @return
 ? ? */
 ? ?private static int[] quickSort01(int[] a, int start, int end) {
 ? ? ? ?//基准值,数组的第一位当作基准值
 ? ? ? ?int pivot = a[start];
 ? ? ? ?int i = start;
 ? ? ? ?int j = end;
 ? ? ? ?//只要start<end就一直循环排序
 ? ? ? ?while(start < end){
 ? ? ? ? ? ?//从右向前移动查找小于基准值的值，并和基准值调换位置
 ? ? ? ? ? ?while((start < end) && (a[end] > pivot)){
 ? ? ? ? ? ? ? ?//角标往前移动
 ? ? ? ? ? ? ? ?end--;
 ? ? ? ? ?  }
 ? ? ? ? ? ?//从左向右移动查找大于基准值的值，并和基准值调换位置
 ? ? ? ? ? ?while((start < end) && (a[start] < pivot)){
 ? ? ? ? ? ? ? ?//角标向前移动
 ? ? ? ? ? ? ? ?start++;
 ? ? ? ? ?  }
 ? ? ? ? ? ?if((start < end) && (a[start] == a[end])){
 ? ? ? ? ? ? ? ?start++;
 ? ? ? ? ?  }else{
 ? ? ? ? ? ? ? ?//开始调换位置
 ? ? ? ? ? ? ? ?int temp = a[start];
 ? ? ? ? ? ? ? ?//将小的放基准值左边
 ? ? ? ? ? ? ? ?a[start] = a[end];
 ? ? ? ? ? ? ? ?//将大的放基准值右边
 ? ? ? ? ? ? ? ?a[end] = temp;
 ? ? ? ? ?  }
 ? ? ? ? ? ?System.out.println(Arrays.toString(a));
 ? ? ? ? ? ?if(start - 1 > i){
 ? ? ? ? ? ? ? ?//对临界值左边的数组排序
 ? ? ? ? ? ? ? ?a = quickSort01(a,i,start-1);
 ? ? ? ? ?  }
 ? ? ? ? ? ?if(end + 1 < j){
 ? ? ? ? ? ? ? ?//对临界值右边的数组排序
 ? ? ? ? ? ? ? ?a = quickSort01(a,end + 1,j);
 ? ? ? ? ?  }
 ? ? ?  }
 ? ? ? ?return a;
 ?  }
}

结果

[4, 2, 5, 7, 1, 8, 9, 3, 6]
[4, 2, 5, 6, 1, 8, 9, 3, 7]
[2, 4, 5, 6, 1, 8, 9, 3, 7]
[2, 4, 5, 6, 1, 8, 9, 3, 7]
[2, 4, 5, 3, 1, 8, 9, 6, 7]
[2, 4, 5, 3, 1, 8, 9, 6, 7]
[2, 4, 5, 3, 1, 8, 9, 6, 7]
[2, 4, 5, 3, 1, 6, 9, 8, 7]
[1, 4, 5, 3, 2, 6, 9, 8, 7]
[1, 2, 5, 3, 4, 6, 9, 8, 7]
[1, 2, 5, 3, 4, 6, 9, 8, 7]
[1, 2, 4, 3, 5, 6, 9, 8, 7]
[1, 2, 4, 3, 5, 6, 9, 8, 7]
[1, 2, 3, 4, 5, 6, 9, 8, 7]
[1, 2, 3, 4, 5, 6, 9, 8, 7]
[1, 2, 3, 4, 5, 6, 9, 8, 7]
[1, 2, 3, 4, 5, 6, 9, 8, 7]
[1, 2, 3, 4, 5, 6, 9, 8, 7]
[1, 2, 3, 4, 5, 6, 9, 8, 7]
[1, 2, 3, 4, 5, 6, 9, 8, 7]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
-------------------------
[1, 2, 3, 4, 5, 6, 7, 8, 9]

[数据结构与算法]快速排序算法

定义

排序流程

原理图

代码实现

相关视频