1.冒泡排序n^2外层遍历轮数【最多 n-1 轮】内层每轮循环遍历1遍将最大值放最右【每一轮内层只遍历未排序部分】冒泡交换操作可以保持稳定遇到相等数字直接跳过不交换数组分为左侧无序区 右侧有序区2.插入排序n^2每次插入要和前面已经排好序的数遍历一遍外层遍历待插入数字一共 n-1 轮从第二个元素开始逐个插入内层往左遍历左侧有序部分从最右开始大数后移当前数字插入有序区空位eg:打扑克牌-整理手牌从乱序整理出注意和冒泡不一样插入后移 插入数组分为左侧有序区 右侧无序区可以保持稳定插入到相同数的后面就好public static void insertSort(int[] arr) { int n arr.length; // 外层n-1轮从第二个元素开始逐个插入 for (int i 1; i n; i) { int temp arr[i]; // 待插入的数字 int j; // 内层往左遍历左边有序区比temp大的全部后移 //eg如果要插入第八个那么从下标7开始遍历 for (j i - 1; j 0 arr[j] temp; j--) { arr[j 1] arr[j]; } // 空位插入temp比如2移到3然后2还减了1所以要1才回到2 arr[j 1] temp; } }3.选择排序n^2先完整遍历找到最值最后只交换 1 次每轮最多一次交换外层 n-1 轮内层找右侧最小值下标最后和 i 交换一轮仅 1 次交换选择排序不稳定:换的时候相对位置会发生改变665-566public static void selectSort(int[] arr) { int n arr.length; // 外层控制每一轮要填充的位置i共n-1轮 for (int i 0; i n - 1; i) { int minIndex i; // 假设当前i是最小值下标 // 内层i右侧无序区间找真正最小值下标 for (int j i 1; j n; j) { if (arr[j] arr[minIndex]) { minIndex j; } } // 找到最小值和当前i位置交换 int temp arr[i]; arr[i] arr[minIndex]; arr[minIndex] temp; } }4.快速排序nlogn操作:随机选一个pivot大的放右边小的放左边。一直分到单个数层数:logn每层遍历 n 个元素:n极端有序数组会退化至 O (n²)【每次选到最大的变成n层】分治思想 :由大到小原地快排不开新数组必须双指针不稳定根源跨距离交换会打乱等值元素的先后顺序5.归并排序先随便拆 然后一直递归拆到最里层再向上合并拆分数组对半二分拆分不是随便拆固定从中间切两半递归拆到每组只剩 1 个元素天然有序合并自下而上不断合并两个有序小数组拼成大有序数组复杂度拆分深度 logn每层所有子数组合并总操作量为 n整体时间 O (n log n)特性稳定排序合并过程可以选择相同数排前面的需要额外临时数组空间 O (n)。即外层分治拆分对半切分递归至单元素 内层核心合并两个有序子数组复杂度每层总遍历 n递归层数 logn稳定 O (n log n)需辅助数组分治思想由小到大