- 插入排序也是一种常见的排序算法，插入排序的思想是：将数据分为有序部分和无序部分，每一步将一个无序部分的数据插入到前面已经排好序的有序部分中，直到插完所有元素为止。
- 时间复杂度：O(n^2)
- 稳定性：稳定
- 直接上动态图：
public class InsertSort {
public static void insertSort(int[] arr) {
//为空或者长度小于2直接返回
if (arr == null || arr.length < 2) {
return;
}
int length = arr.length;
for (int i = 1; i < length; i++) {
//要插入的元素
int temp = arr[i];
//记录插入元素的下标，从已排好序的最右边开始比较，找到比其大的数
int j = i;
while (j > 0 && temp < arr[j - 1]) {
arr[j] = arr[j - 1];
j--;
}
if (j != i) {
arr[j] = temp;
}
}
}
public static void main(String[] args) {
Random random = new Random();
int[] arr = new int[100000];
for (int i = 0; i < 100000; i++) {
int num = random.nextInt(300000);
arr[i] = num;
}
long start = System.currentTimeMillis();
insertSort(arr);
long end = System.currentTimeMillis();
System.out.println(end - start);
}
}
希尔排序
简介
希尔排序，是插入排序的一种进阶排序算法，通过一个不断缩小的增量序列，对无序序列反复的进行拆分并且对拆分后的序列使用插入排序的一种算法，所以也叫作缩小增量排序或者递减增量排序。
既然希尔排序也是使用插入排序进行序列排序操作的，为什么会有希尔排序呢？这是基于插入排序的两点性质而来：
- 对一个“几乎”已经排好序的无序序列，插入排序的效率是很高的，可以达到线性排序的效率。比如，当序列中只有一位元素没有在适当的位置，那么整个序列只需要移动该序列的位置即可达到完成排序的任务。
- 但是一般的无序序列不是一个“几乎”已经排好序的序列，所以插入排序是低效的。因为它每次只能移动一位元素。
平均时间复杂度：O(n logn)
基本步骤：假设给定一个无序序列
- 首先我们选择一个增量，尽量在2或者以上，但是个人建议不要是偶数，因为可能会出现重复分组，详细我就不解释了，这里的数组长度为10，那么为了演示，增量就为[3，2，1]，我这里就不搞啥啥啥的倍数了，看得懂就行，不要在乎细节，是吧，各位。
- 第一次以增量为3分组如下
- 然后对每个分组进行插入排序即可，得到的结果如下：
- 然后再对上面的数组已增量为2进行分组，如图：
- 再一次对每个小组做插入排序即可，结果如下：
- 最后再做一次增量为1的插入排序。也就是你们熟悉的插入排序
public class ShellSort {
public static void shellSort(int[] arr) {
//为空或者长度小于2直接返回
if (arr == null || arr.length < 2) {
return;
}
int length = arr.length;
int gap = 1;
//先找出最大的增量
while (gap < length) {
//保证为奇数增量，当增量为偶数时会出现重复分组
int i = gap * 3;
if (i >= length) {
break;
}
gap = i;
}
//开始对每个增量进行循环，逐渐缩小增量
for (; gap >= 1; gap /= 3) {
for (int i = gap; i < length; i++) {
int temp = arr[i];
int j = i - gap;
while (j >= 0 && arr[j] > temp) {
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = temp;
}
}
}
public static void main(String[] args) {
Random random = new Random();
int[] arr = new int[100000];
for (int i = 0; i < 100000; i++) {
int num = random.nextInt(300000);
arr[i] = num;
}
long start = System.currentTimeMillis();
shellSort(arr);
long end = System.currentTimeMillis();
System.out.println((end - start) / 1000.0);
}
}
