交换排序：冒泡排序和快速排序

冒泡排序

思路

通过多次遍历数组，比较相邻的元素，并交换它们，使得每次遍历结束后，最大（或最小）的元素都“冒泡”到数组的末尾

实现

public class  Main {public static void main(String[] args) {int[] arr = {1, 7, 8, 4, 5, 3};f(arr);for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}}static void f(int arr[]) {for (int i = 0; i < arr.length - 1; i++) {for (int j = 0; j < arr.length - 1 - i; j++) {if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}}
}          

快速排序

思路

(1)设定一个分界值【如最大索引位置的值】，通过该分界值将数组分成左右两部分：小于分界值的全部在其左边，大于或等于分界值的全部在其右边

(2)对(1)中分界分界值左右两部分都看做一个整体，按照(1)中思路再次分配

(3)重复(2)

实现

public class Main {public static void main(String[] args) {int[] arr = {64, 34, 25, 12, 22, 11, 90};quickSort(arr, 0, arr.length - 1);for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}}public static void quickSort(int[] arr, int left, int right) {if (left < right) {// 寻找分界值int pi = partition(arr, left, right);// 递归对分割点左边的子数组进行排序quickSort(arr, left, pi - 1);// 递归对分割点右边的子数组进行排序quickSort(arr, pi + 1, right);}}public static int partition(int[] arr, int left, int right) {int pivot = arr[right]; // 选择最后一个元素作为分界值int i = left - 1; // 初始化分界值的位置for (int j = left; j < right; j++) {// 如果当前元素小于分界值，则将其交换到分界点位置if (arr[j] < pivot) {i++;int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 将基准值交换到分界值位置int temp = arr[i + 1];arr[i + 1] = arr[right];arr[right] = temp;return i + 1;}
}