|
目录
插入排序
希尔排序
插入排序
插入排序(InsertionSort)，一般也被称为直接插入排序。（稳定排序）
对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增 1 的有序表
。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。
/**
* @packageName: com.sofwin.controller
* @author: wentao
* @date: 2022/10/31 11:06
* @version: 1.0
* @description: 插入算法
*/
public class InsertSort {
? ?public static void main(String[]args){
? ? ? ?int[] a = {9,3,7,2,5,8,1,4};
? ? ? ?insert(a);
? ? ? ?System.out.println(Arrays.toString(a));
? }
?
? ?public static void insert(int[] arr) {
?
?
? ? ? ?//i代表插入元素的索引
? ? ? ?for (int i = 1; i < arr.length; i++) {
? ? ? ? ? ?//代表待插入的值
? ? ? ? ? ?int t = arr[i];
? ? ? ? ? ?int j; //已排序区的索引
? ? ? ? ? ?for (j = i-1;j >= 0;j--) {
? ? ? ? ? ? ? ?//如果前面大 就插入即可
? ? ? ? ? ? ? ?if (arr[j] > t) {
? ? ? ? ? ? ? ? ? arr[j+1] =arr[j];
? ? ? ? ? ? ? }else {
? ? ? ? ? ? ? ? ? ?//如果t大于了 就直接退出即可
? ? ? ? ? ? ? ? ? ?break;
? ? ? ? ? ? ? }
? ? ? ? ? }
? ? ? ? ? ?//退出完毕后 我们将j的前一个插入t即可
? ? ? ? ? ?arr[j+1] = t;
? ? ? ? ? ?System.out.println("结果："+Arrays.toString(arr));
? ? ? }
? }
}
?
优化方式：
-
待插入元素进行比较时，遇到比自己小的元素，就代表找到插入位置，无序进行后序比较 -
插入的时候直接移动元素，无需交换元素
与选择排序比较：
-
二者平均时间复杂度是O（n^2） -
大部分情况下，插入都略优于选择 -
有序集合插入的时间复杂度为O(n) -
插入排序属于稳定排序算法，而选择属于不稳定排序算法
希尔排序
插入排序如果大的数在前面，需要移动很多次 ，希尔排序是为了解决插入排序的这个缺点
希尔排序(Shell Sort)是插入排序的一种，它是针对直接插入排序算法的改进。
?
希尔排序又称缩小增量排序，因 DL.Shell 于 1959 年提出而得名。
?
它通过比较相距一定间隔的元素来进行，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。（有各种不同的间隔的取法 ）
|