当前位置：首页 > news >正文

1.1.3 插入排序

news 2025/2/9 5:44:27

插入排序

1. 原理

时间复杂度O(N^2)，额外空间复杂度O(1)
算法流程按照最差情况来估计时间复杂度0~0 上有序
0~1上有序，从1往前看，if 当前数小于左边的数，就一直往前进行交换。
0~2上有序，从2往前看，if 当前数小于左边的数，就一直往前进行交换。
0~3上有序，从3往前看，if 当前数小于左边的数，就一直往前进行交换。
......
0~n-1上有序，从n-1往前看，if 当前数小于左边的数，就一直往前进行交换。例子
arr = [12, 11, 13, 5, 6]
ind = [0,   1,  2, 3, 4]有序部分， 无序部分
开始：[]      arr
0~0: arr[0] 有序[0,   1,  2, 3, 4][12, 11, 13, 5, 6][12]
0~1:  arr[1]: 11 > 12, swap, 有序部分[0,   1,  2, 3, 4][12, 11, 13, 5, 6]    arr[0] > arr[1],  swap(arr, 0, 1)[11, 12, 13, 5, 6]
0~2: arr[2] > arr[1], continue
0~3:[0,   1,  2, 3, 4][11, 12, 13, 5, 6]   arr[2] > arr[3],  swap(arr, 2, 3)[11,  5, 12, 13, 6]   arr[1] > arr[2],  swap(arr, 1, 2)[5,  11, 12, 13, 6]   arr[0] > arr[1],  swap(arr, 0, 1)0~4:
[0,   1,  2, 3, 4]
[5,  11, 12, 13, 6]   arr[3] > arr[4],  swap(arr, 3, 4)
[5,  11, 12, 6, 13]   arr[2] > arr[3],  swap(arr, 2, 3)
[5,  11, 6, 12, 13]   arr[1] > arr[2],  swap(arr, 1, 2)
[5,  6, 11, 12, 13]   ok插入排序的原理
插入排序的基本思想是将数组分成两个部分：已排序部分和未排序部分。
1. 初始状态：已排序部分包含数组的第一个元素，未排序部分包含剩余的元素。
2. 从未排序部分取出第一个元素，将其插入到已排序部分的适当位置。
3. 重复步骤 2，直到未排序部分为空。插入排序的时间复杂度
- **最坏情况时间复杂度**：O(n^2)，当数组是反序时。
- **最佳情况时间复杂度**：O(n)，当数组已经有序时。
- **平均情况时间复杂度**：O(n^2)。插入排序的空间复杂度 O(1)
插入排序的稳定性
插入排序是一个稳定的排序算法，因为相等元素的相对顺序不会改变。

2. code

插入排序


from test1 import *
def insertionSort(arr):if arr == [] or len(arr) < 2:returnfor i in range(1, len(arr)):for j in range(i-1, -1, -1):if arr[j] > arr[j + 1]:swap(arr, j, j + 1)else:breakreturn# for test
def main():testTime =  50000              # 500000maxSize = 100maxValue = 100succeed = Truefor i in range(testTime):arr1 = generateRandomArray(maxSize, maxValue)arr2 = copyArray(arr1)insertionSort(arr1)             # ------------------test-------------------------comparator(arr2)if (not isEqual(arr1, arr2)):succeed = FalseprintArray(arr1)printArray(arr2)breakif succeed:print("Nice!")else:print("Fucking fucked!")arr = generateRandomArray(maxSize, maxValue)printArray(arr)insertionSort(arr)printArray(arr)if __name__ == '__main__':main()