关于数据结构和算法:数据结构插入排序

插入排序的一种 Go 实现

package main

import "fmt"

// 插入排序是仅次于疾速排序的高效排序算法，插入排序和冒泡排序、抉择排序一样都是外部排序（内存）// 与其余两个不同的是插入排序是将无序的向有序的数组外面插入，因而区别于其余两个都是循环无序的排序算法
func InsertSort (arr *[5]int) {
    // 插入排序的核心思想是假如第一个元素为有序的，前面的都是无序的，挨个将前面无序的插入到后面有序的过程
    for i := 1; i < len(arr); i++ {insertVal := arr[i]
        insertIndex := i - 1

        // 降序
        for insertIndex >= 0 && arr[insertIndex] < insertVal {arr[insertIndex + 1] = arr[insertIndex] // 插入到以后地位的下一个地位
            insertIndex-- // 如果没有适合的地位向前持续找插入地位
        }
        // 插入
        if insertIndex + 1 != i {arr[insertIndex + 1] = insertVal
        }
        fmt.Printf("第 %d 次插入后 %v\n", i, *arr)
    }
}

func main(){arr := [5]int{23, 0, 12, 56, 34}
    InsertSort(&arr)
}

输入：

 第 1 次插入后 [23 0 12 56 34]
第 2 次插入后 [23 12 0 56 34]
第 3 次插入后 [56 23 12 0 34]
第 4 次插入后 [56 34 23 12 0]