1. 选择排序

1.1 直接选择排序

1.1.1详细过程

1.1.2 代码实现

 //直接选择排序public static void sort(int[] arr){int left=0;do{int min=left;for(int i=left+1;i<arr.length;i++){//找到最小if(arr[i]<arr[min]) min=i;}//交换int tmp=arr[left];arr[left]=arr[min];arr[min]=tmp;left++;System.out.println("第"+left+"次: "+ Arrays.toString(arr));}while(left<arr.length);}public static void main(String[] args) {int[] arr=new int[]{1,56,88,66,35,2,8};sort(arr);}

运行结果：

1.1.3 复杂度和稳定性

• 时间复杂度O(N^2)
• 空间复杂度O(1)
• 稳定性: 稳定

1.2 堆排序

关于堆排序的内容，详细跳转堆排序

2. 交换排序

2.1 冒泡排序

由于大家对冒泡排序已经很熟悉了，所以在这里就不做多余解释，直接进行代码实现。

2.1.1 代码实现

    public static void sort(int[] arr) {boolean swapped;for (int i = 0; i < arr.length - 1; i++) {swapped = false;for (int j = 0; j < arr.length - 1 - i; j++) {if (arr[j] > (arr[j + 1])) {// 交换int tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;swapped = true;}}System.out.println("第" + (i + 1) + "遍：" + Arrays.toString(arr));// 如果这一轮没有发生交换，说明数组已经有序，可以提前结束if (!swapped) {break;}}}public static void main(String[] args) {int[] arr = new int[]{56, 1, 88, 66, 35, 7, 6, 2};sort(arr);}

运行结果

2.1.2 复杂度和稳定性

• 时间复杂度O(N^2)
• 空间复杂度O(1)
• 稳定性: 稳定

2.2 快速排序——挖坑法

2.2.1详细过程

2.2.2 代码实现

public static void sort(int[] arr, int left, int right) {if (left >= right || left >= arr.length || right < 0) return;int pos = arr[left]; // 挖坑，保存基准值int i = left, j = right;while (i < j) {// 从右侧开始，找到小于基准值的数while (i < j && arr[j] >= pos) {j--;}if (i < j) {arr[i] = arr[j]; // 将小于基准值的数填到左边坑中i++;}// 从左侧开始，找到大于基准值的数while (i < j && arr[i] <= pos) {i++;}if (i < j) {arr[j] = arr[i]; // 将大于基准值的数填到右边坑中j--;}}arr[i] = pos; // 将基准值填回坑中System.out.println(Arrays.toString(arr));sort(arr, left, i - 1); // 递归排序左半部分sort(arr, i + 1, right); // 递归排序右半部分}public static void main(String[] args) {int[] arr = new int[]{56, 1, 88, 66, 35, 7, 6, 2，8};sort(arr, 0, arr.length - 1);}

运行结果

2.2.3 复杂度和稳定性

• 时间复杂度O(N*logN)
• 空间复杂度O(1)
• 稳定性: 不稳定