Sorting Algorithms:Straight Insertion Sort
предисловие
Этот блог используется для обзора и консолидации этой слабой курицы и закладки прочного фундамента.
Основная мысль
Как следует из названия, это вставка нового элемента в отсортированный массив для формирования нового отсортированного массива.
Начиная с первого элемента, возьмите следующий элемент и сравните его, чтобы добиться сортировки для формирования нового массива,
Затем возьмите третий элемент и сравните его с массивом,
При сравнении начинать сравнение с последнего бита массива,
Если новый элемент меньше, чем элемент, с которым он сравнивается, то элемент сравнения перемещается назад, как
пока новый элемент не будет найден слева от массива, куда его следует вставить.
Анимированный пример
Анализ сложности алгоритма
| средний | худший | самый | стабильность | космическая сложность |
|---|---|---|---|---|
| O(n^2) | O(n^2) | O(n) | стабильность | O(1) |
p.s. Среднее количество сравнений и ходов составляет около (n ^ 2)/4, лучшая производительность при простой сортировке при прямой сортировке вставками, лучше, чем Selection & Bubble.
Код
import java.util.Arrays;
import java.util.Random;
/**
* Straight Insertion Sort
* 顾名思义，就是把一个新的元素插入已排好序的数组形成一个新的已排好序的数组
* 从第一个元素开始，取下一个元素比较后实现排序，形成新的数组，
* 再取第三个元素与该数组比较，
* 比较时从该数组的最后一位开始比较，
* 若新元素比与其比较的元素小，则将该比较的元素后移以为，
* 直到新元素比该数组左边找到其应该插入的位置
* <p>
* 算法复杂度分析
* 时间复杂度（平均） O(n^2) 外循环n次，内循环m次 m*n
* 时间复杂度（最坏） O(n^2) 外循环n次，内循环m次 m*n
* 时间复杂度（最好） O(n) ，数组已经排好序的情况，即当所有a[i] > a[i-1] 时不需要再执行内循环
* 空间复杂度 O(1)
* 稳定性 稳定
* <p>
* 平均比较和移动次数约为 (n^2)/4
* 直接插入排序时简单排序中性能最好的
* better than Selection & Bubble
*
* @author Wayne Zhang
* @date 2018/07/14
*/
public class InsertionSort {
public static void main(String[] args) {
int[] a = new int[10];
//random array
for (int i = 0; i < a.length; i++) {
Random rd = new Random();
a[i] = rd.nextInt(10);
}
System.out.println("Random Array :");
System.out.println(Arrays.toString(a));
System.out.println();
System.out.println("Insertion Sort :");
//插入排序
/*for(int i = 1;i<a.length;i++){
int key = a[i];
int index = i;
for(int j = i-1 ;j>=0;j--){
if(key<a[j]){
a[j+1]=a[j];
index = j;
}
}
a[index] = key;
}*/
//插入排序
//外循环规定从第二个元素开始，将元素插入到已排好的数组中
for (int i = 1; i < a.length; i++) {
//用key来表示插入的元素，若直接用a[i]表示，a[j+1]操作会更改a[i]的值
int key = a[i];
//j表示从已排好序的数组的最右边开始比较
int j = i - 1;
while (j >= 0 && key < a[j]) {
//若插入的元素小，则将被比较的元素后移一位
a[j + 1] = a[j];
j--;
}
//此时的a[j]代表着被插入元素左边相邻的那个元素
a[j + 1] = key;
}
System.out.println(Arrays.toString(a));
}
}
Ссылаться на
Гик для гиков: https://www.geeksforgeeks.org/insertion-sort/
10 лучших классических алгоритмов сортировки: https://www.cnblogs.com/onepixel/articles/7674659.html
«Структура данных Dahua»: https://book.douban.com/subject/6424904/