插入排序

[hunterhug]

https://hunterhug.github.io/goa.c/#/algorithm/sort/insert_sort

Description

[Carlos9986]

作者你好，想问这里if的作用是什么？是否可以省略？因为去掉if不影响测试结果，代码如下：

package main

import "fmt"

func InsertSort(list []int) {

	n := len(list)

	// 进行 N-1 轮迭代

	for i := 1; i <= n-1; i++ {

		deal := list[i] // 待排序的数

		j := i - 1      // 待排序的数左边的第一个数的位置

		// 如果第一次比较，比左边的已排好序的第一个数小，那么进入处理

		if deal < list[j] {//note:if判断作用？？？可以去掉吗？？？

			// 一直往左边找，比待排序大的数都往后挪，腾空位给待排序插入

			for ; j >= 0 && deal < list[j]; j-- {

				list[j+1] = list[j] // 某数后移，给待排序留空位

			}

			list[j+1] = deal // 结束了，待排序的数插入空位

		}
	}
}

func InsertSortTest(s []int){

	n := len(s)

	for i:=1;i<=n-1;i++ {

		insertNum:=s[i]//不能通过index交换，因为“list[j+1] = list[j]”可能导致原index-value对改变，所以只好利用数值而不是索引，注意与SelectSort区别

		j:=i-1

		for ; (j >= 0) && (insertNum< s[j]); j--{

			s[j+1] = s[j]

		}

		s[j+1]=insertNum

	}
}


func main() {
	list := []int{5}
	InsertSort(list)
	fmt.Println(list)
	s:=[]int{5}
	InsertSortTest(s)
	fmt.Println(s)

	list1 := []int{5, 9}
	InsertSort(list1)
	fmt.Println(list1)
	s1:=[]int{5, 9}
	InsertSortTest(s1)
	fmt.Println(s1)

	list2 := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
	InsertSort(list2)
	fmt.Println(list2)
	s2:=[]int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
	InsertSortTest(s2)
	fmt.Println(s2)
}

[hunterhug]

作者你好，想问这里if的作用是什么？是否可以省略？因为去掉if不影响测试结果，代码如下：

package main

import "fmt"

func InsertSort(list []int) {

	n := len(list)

	// 进行 N-1 轮迭代

	for i := 1; i <= n-1; i++ {

		deal := list[i] // 待排序的数

		j := i - 1      // 待排序的数左边的第一个数的位置

		// 如果第一次比较，比左边的已排好序的第一个数小，那么进入处理

		if deal < list[j] {//note:if判断作用？？？可以去掉吗？？？

			// 一直往左边找，比待排序大的数都往后挪，腾空位给待排序插入

			for ; j >= 0 && deal < list[j]; j-- {

				list[j+1] = list[j] // 某数后移，给待排序留空位

			}

			list[j+1] = deal // 结束了，待排序的数插入空位

		}
	}
}

func InsertSortTest(s []int){

	n := len(s)

	for i:=1;i<=n-1;i++ {

		insertNum:=s[i]//不能通过index交换，因为“list[j+1] = list[j]”可能导致原index-value对改变，所以只好利用数值而不是索引，注意与SelectSort区别

		j:=i-1

		for ; (j >= 0) && (insertNum< s[j]); j--{

			s[j+1] = s[j]

		}

		s[j+1]=insertNum

	}
}


func main() {
	list := []int{5}
	InsertSort(list)
	fmt.Println(list)
	s:=[]int{5}
	InsertSortTest(s)
	fmt.Println(s)

	list1 := []int{5, 9}
	InsertSort(list1)
	fmt.Println(list1)
	s1:=[]int{5, 9}
	InsertSortTest(s1)
	fmt.Println(s1)

	list2 := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
	InsertSort(list2)
	fmt.Println(list2)
	s2:=[]int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
	InsertSortTest(s2)
	fmt.Println(s2)
}

没错：

// 如果第一次比较，比左边的已排好序的第一个数小，那么进入处理
        if deal < list[j] {

这个是可以去掉的，没有任何影响。下面的 for 循环会找到这个数的位置，然后插进去。