1.先从数列中取出一个数作为基准数（简单起见就选第一个数）
2.分区过程：将比这个数大的数全放到他的右边，比他小的数全放到他的左边（分治）
3.再对左右两边的区重复第一步和第二部操作，直到各区间只有一个数（递归）
可以理解为： 快速排序 = 冒泡 + 分治 + 递归
快排就是一种暴力排序法
package com.sscm.saas; import org.junit.Test; import java.util.Arrays; /** * @author samxie * @version 1.0 * @date 2021/12/27 19:40 **/ public class Test2 { @Test public void test10() { int arr[] = {12,2,432,4,5,6,2,34,7,3,2,2}; System.out.println(Arrays.toString(arr)); KSPX(arr); System.out.println(Arrays.toString(arr)); } public static void KSPX(int[] arr) { int l = 0; int h = arr.length - 1; KSPX(arr, 1, h); } private static void KSPX(int[] arr, int l, int h) { if (l < h) { int index = part(arr, l, h); KSPX(arr, l, h - 1); KSPX(arr, l + 1, h); } } private static int part(int[] arr, int l, int h) { int i = l; int j = h; int x = arr[l]; while (i < j) { while (arr[j] >= x && i < j) { j--; } if (i < j) { arr[i] = arr[j]; i++; } while (arr[i] <= x && i < j) { i++; } if (i < j) { arr[j] = arr[i]; j--; } } arr[i] = x; return i; } }
===========
快速排序 第二版
public class test3 { @Test public void test922() { int[] arr = {5, 1, 7, 3, 1, 343, 34443, 6, 9, 4}; quickSort(arr, 0, arr.length - 1); for (int i : arr) { System.out.print(i + "\t"); } } private static void quickSort(int[] arr, int leftIndex, int rightIndex) { if (leftIndex >= rightIndex) { return; } int left = leftIndex; int right = rightIndex; //待排序的第一个元素作为基准值 int key = arr[left]; //从左右两边交替扫描，直到left = right while (left < right) { while (right > left && arr[right] >= key) { //从右到左扫描，找到第一个的匀速 right--; } arr[left] = arr[right]; while (left < right && arr[left] <= key) { left++; } arr[right] = arr[left]; } //基准归位 arr[left] = key; //对基准值右边的元素进行 quickSort(arr, leftIndex, left - 1); quickSort(arr, right + 1, rightIndex); } }
