-
插入排序-直接插入排序
基本思想：把整个要排序的数列分为两部分，一个是有序，其余是无序，把无序数组内容逐渐加入有序数组内容进行排序，直至无序数组内容为空
实现思路：把一个无序数字加入有序数组排序方式可以先找到要插入的下标，然后该下标之后的元素后移
效率：
时间复杂度：O（n^2）.
java实现：
public class InsertSort { public static void main(String[] args) { // int[] array = {3, 9, -1, 10, 20}; // sort(array); // System.out.println(Arrays.toString(array)); int[] array = new int[80000]; for (int i = 0; i < 80000; i++) { array[i] = (int) (Math.random() * 80000); } LocalDateTime localDateTime1 = LocalDateTime.now(); System.out.println("执行前" + localDateTime1.format(DateTimeFormatter.ofPattern("yyyy-MM-DD " + "HH-mm-ss"))); sort(array); LocalDateTime localDateTime2 = LocalDateTime.now(); System.out.println("执行后" + localDateTime2.format(DateTimeFormatter.ofPattern("yyyy-MM-DD " + "HH-mm-ss"))); } static void sort(int[] array) { // 下标从1开始，因为0看做是一个有序的 for (int i = 1; i < array.length; i++) { // 新的将要插入的数据 int insertVal = array[i]; int insertIndex = i - 1; while (insertIndex >= 0 && insertVal < array[insertIndex]) { array[insertIndex + 1] = array[insertIndex]; insertIndex--; } array[insertIndex + 1] = insertVal; } } }
JS实现：
function insertSort (arr) {
for (var i = 1; i < arr.length; i++) {
var temp = arr[i];
//实际上这个可以拆开成for里面加一个if
for (var j = i - 1; j >= 0 && temp < arr[j]; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = temp;
}
return arr;
}
-
插入排序-希尔排序
基本思想：（其实就是直接插入排序的变种，就变了一点点）
选择一个增量组成一个数组，进行排序，之后增量减半，直至增量为1；（一开始就排序两个数，然后越来越多，最后到1）
每个子数组用直接插入排序进行排序
java实现：
```java
public class ShellSort {
public static void main(String[] args) {
// int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
// sort(arr);
// System.out.println(Arrays.toString(arr));
int[] array = new int[80000];
for (int i = 0; i < 80000; i++) {
array[i] = (int) (Math.random() * 80000);
}
LocalDateTime localDateTime1 = LocalDateTime.now();
System.out.println("执行前" + localDateTime1.format(DateTimeFormatter.ofPattern("yyyy-MM-DD "
+ "HH-mm-ss-SSS")));
sort(array);
LocalDateTime localDateTime2 = LocalDateTime.now();
System.out.println("执行后" + localDateTime2.format(DateTimeFormatter.ofPattern("yyyy-MM-DD "
+ "HH-mm-ss-SSS")));
}
static void sort(int[] arr) {
int length = arr.length;
int gap = length/2;
while (gap > 0) {
for (int i = gap; i < length; i++) {
int index = i - gap;
int insertVal = arr[i];
while (index >= 0 && insertVal < arr[index]) {
arr[index+gap] = arr[index];
index = index - gap;
}
arr[index + gap] = insertVal;
}
// System.out.println(Arrays.toString(arr));
gap = gap/2;
}
}
}
```
js实现
```javascript
function shellSort(arr) {
var gap = Math.floor(arr.length / 2);
while (gap >= 1) {
for (var i = gap; i < arr.length; i++) {
var temp = arr[i];
for (var j = i - gap; j >= 0 && temp < arr[j]; j = j - gap) {
arr[j + gap] = arr[j];
}
arr[j + gap] = temp;
}
gap = Math.floor(gap / 2);
}
return arr
}
```