数据结构与算法:插入排序

2023-12-14 18:25:15

原理

保证区间内排好顺序,逐渐将区间外数据插入到该区间中。

从局部扩散到整体。

第一次:保证0-1范围内有序
arr[0]和arr[1]对比,若arr[0] 大于 arr[1] ,交换两个值,
0-1范围内有序。

第二次:保证 0-2 范围内有序。
arr[2]和arr[1]比,若 arr[1] 大于arr[2],交换两个值。
arr[1]和arr[0]再比,arr[0] 大于 arr[1] ,交换两个值。
至此,0-2范围内有序。

第三次:保证0-3范围内有序
arr[3]和arr[2]比,若 arr[2] 大于arr[3],交换两个值。
arr[2]和arr[1]比,若 arr[1] 大于arr[2],交换两个值。
arr[1]和arr[0]再比,arr[0] 大于 arr[1] ,交换两个值。
至此,0-2范围内有序。

第i次:保证0-i范围内有序
arr[i]和arr[i-1]比,若 arr[i-1] 大于arr[i],交换两个值。

图解

在这里插入图片描述

复杂度

时间复杂度 O(n2)

  • 最好情况 O(n)
  • 最差情况 O(n2)
    额外空间复杂度 O(1)

代码实现

java
public static void insertSort(int[] array) {  
    if (array == null || array.length < 2) {  
        return;  
    }  
  
    for (int i = 1; i < array.length; i++) {  // 控制第几次循环  
        for (int j = i; j > 0; j--) {  
            if (array[j] < array[j - 1]) {  
                swap(array, j, j -1);  
            }  
        }  
    }  
}
kotlin
fun insertionSort(array: IntArray) {  
    if (array.size < 2) {  
        return  
    }  
  
    for (i in 1 until array.size) {  // 0 ~ i 做到有序   抓扑克牌  
        for (j in i - 1 downTo 0) {  
            if (array[j] > array[j + 1]) {  
                swap(array, j, j + 1)  
            }  
        }  
    }  
}

文章来源:https://blog.csdn.net/yztbydh/article/details/134985395
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。