SYSTEM
插入排序
src/content/notes/system/插入排序.md 插入排序
直接插入
插入排序(Insertion Sort):在要排序的一组数中,假定前 n-1 个数已经排好序,现在将第 n 个数插到这个有序数列中,使得这 n 个数也是排好顺序的,如此反复循环,直到全部排好顺序
public class InsertSort {
public static void main(String[] args) {
int[] arr = {55, 22, 2, 5, 1, 3, 8, 5, 7, 4, 3, 99, 88};
for (int i = 1; i < arr.length; i++) {
for (int j = i; j > 0; j--) {
// 比较索引j处的值和索引j-1处的值,
// 如果索引j-1处的值比索引j处的值大,则交换数据,
// 如果不大,那么就找到合适的位置了,退出循环即可;
if (arr[j - 1] > arr[j]) {
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
}
System.out.println(Arrays.toString(arr));
}
}
插入排序时间复杂度:
- 比较的次数为:
(N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2 - 交换的次数为:
(N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)(N-1)/2=N^2/2-N/2 - 总执行次数为:
(N^2/2-N/2)+(N^2/2-N/2)=N^2-N
按照大 O 推导法则,保留函数中的最高阶项那么最终插入排序的时间复杂度为 O(N^2)
希尔排序
希尔排序(Shell Sort):也是一种插入排序,也称为缩小增量排序
实现思路:
- 选定一个增长量 h,按照增长量 h 作为数据分组的依据,对数据进行分组
- 对分好组的每一组数据完成插入排序
- 减小增长量,最小减为 1,重复第二步操作
希尔排序的核心在于间隔序列的设定,既可以提前设定好间隔序列,也可以动态的定义间隔序列,希尔排序就是插入排序增加了间隔
public class ShellSort {
public static void main(String[] args) {
int[] arr = {55, 22, 2, 5, 1, 3, 8, 5, 7, 4, 3, 99, 88};
// 确定增长量h的初始值
int h = 1;
while (h < arr.length / 2) {
h = 2 * h + 1;
}
// 希尔排序
while (h >= 1) {
// 找到待插入的元素
for (int i = h; i < arr.length; i++) {
// 把待插入的元素插到有序数列中
for (int j = i; j >= h; j -= h) {
// 待插入的元素是arr[j],比较arr[j]和arr[j-h]
if (arr[j] < arr[j - h]) {
int temp = arr[j];
arr[j] = arr[j - h];
arr[j - h] = temp;
}
}
}
// 减小h的值,减小规则为:
h = h / 2;
}
System.out.println(Arrays.toString(arr));
}
}
在希尔排序中,增长量 h 并没有固定的规则,有很多论文研究了各种不同的递增序列,但都无法证明某个序列是最好的,所以对于希尔排序的时间复杂度分析就认为 O(nlogn)