午休前写个插入排序压压惊

叁歲伎倆 2023-06-28 08:44 9阅读 0赞

**目录**

原理

简单举例

注意

上代码

--------------------

### 原理 ###

有一组数，先认定第一个元素为有序序列，后面的都是无序序列，然后拿无序序列的第一个元素和有序序列的最后一个元素比，如果后者大于前者，那么插入到有序序列的末尾；如果前者大于后者，那么继续和有序序列的倒数第二个元素比，以此类推插入到有序序列中，直到有序序列是全部元素时排序完毕。

### 简单举例 ###

有一组数**\{8,18,6,88\}**，需要从小到大排列出来，步骤如下：

1，先认定一个有序序列**\{8\}**，即第一个元素；再认定一个无序序列**\{18,6,88\}**，即第一个后面的元素。然后开始；

2，取出无序序列的第一个元素18，用18和有序序列的最后一个，即和8比较，18>8，因此将18放在8的后面，此时有序序列为**\{8,18\} ****；**

3，取出无序序列的第一个元素6，用6和有序序列的最后一个，即和18比较，6<18，因此6放在18的前面，继续拿6和8(18的上一个元素)比较，6<8，所以把6放在8的前面，有序序列就两个元素，所以这一趟就比完了，此时有序序列为**\{6,8,18\}  ****；**

4，拿88和有序序列的最后一个元素18比较，88>18，所以这一趟比较完了，88直接放在18后面，此时有序序列的元素是四个**\{6,8,18,88\}，即已经比较完了。**

### **注意** ###

1，数组长度为n的话，需要遍历n-1趟，走完每趟都会给有序序列插入一个数，无序序列会少一个数，遍历第m趟时有序序列已经存在m个数，每趟最多需要遍历的次数就是n-m。

2，如果需要有大到小排列出来，那么建议每次拿无序序列的第一个元素先和有序序列的第一个元素比，因为此时如果前者大于后者，那么就不需要继续比下去了，直接可以进行下一趟遍历。

### 上代码 ###

/* 由小到大排列 */
    func main() {
    	arr := [...]int{79, 1, 90, 38, 76, 33, 17, 88}
    	fmt.Println("排序完成：", sortArrC1(arr[:]))
    }
    
    func sortArrC1(arr []int) []int {
    	fmt.Println("传入数组：", arr, "长度：", len(arr))
    	for i := range arr {
    		fmt.Println("key=", i)
    		preIndex := i - 1
    		currentV := arr[i]
    		for preIndex >= 0 && arr[preIndex] > currentV {
    			arr[preIndex+1] = arr[preIndex]
    			preIndex -= 1 // 继续跟有序序列的其他值比较(从后往前)
    		}
    		arr[preIndex+1] = currentV //如果比有序序列的最后一个元素大，直接跟到有序序列的后面即可
    		fmt.Println("i=", i, "\t当前数组=", arr)
    	}
    	return arr
    }

打印：

传入数组： [79 1 90 38 76 33 17 88] 长度： 8
    key= 0
    i= 0 	当前数组= [79 1 90 38 76 33 17 88]
    key= 1
    i= 1 	当前数组= [1 79 90 38 76 33 17 88]
    key= 2
    i= 2 	当前数组= [1 79 90 38 76 33 17 88]
    key= 3
    i= 3 	当前数组= [1 38 79 90 76 33 17 88]
    key= 4
    i= 4 	当前数组= [1 38 76 79 90 33 17 88]
    key= 5
    i= 5 	当前数组= [1 33 38 76 79 90 17 88]
    key= 6
    i= 6 	当前数组= [1 17 33 38 76 79 90 88]
    key= 7
    i= 7 	当前数组= [1 17 33 38 76 79 88 90]
    排序完成： [1 17 33 38 76 79 88 90]

## 黄昏时偷来你的肋骨酿酒  百年后醉得有血有肉 ##