一、二维数组的基本概念

使用二维数组的元素

示例代码：

package initialize;/* @Date: 2023-3-15 周三 16:37* @Author: Special Care* @Description: TODO 静态初始化二维数组* @Version: 1.0.0*/
public class ArrayDemo {public static void main(String[] args) {// 二维数组的静态初始化的语法与一维数组相似，例如：//int[][] array = {{7,1,9,6},{4,2,8,1},{6,0,3,5}};int[][] array = {{7,1},{4,2,8,1},{6,0,3}};// 可以使用“数组名[横排下标][竖排下标]”语法来表示要访问的元素System.out.println(array[2][1]);// 0}
}

二、二维数组的本质

二维数组的本质就是：将多个一维数组作为另一个一维数组的元素

三、二维数组的动态初始化

示例代码：

package initialize;/* @Date: 2023-3-15 周三 16:57* @Author: Special Care* @Description: TODO 动态初始化二维数组* @Version: 1.0.0*/
public class ArrayDemo2 {public static void main(String[] args) {//int[][] array = new int[3][4];int[][] array = new int[3][];array[0] = new int[2];array[0][0] = 7;array[0][1] = 1;System.out.println(array[0][1]);// 1array[1] = new int[4];array[1][0] = 4;array[1][1] = 2;array[1][2] = 8;array[1][3] = 1;System.out.println(array[1][2]);// 8}
}

四、二维数组的遍历

示例代码：

package initialize;import java.util.Arrays;/* @Date: 2023-3-15 周三 17:14* @Author: Special Care* @Description: TODO 遍历二维数组* @Version: 1.0.0*/
public class ArrayDemo3 {public static void main(String[] args) {int[][] array = {{7,1,9,6},{4,2,8,1},{6,0,3,5}};for (int i = 0; i < array.length; i++) {System.out.println(Arrays.toString(array[i]));for (int j = 0; j < array[i].length; j++) {System.out.println(array[i][j]);}}/* [7, 1, 9, 6]* 7* 1* 9* 6* [4, 2, 8, 1]* 4* 2* 8* 1* [6, 0, 3, 5]* 6* 0* 3* 5*/}
}

五、冒泡排序（Bubble sort）

冒泡排序原理

实现步骤分析

示例代码：

package sort;import java.util.Arrays;/* @Date: 2023-3-15 周三 18:46* @Author: Special Care* @Description: TODO 冒泡排序* @Version: 1.0.0*/
public class BubbleSort {public static void main(String[] args) {// 创建需要排序的数组对象int[] array = {8,1,4,9,0,3,5,2,7,6};for (int i = 0; i < array.length - 1; i++) {// 遍历数组// 循环变量j：某元素的下标，将始终与下标为j+1的元素进行对比// 注意：数组的最右侧元素没有对比对象，所以遍历至 i < array.length - 1// 注意：内层循环的次数是递减的，需要改为 j < array.length - 1 - ifor (int j = 0; j < array.length - 1 - i; j++) {// 如果左侧元素更大，则换位if (array[j] > array[j+1]){int temp = array[j];array[j] = array[j+1];array[j+1] = temp;}// 输出显示数组System.out.println(Arrays.toString(array));}System.out.println();}/* [1, 8, 4, 9, 0, 3, 5, 2, 7, 6]* [1, 4, 8, 9, 0, 3, 5, 2, 7, 6]* [1, 4, 8, 9, 0, 3, 5, 2, 7, 6]* [1, 4, 8, 0, 9, 3, 5, 2, 7, 6]* [1, 4, 8, 0, 3, 9, 5, 2, 7, 6]* [1, 4, 8, 0, 3, 5, 9, 2, 7, 6]* [1, 4, 8, 0, 3, 5, 2, 9, 7, 6]* [1, 4, 8, 0, 3, 5, 2, 7, 9, 6]* [1, 4, 8, 0, 3, 5, 2, 7, 6, 9] [1, 4, 8, 0, 3, 5, 2, 7, 6, 9]* [1, 4, 8, 0, 3, 5, 2, 7, 6, 9]* [1, 4, 0, 8, 3, 5, 2, 7, 6, 9]* [1, 4, 0, 3, 8, 5, 2, 7, 6, 9]* [1, 4, 0, 3, 5, 8, 2, 7, 6, 9]* [1, 4, 0, 3, 5, 2, 8, 7, 6, 9]* [1, 4, 0, 3, 5, 2, 7, 8, 6, 9]* [1, 4, 0, 3, 5, 2, 7, 6, 8, 9] [1, 4, 0, 3, 5, 2, 7, 6, 8, 9]* [1, 0, 4, 3, 5, 2, 7, 6, 8, 9]* [1, 0, 3, 4, 5, 2, 7, 6, 8, 9]* [1, 0, 3, 4, 5, 2, 7, 6, 8, 9]* [1, 0, 3, 4, 2, 5, 7, 6, 8, 9]* [1, 0, 3, 4, 2, 5, 7, 6, 8, 9]* [1, 0, 3, 4, 2, 5, 6, 7, 8, 9] [0, 1, 3, 4, 2, 5, 6, 7, 8, 9]* [0, 1, 3, 4, 2, 5, 6, 7, 8, 9]* [0, 1, 3, 4, 2, 5, 6, 7, 8, 9]* [0, 1, 3, 2, 4, 5, 6, 7, 8, 9]* [0, 1, 3, 2, 4, 5, 6, 7, 8, 9]* [0, 1, 3, 2, 4, 5, 6, 7, 8, 9] [0, 1, 3, 2, 4, 5, 6, 7, 8, 9]* [0, 1, 3, 2, 4, 5, 6, 7, 8, 9]* [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]* [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]* [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]* [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]* [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]* [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]* [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]* [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]* [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]*/}
}

package sort;import java.util.Arrays;
import java.util.Random;/* @Date: 2023-3-15 周三 18:46* @Author: Special Care* @Description: TODO 统计冒泡排序中的对比、换位次数、耗时以及生成随机数组成数组* @Version: 1.0.0*/
public class BubbleSort2 {public static void main(String[] args) {// 创建需要排序的数组对象//int[] array = {8,1,4,9,0,3,5,2,7,6};// ----- 以下代码用于生成随机数组成的数组 -----// 随机数工具对象Random random = new Random();// 将生成的随机数的数值大小上限(不包含此值)int numberBound = 100;// 将生成的随机数的数量，也是数组的长度int numbersCount = 50;//创建数组，数组长度就是将生成的随机数的数量int[] array = new int[numbersCount];// 遍历数组for (int i = 0; i < array.length; i++) {array[i] = random.nextInt(numberBound);}// 输出显示生成的数组System.out.println(Arrays.toString(array));// ----- 生成随机数组成的数组，完成！-----// 声明变量：统计对比次数int compareCount = 0;// 声明变量：统计换位次数int swapCount = 0;// 记录排序之前的时间值long startTime = System.currentTimeMillis();// 外层的循环for (int i = 0; i < array.length - 1; i++) {// 遍历数组// 循环变量j：某元素的下标，将始终与下标为j+1的元素进行对比// 注意：数组的最右侧元素没有对比对象，所以遍历至 i < array.length - 1// 注意：内层循环的次数是递减的，需要改为 j < array.length - 1 - ifor (int j = 0; j < array.length - 1 - i; j++) {// 对比次数自增compareCount++;// 如果左侧元素更大，则换位if (array[j] > array[j+1]){// 执行换位int temp = array[j];array[j] = array[j+1];array[j+1] = temp;// 换位次数自增swapCount++;}// 输出显示数组//System.out.println(Arrays.toString(array));}//System.out.println();}//记录排序之后的时间值long endTime = System.currentTimeMillis();// 输出显示生成的数组System.out.println(Arrays.toString(array));// 输出结果System.out.println("对比次数：" + compareCount);System.out.println("换位次数：" + swapCount);System.out.println("耗时：" + (endTime - startTime) + "毫秒");}
}

六、选择排序（Selection sort）

选择排序原理

实现步骤分析

示例代码：

package sort;import java.util.Arrays;/* @Date: 2023-3-15 周三 20:04* @Author: Special Care* @Description: TODO 选择排序* @Version: 1.0.0*/
public class SelectionSort {public static void main(String[] args) {// 创建需要排序的数组int[] array = {8,1,4,9,0,3,5,2,7,6};// 输出数组，观察原数组System.out.println(Arrays.toString(array));System.out.println();// 新的循环for (int i = 0; i < array.length; i++) {// 遍历数组// 使用j表示被对比的元素下标，暂时使用1作为循环初始条件for (int j = i + 1; j < array.length; j++) {// 第1个元素的下标，也是于其它元素对比的元素的下标int minIndex = i;// 如果被遍历到的元素更小，则换位if (array[minIndex] > array[j]){int temp = array[minIndex];array[minIndex] = array[j];array[j] = temp;}// 输出数组，观察数组的变化System.out.println(Arrays.toString(array));}System.out.println();}/* [8, 1, 4, 9, 0, 3, 5, 2, 7, 6] [1, 8, 4, 9, 0, 3, 5, 2, 7, 6]* [1, 8, 4, 9, 0, 3, 5, 2, 7, 6]* [1, 8, 4, 9, 0, 3, 5, 2, 7, 6]* [0, 8, 4, 9, 1, 3, 5, 2, 7, 6]* [0, 8, 4, 9, 1, 3, 5, 2, 7, 6]* [0, 8, 4, 9, 1, 3, 5, 2, 7, 6]* [0, 8, 4, 9, 1, 3, 5, 2, 7, 6]* [0, 8, 4, 9, 1, 3, 5, 2, 7, 6]* [0, 8, 4, 9, 1, 3, 5, 2, 7, 6] [0, 4, 8, 9, 1, 3, 5, 2, 7, 6]* [0, 4, 8, 9, 1, 3, 5, 2, 7, 6]* [0, 1, 8, 9, 4, 3, 5, 2, 7, 6]* [0, 1, 8, 9, 4, 3, 5, 2, 7, 6]* [0, 1, 8, 9, 4, 3, 5, 2, 7, 6]* [0, 1, 8, 9, 4, 3, 5, 2, 7, 6]* [0, 1, 8, 9, 4, 3, 5, 2, 7, 6]* [0, 1, 8, 9, 4, 3, 5, 2, 7, 6] [0, 1, 8, 9, 4, 3, 5, 2, 7, 6]* [0, 1, 4, 9, 8, 3, 5, 2, 7, 6]* [0, 1, 3, 9, 8, 4, 5, 2, 7, 6]* [0, 1, 3, 9, 8, 4, 5, 2, 7, 6]* [0, 1, 2, 9, 8, 4, 5, 3, 7, 6]* [0, 1, 2, 9, 8, 4, 5, 3, 7, 6]* [0, 1, 2, 9, 8, 4, 5, 3, 7, 6] [0, 1, 2, 8, 9, 4, 5, 3, 7, 6]* [0, 1, 2, 4, 9, 8, 5, 3, 7, 6]* [0, 1, 2, 4, 9, 8, 5, 3, 7, 6]* [0, 1, 2, 3, 9, 8, 5, 4, 7, 6]* [0, 1, 2, 3, 9, 8, 5, 4, 7, 6]* [0, 1, 2, 3, 9, 8, 5, 4, 7, 6] [0, 1, 2, 3, 8, 9, 5, 4, 7, 6]* [0, 1, 2, 3, 5, 9, 8, 4, 7, 6]* [0, 1, 2, 3, 4, 9, 8, 5, 7, 6]* [0, 1, 2, 3, 4, 9, 8, 5, 7, 6]* [0, 1, 2, 3, 4, 9, 8, 5, 7, 6] [0, 1, 2, 3, 4, 8, 9, 5, 7, 6]* [0, 1, 2, 3, 4, 5, 9, 8, 7, 6]* [0, 1, 2, 3, 4, 5, 9, 8, 7, 6]* [0, 1, 2, 3, 4, 5, 9, 8, 7, 6] [0, 1, 2, 3, 4, 5, 8, 9, 7, 6]* [0, 1, 2, 3, 4, 5, 7, 9, 8, 6]* [0, 1, 2, 3, 4, 5, 6, 9, 8, 7] [0, 1, 2, 3, 4, 5, 6, 8, 9, 7]* [0, 1, 2, 3, 4, 5, 6, 7, 9, 8] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]*/}
}

七、插入排序（Insertion sort）

插入排序原理

实现步骤分析

示例代码：

package sort;import java.util.Arrays;/* @Date: 2023-3-15 周三 21:45* @Author: Special Care* @Description: TODO 插入排序* @Version: 1.0.0*/
public class InsertionSort {public static void main(String[] args) {// 创建需要排序的数组int[] array = {8,1,4,9,0,3,5,2,7,6};// 输出数组，观察原数组System.out.println(Arrays.toString(array));System.out.println();// 从下标为1的元素开始，反复对比左侧元素for (int i = 1; i < array.length; i++) {// 当前需要确定位置的元素的下标，暂时假设是数组的最右侧元素int j = i;// 当j > 0时循环while (j > 0){// 判断j指向的元素与其左侧元素的大小if (array[j] < array[j - 1]){// 当左侧元素j - 1更大时，执行换位int temp = array[j];array[j] = array[j - 1];array[j - 1] = temp;// j自减，表示左向移动j--;// 输出数组，观察本次换位后的效果System.out.println(Arrays.toString(array));}else {// 当不满足条件(左侧元素小于或等于当前元素)时，跳出循环break;}}// 输出空白行System.out.println();}/* [8, 1, 4, 9, 0, 3, 5, 2, 7, 6] [1, 8, 4, 9, 0, 3, 5, 2, 7, 6] [1, 4, 8, 9, 0, 3, 5, 2, 7, 6]* [1, 4, 8, 0, 9, 3, 5, 2, 7, 6]* [1, 4, 0, 8, 9, 3, 5, 2, 7, 6]* [1, 0, 4, 8, 9, 3, 5, 2, 7, 6]* [0, 1, 4, 8, 9, 3, 5, 2, 7, 6] [0, 1, 4, 8, 3, 9, 5, 2, 7, 6]* [0, 1, 4, 3, 8, 9, 5, 2, 7, 6]* [0, 1, 3, 4, 8, 9, 5, 2, 7, 6] [0, 1, 3, 4, 8, 5, 9, 2, 7, 6]* [0, 1, 3, 4, 5, 8, 9, 2, 7, 6] [0, 1, 3, 4, 5, 8, 2, 9, 7, 6]* [0, 1, 3, 4, 5, 2, 8, 9, 7, 6]* [0, 1, 3, 4, 2, 5, 8, 9, 7, 6]* [0, 1, 3, 2, 4, 5, 8, 9, 7, 6]* [0, 1, 2, 3, 4, 5, 8, 9, 7, 6] [0, 1, 2, 3, 4, 5, 8, 7, 9, 6]* [0, 1, 2, 3, 4, 5, 7, 8, 9, 6] [0, 1, 2, 3, 4, 5, 7, 8, 6, 9]* [0, 1, 2, 3, 4, 5, 7, 6, 8, 9]* [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]*/}
}

八、希尔排序（Shell sort）

实现步骤分析

示例代码：

package sort;import java.util.Arrays;/* @Date: 2023-3-16 周四 09:53* @Author: Special Care* @Description: TODO 希尔排序* @Version: 1.0.0*/
public class ShellSort {public static void main(String[] args) {// 创建需要排序的数组int[] array = {8,1,4,9,0,3,5,2,7,6};// 输出数组，观察原数组System.out.println(Arrays.toString(array));System.out.println();// 多轮循环：缩减增量// 初始条件：增量(gap)值为数组长度除以2// 循环条件：增量 > 0// 条件自变：增量自除2for (int gap = array.length / 2; gap > 0; gap /= 2){// 从与增量值大小相等的下标位置开始，向右循环for (int i = gap; i < array.length; i++) {// 接下来的循环表示向左找“同组”的元素尝试对比及必要的换位// j：左侧“同组”元素的下标，即被对比元素的下标，因为可能有多个，所以需要循环for (int j = i - gap; j >= 0; j -= gap) {// 判断需要对比的2个元素的大小，进行必要的换位// 注意：使用的下标分别是j和j+gap，后者是因为j的值变化时需要跟随调整if (array[j] > array[j + gap]){// 执行换位int temp = array[j];array[j] = array[j + gap];array[j + gap] = temp;// 输出数组，观察换位后的数组System.out.println(Arrays.toString(array));}else {// 基于插入排序的特点，一旦左侧元素更小// 那么，更左侧的元素肯定也是更小的// 则，没有必要继续循环下去break;}}}System.out.println();}/* [8, 1, 4, 9, 0, 3, 5, 2, 7, 6] [3, 1, 4, 9, 0, 8, 5, 2, 7, 6]* [3, 1, 2, 9, 0, 8, 5, 4, 7, 6]* [3, 1, 2, 7, 0, 8, 5, 4, 9, 6] [2, 1, 3, 7, 0, 8, 5, 4, 9, 6]* [2, 1, 0, 7, 3, 8, 5, 4, 9, 6]* [0, 1, 2, 7, 3, 8, 5, 4, 9, 6]* [0, 1, 2, 7, 3, 4, 5, 8, 9, 6]* [0, 1, 2, 4, 3, 7, 5, 8, 9, 6]* [0, 1, 2, 4, 3, 7, 5, 6, 9, 8]* [0, 1, 2, 4, 3, 6, 5, 7, 9, 8] [0, 1, 2, 3, 4, 6, 5, 7, 9, 8]* [0, 1, 2, 3, 4, 5, 6, 7, 9, 8]* [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]*/}
}

九、归并排序（Merge sort）

实现步骤分析

示例代码：

package sort;import java.util.Arrays;/* @Date: 2023-3-16 周四 15:38* @Author: Special Care* @Description: TODO 归并排序* @Version: 1.0.0*/
public class MergeSort {public static void main(String[] args) {// 创建需要排序的数组int[] array = {8,1,4,9,0,3,5,2,7,6};// 输出数组，观察原数组System.out.println(Arrays.toString(array));System.out.println();// 调用mergeSort()方法进行排序int[] finalArray = mergeSort(array,0, array.length - 1);// 输出数组，观察最终结果数组System.out.println(Arrays.toString(finalArray));}/* 这是一个自定义的方法，方法的声明可以参考main()方法* @param array 原数组* @param start 需要被拆分的区间的起始元素下标* @param end 需要被拆分的区间的结束元素下标* @return 合并后的有序新数组*/public static int[] mergeSort(int[] array,int start,int end){// 为防止递归出现“死循环”，当end与start相同时(发生在尝试对长度为1的数组再拆分)，不必再执行if (end == start){// 使用return返回当前片段的新数组return new int[]{array[start]};}// 求数组需要被拆分的区间的中间点int mid = start + (end - start) / 2;// 创建2个新的数组，分别表示拆分之后的左侧区域和右侧区域int[] leftArray = mergeSort(array, start, mid);int[] rightArray = mergeSort(array, mid + 1, end);// 创建新的数组，用于存放合并后的有序结果int[] newArray = new int[leftArray.length + rightArray.length];// 声明变量，分别表示leftArray、rightArray、newArray的下标变量int l = 0,r = 0,n = 0;// 当leftArray和rightArray都没有遍历结束之前，一直循环while (l < leftArray.length && r < rightArray.length){// 对比2个数组中的元素//if (leftArray[l] <= rightArray[r]){// 左侧数组的元素更小，将其放到新数组中//    newArray[n++] = leftArray[l++];//}else {// 右侧数组的元素更小，将右侧数组的元素放到新数组中//    newArray[n++] = rightArray[r++];//}newArray[n++] = leftArray[l] <= rightArray[r] ? leftArray[l++] : rightArray[r++];}// 如果左侧数组还有剩余，可直接依次全部填充到新数组中while (l < leftArray.length){newArray[n++] = leftArray[l++];}// 如果右侧数组还有剩余，可直接依次全部填充到新数组中while (r < rightArray.length){newArray[n++] = rightArray[r++];}// 返回新数组return newArray;}/* [8, 1, 4, 9, 0, 3, 5, 2, 7, 6] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]*/
}

十、快速排序（Quick sort）

快速排序原理（1）

实现步骤分析（1）

示例代码（1）：

package sort;import java.util.Arrays;/* @Date: 2023-3-16 周四 17:10* @Author: Special Care* @Description: TODO 快速排序* @Version: 1.0.0*/
public class QuickSort1 {public static void main(String[] args) {// 创建需要排序的数组int[] array = {8, 1, 4, 9, 0, 3, 5, 2, 7, 6};// 输出数组，观察原数组System.out.println(Arrays.toString(array));System.out.println();// 执行快速排序quickSort(array, 0, array.length - 1);// 输出数组，观察排序后数组System.out.println(Arrays.toString(array));}/* 这是一个自定义的方法，方法的声明可以参考main()方法* 注意：快速排序本质上没有拆出新数组，也不需要合并，所以该方法不需要返回值* @param array 原数组* @param start 需要被拆分的区间的起始元素下标* @param end 需要被拆分的区间的结束元素下标*/public static void quickSort(int[] array, int start, int end){// 使用新的变量表示枢纽元位置的元素值int pivot = array[end];// 创建新的变量，用于表示“左侧区域”的最大下标(最右侧元素的下标)int x = start - 1;// 遍历数组片段，实现分出左右两个区域for (int i = start; i < end; i++) {// 判断当前元素是否小于或等于枢纽元if (array[i] <= pivot){// 判断当前元素的左侧是否已存在于大枢纽元的元素if (i - x > 1){// 将下标i与下标x+1位置的数据换位int temp = array[i];array[i] = array[x + 1];array[x + 1] = temp;// x自增x++;}else {// 更新x位置x = i;}}}// 将枢纽元放在左右两个区域的中间// 交换枢纽元与第1个大于枢纽元的位置的位置if (pivot < array[x + 1]){array[end] = array[x + 1];array[x + 1] = pivot;}// 如果左侧区域仍有多个元素，则递归// 因为x是左侧区域的最大下标(最右侧元素下标)// 若比需要处理的数组片段的最左侧元素下标大，则表示左侧区域存在超过1个元素if (x > start){quickSort(array, start, x);}// 如果右侧区域仍有多个元素，则递归// 提示：x是左侧区域的最大下标，其右侧还有1个枢纽元，如果存在右侧区域，则起始下标为x+2if (end - x - 1 > 1){quickSort(array, x + 2, end);}}/* [8, 1, 4, 9, 0, 3, 5, 2, 7, 6] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]*/
}

快速排序原理（2）

实现步骤分析（2）

示例代码（2）：

package sort;import java.util.Arrays;/* @Date: 2023-3-16 周四 17:10* @Author: Special Care* @Description: TODO 快速排序* @Version: 1.0.0*/
public class QuickSort2 {public static void main(String[] args) {// 创建需要排序的数组int[] array = {8, 1, 4, 9, 0, 3, 5, 2, 7, 6};// 输出数组，观察原数组System.out.println(Arrays.toString(array));System.out.println();// 执行快速排序quickSort(array, 0, array.length - 1);// 输出数组，观察排序后数组System.out.println(Arrays.toString(array));}/* 这是一个自定义的方法，方法的声明可以参考main()方法* 注意：快速排序本质上没有拆出新数组，也不需要合并，所以该方法不需要返回值* @param array 原数组* @param start 需要被拆分的区间的起始元素下标* @param end 需要被拆分的区间的结束元素下标*/public static void quickSort(int[] array, int start, int end){// 使用新的变量表示枢纽元位置的元素值int pivot = array[end];// 使用新的变量，表示左侧区域的最大下标,默认是当前需要处理的数组片段的最左侧int x = start;// 使用新的变量，表示右侧区域的最小下标,默认是当前需要处理的数组片段的最右侧int y = end;// y会递减，x递增，当x < y时循环while (x < y){// 从右至左找出第1个大于枢纽元的元素，并标记位置，当指向的元素小于或等于枢纽元时，跳出循环while (x < y && array[y] > pivot){y--;}// 从左至右找出小于枢纽元的元素，并标记位置，当指向的元素大于或等于枢纽元时，跳出循环while (x < y && array[x] < pivot){x++;}// 判断现在x与y指向的元素是否与枢纽元的大小相同if (x < y && array[x] == array[y]){// x与y指向的元素与枢纽元的大小相同，x向右移动，否则就会卡死x++;}else {// x与y指向的不是枢纽元，但x指向的元素大于或等于枢纽元，y指向的元素小于或等于枢纽元，则需要换位int temp = array[x];array[x] = array[y];array[y] = temp;}}// 如果左侧区域仍有元素，则递归if (x - 1 > start){quickSort(array, start, x - 1);}// 如果右侧区域仍有元素，则递归if (y + 1 < end){quickSort(array, y + 1, end);}}/* [8, 1, 4, 9, 0, 3, 5, 2, 7, 6] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]*/
}

关于快速排序的枢纽元

package sort;import java.util.Arrays;
import java.util.Random;/* @Date: 2023-3-16 周四 17:10* @Author: Special Care* @Description: TODO 使用随机枢纽元分别对升序、降序排列的数组进行快速排序，并统计对比、换位次数* @Version: 1.0.0*/
public class QuickSortAboutPivot {public static int compareCount = 0;public static int swapCount = 0;public static void main(String[] args) {// 创建需要排序的数组//int[] array = {8, 1, 4, 9, 0, 3, 5, 2, 7, 6};// 准备长度为100的升序数组//int[] array = new int[100];//for (int i = 0; i < array.length; i++) {//    array[i] = i;//}// 准备长度为100的降序数组int[] array = new int[100];for (int i = 0; i < array.length; i++) {array[i] = array.length - i;}// 输出数组，观察原数组System.out.println(Arrays.toString(array));System.out.println();// 执行快速排序quickSort(array, 0, array.length - 1);// 输出数组，观察排序后数组System.out.println(Arrays.toString(array));// 输出性能指标System.out.println("对比次数：" + compareCount);System.out.println("换位次数：" + swapCount);}/* 这是一个自定义的方法，方法的声明可以参考main()方法* 注意：快速排序本质上没有拆出新数组，也不需要合并，所以该方法不需要返回值* @param array 原数组* @param start 需要被拆分的区间的起始元素下标* @param end 需要被拆分的区间的结束元素下标*/public static void quickSort(int[] array, int start, int end){// 使用新的变量表示枢纽元位置的元素值//int pivot = array[end];// 使用随机位置的枢纽元Random random = new Random();int randomIndex = random.nextInt(end - start) + start;int pivot = array[randomIndex];// 使用新的变量，表示左侧区域的最大下标,默认是当前需要处理的数组片段的最左侧int x = start;// 使用新的变量，表示右侧区域的最小下标,默认是当前需要处理的数组片段的最右侧int y = end;// y会递减，x递增，当x < y时循环while (x < y){// 从右至左找出第1个大于枢纽元的元素，并标记位置，当指向的元素小于或等于枢纽元时，跳出循环while (x < y && array[y] > pivot){y--;}// 从左至右找出小于枢纽元的元素，并标记位置，当指向的元素大于或等于枢纽元时，跳出循环while (x < y && array[x] < pivot){x++;}// 对比次数自增compareCount++;// 判断现在x与y指向的元素是否与枢纽元的大小相同if (x < y && array[x] == array[y]){// x与y指向的元素与枢纽元的大小相同，x向右移动，否则就会卡死x++;}else {// x与y指向的不是枢纽元，但x指向的元素大于或等于枢纽元，y指向的元素小于或等于枢纽元，则需要换位int temp = array[x];array[x] = array[y];array[y] = temp;// 换位次数自增swapCount++;}}// 如果左侧区域仍有元素，则递归if (x - 1 > start){quickSort(array, start, x - 1);}// 如果右侧区域仍有元素，则递归if (y + 1 < end){quickSort(array, y + 1, end);}}
}

十一、排序算法的选取