冒泡排序（Bubble Sort）
arr[0] 与 arr[1]比较，如果前面元素大就交换，如果后边元素大就不交换。然后依次arr[1]与arr[2]比较，第一轮将最大值排到最后一位。
第二轮arr.length-1个元素进行比较，将第二大元素排到倒数第二位。直到某一轮元素位置没有交换或者结束最后一轮结束排序。这是冒泡排序改良版本。
//冒泡排序
public void test1() {int[] arr = {5, 2, 8, 3, 1, 6};//i是冒泡次数for (int i = 0; i < arr.length - 1; i++) {//每一轮将flag设置成true，当已经排好后直接返回，不需要进行完整个循环boolean flag = true;//j需要排序的元素个数for (int j = 0; j < arr.length - i - 1; j++) {if (arr[j] > arr[j + 1]) {// 交换arr[j+1]和arr[j]int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;flag = false;}}if(flag == true){break;}}//arr = [1, 2, 3, 5, 6, 8]System.out.println("arr = " + Arrays.toString(arr));
}
选择排序（Selection Sort）
选择排序每次从待排序的元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的元素排完。
从数组中选择出最小值放在第一个，将之前第一个元素和最小值之前所在索引位交换，依次进行第二个、第三个…
//选择排序
public void test2() {int[] arr = {5, 2, 8, 3, 1, 6};for (int i = 0; i < arr.length - 1; i++) {int minIndex = i;for (int j = i + 1; j < arr.length; j++) {//当前元素与下一个元素比较,记录较小的索引if (arr[j] < arr[minIndex]) {minIndex = j;}}// 交换arr[i]和arr[minIndex]int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}//arr = [1, 2, 3, 5, 6, 8]System.out.println("arr = " + Arrays.toString(arr));
}
插入排序（Insertion Sort）
插入排序是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。
第一个元素天然排序；第二个元素如果比第一个小就插入到第一个前面；第三个与第一个小就插入到第一个前面，如果比第二个小就插入到第二个前面；依次类推…
//插入排序
public void test3() {int[] arr = {5, 2, 8, 3, 1, 6};// 外部循环从第二个元素开始，// 因为我们将第一个元素视为已排序部分for (int i = 1; i < arr.length; i++) {int temp = arr[i];int j = i - 1;// 将当前值key和前面的值进行比较，// 如果前面的值>key 则将值往后移1位while (j >= 0 && arr[j] > temp ) {arr[j + 1] = arr[j];j--;}// 在不小当前值temp的位置，插入当前值temparr[j + 1] = temp;}//arr = [1, 2, 3, 5, 6, 8]System.out.println("arr = " + Arrays.toString(arr));
}
希尔排序（Shell Sort）
希尔排序是一种改进的插入排序算法，它的基本思想是将待排序的数组按照一定的间隔进行分组，对每组使用插入排序算法进行排序，然后缩小间隔，再对分组进行排序，直到间隔为1为止。
逐渐减小间隔大小的方法有助于提高排序过程的效率，可以减少比较和交换的次数。这是希尔排序算法的一个关键特点。
//希尔排序
public void test4() {//第一轮比如步长为5,拿出array[i],array[i+5]...,6与5,2与7,8与9等排序后array = {6, 2, 8, 3, 1, 5,7,9,4};//第二轮比如步长为3,第二轮拿出array[i],array[i+3]...,6与3与7,2与1与9,8与5与4,排序后array = {3, 1, 4, 6, 2, 5,7,9,8};//第三轮比如步长为1,进行插入排序int[] array = {5, 2, 8, 3, 1, 6,7,9,4};int increment = array.length / 2;while (increment >= 1){for (int i = increment; i < array.length; i++) {int j = i - increment;int temp = array[i];// 寻找插入位置并移动数据while (j >= 0 && array[j] > temp) {array[j + increment] = array[j];j -= increment;}array[j + increment] = temp;}// 设置新的增量increment /= 2;}//arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]System.out.println("arr = " + Arrays.toString(array));
}
快速排序（Quick Sort）
快速排序是一种分治思想的排序算法，它的基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后再分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
int[] array = {5, 2, 8, 3, 1, 6,7,9,4};
第一次拿最大索引元素4,将比4大的都放后边,比4小的都放前面
array = {3,1, 2,4,5,8, 6,7,9}
元素4索引位置已经确定
比4小的{3,1, 2}再以2为中心,小的排前面,大的排后边,确定了2的顺序。
因为1,3在2的前后,只有一个元素,也就确定了1,3顺序。
比4大的{5,8, 6,7,9}再以9为中心,依次类推...
public class Quick {public static void main(String[] args) {int[] arr = {5, 2, 8, 6, 1, 3};int[] expectedArr = {1, 2, 3, 5, 6, 8};Quick.quickSort(arr, 0, arr.length - 1);System.out.println("arr = " + Arrays.toString(arr));Assertions.assertArrayEquals(expectedArr, arr);}// 接收一个数组 arr，一个低索引 low ，和一个高索引 high 作为参数public static void quickSort(int[] arr, int low, int high) {// 检查 low 是否小于 high。如果不是，则意味着数组只有一个元素或为空，因此不需要排序if (low < high) {int pivot = partition(arr, low, high);quickSort(arr, low, pivot - 1);quickSort(arr, pivot + 1, high);}}/*** 取最后一个元素作为枢轴元素，将较小的元素放在左边，较大的元素放在右边* @param arr 输入数组* @param low 低位索引* @param high 高位索引* @return 枢轴所在位置*/private static int partition(int[] arr, int low, int high) {// 将最后一个元素作为枢轴元素（ arr[high] ）int pivot = arr[high];// 将 i 初始化为 low - 1，用于跟踪较小元素的索引int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] < pivot) {// 如果当前元素 arr[j] 小于枢轴元素，则增加 i 并交换 arr[i] 和 arr[j]// 较小元素索引+1i++;// 将当前元素 arr[j] 放在较小元素索引位置// 将较小元素放在前面swap(arr, i, j);}// 其他情况，则较小元素索引没有增加，说明当前元素应该放在右边}// 将枢轴元素（ arr[high] ）与索引 i + 1 处的元素交换。// 确保枢轴元素左边是较小元素，右边是较大元素swap(arr, i + 1, high);// 将 i + 1 作为枢轴索引返回return i + 1;}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}
