企业官网建设流程全解析

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->566

public 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)，需辅助数组

分治思想：由小到大