希尔排序

[hunterhug]

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

Description

[Carlos9986]

作者你好，在step内部使用的好像不是插入排序，更像是冒泡排序，代码对比如下，请指教：

package main

import "fmt"

// 增量序列折半的希尔排序

func ShellSort(list []int) {

	// 数组长度

	n := len(list)


	// 每次减半，直到步长为 1

	for step := n / 2; step >= 1; step /= 2 {

		// 开始插入排序，每一轮的步长为 step

		for i := step; i < n; i += step {

			for j := i - step; j >= 0; j -= step {

				// 满足插入那么交换元素

				if  list[j] > list[j+step]{  //note:感觉这里是冒泡排序，不是插入排序

					list[j], list[j+step] = list[j+step], list[j]

					continue

				}
				break

			}
		}
	}
}


func ShellSort2(s []int){

	n:= len(s)


	for step:=n/2;step>=1;step/=2{

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

			insertNum:=s[i]


			j:=i-step

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

				s[j+step]=s[j]

			}

			s[j+step]=insertNum

		}
	}
}


func main() {

	list := []int{5}
	ShellSort(list)
	fmt.Println(list)
	s:=[]int{5}
	ShellSort2(s)
	fmt.Println(s)

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

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

	list3 := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3, 2, 4, 23, 467, 85, 23, 567, 335, 677, 33, 56, 2, 5, 33, 6, 8, 3}
	ShellSort(list3)
	fmt.Println(list3)
	s3:=[]int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3, 2, 4, 23, 467, 85, 23, 567, 335, 677, 33, 56, 2, 5, 33, 6, 8, 3}
	ShellSort2(s3)
	fmt.Println(s3)
}

[hunterhug]

作者你好，在step内部使用的好像不是插入排序，更像是冒泡排序，代码对比如下，请指教：

package main

import "fmt"

// 增量序列折半的希尔排序

func ShellSort(list []int) {

	// 数组长度

	n := len(list)


	// 每次减半，直到步长为 1

	for step := n / 2; step >= 1; step /= 2 {

		// 开始插入排序，每一轮的步长为 step

		for i := step; i < n; i += step {

			for j := i - step; j >= 0; j -= step {

				// 满足插入那么交换元素

				if  list[j] > list[j+step]{  //note:感觉这里是冒泡排序，不是插入排序

					list[j], list[j+step] = list[j+step], list[j]

					continue

				}
				break

			}
		}
	}
}


func ShellSort2(s []int){

	n:= len(s)


	for step:=n/2;step>=1;step/=2{

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

			insertNum:=s[i]


			j:=i-step

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

				s[j+step]=s[j]

			}

			s[j+step]=insertNum

		}
	}
}


func main() {

	list := []int{5}
	ShellSort(list)
	fmt.Println(list)
	s:=[]int{5}
	ShellSort2(s)
	fmt.Println(s)

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

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

	list3 := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3, 2, 4, 23, 467, 85, 23, 567, 335, 677, 33, 56, 2, 5, 33, 6, 8, 3}
	ShellSort(list3)
	fmt.Println(list3)
	s3:=[]int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3, 2, 4, 23, 467, 85, 23, 567, 335, 677, 33, 56, 2, 5, 33, 6, 8, 3}
	ShellSort2(s3)
	fmt.Println(s3)
}

确实，里面是通过交换，而不是挪位来插入的，如果你看过插入排序那一章的逻辑，是元素向右挪位，然后找到位置插进去，其实我们也可以改成那样。

[cyj19]

多次分组进行插入排序，使得最后对整个列表排序时，列表已经是大致有序的，那么最后一次插入排序就会时间复杂度就趋向线性的。

func ShellSort(list []int) {
	n := len(list)

	// 增量每次减半
	for step := n / 2; step >= 1; step /= 2 {
		// 将step的整倍数分为一组进行插入排序
		for i := step; i < n; i += step {
			// 待排序的数
			deal := list[i]
			// 待排序的数的左边最近一个数的下标
			j := i - step
			// 在有序列表中寻找待排序数的插入位置
			for ; j >= 0 && deal < list[j]; j -= step {
				// 比待排序数大的数往后移
				list[j+step] = list[j]
			}
			// 此时deal > list[j]，那么待排序数的下标就是j+step
			list[j+step] = deal
		}
	}
}

[hunterhug]

多次分组进行插入排序，使得最后对整个列表排序时，列表已经是大致有序的，那么最后一次插入排序就会时间复杂度就趋向线性的。

func ShellSort(list []int) {
	n := len(list)

	// 增量每次减半
	for step := n / 2; step >= 1; step /= 2 {
		// 将step的整倍数分为一组进行插入排序
		for i := step; i < n; i += step {
			// 待排序的数
			deal := list[i]
			// 待排序的数的左边最近一个数的下标
			j := i - step
			// 在有序列表中寻找待排序数的插入位置
			for ; j >= 0 && deal < list[j]; j -= step {
				// 比待排序数大的数往后移
				list[j+step] = list[j]
			}
			// 此时deal > list[j]，那么待排序数的下标就是j+step
			list[j+step] = deal
		}
	}
}

越有序的数列，直接插入排序的效率越高，希尔排序通过分组使用直接插入排序，因为步长比 1 大，在一开始可以很快将无序的数列变得不那么无序，比较和交换的次数也减少，直到最后使用步长为 1 的直接插入排序，数列已经是相对有序了，所以时间复杂度会稍好一点。

[cyj19]

@hunterhug

多次分组进行插入排序，使得最后对整个列表排序时，列表已经是大致有序的，那么最后一次插入排序就会时间复杂度就趋向线性的。

func ShellSort(list []int) {
	n := len(list)

	// 增量每次减半
	for step := n / 2; step >= 1; step /= 2 {
		// 将step的整倍数分为一组进行插入排序
		for i := step; i < n; i += step {
			// 待排序的数
			deal := list[i]
			// 待排序的数的左边最近一个数的下标
			j := i - step
			// 在有序列表中寻找待排序数的插入位置
			for ; j >= 0 && deal < list[j]; j -= step {
				// 比待排序数大的数往后移
				list[j+step] = list[j]
			}
			// 此时deal > list[j]，那么待排序数的下标就是j+step
			list[j+step] = deal
		}
	}
}

越有序的数列，直接插入排序的效率越高，希尔排序通过分组使用直接插入排序，因为步长比 1 大，在一开始可以很快将无序的数列变得不那么无序，比较和交换的次数也减少，直到最后使用步长为 1 的直接插入排序，数列已经是相对有序了，所以时间复杂度会稍好一点。

感觉这个分组排序的想法和快速排序好像呀？

[hunterhug]

@hunterhug

多次分组进行插入排序，使得最后对整个列表排序时，列表已经是大致有序的，那么最后一次插入排序就会时间复杂度就趋向线性的。

func ShellSort(list []int) {
	n := len(list)

	// 增量每次减半
	for step := n / 2; step >= 1; step /= 2 {
		// 将step的整倍数分为一组进行插入排序
		for i := step; i < n; i += step {
			// 待排序的数
			deal := list[i]
			// 待排序的数的左边最近一个数的下标
			j := i - step
			// 在有序列表中寻找待排序数的插入位置
			for ; j >= 0 && deal < list[j]; j -= step {
				// 比待排序数大的数往后移
				list[j+step] = list[j]
			}
			// 此时deal > list[j]，那么待排序数的下标就是j+step
			list[j+step] = deal
		}
	}
}

越有序的数列，直接插入排序的效率越高，希尔排序通过分组使用直接插入排序，因为步长比 1 大，在一开始可以很快将无序的数列变得不那么无序，比较和交换的次数也减少，直到最后使用步长为 1 的直接插入排序，数列已经是相对有序了，所以时间复杂度会稍好一点。

感觉这个分组排序的想法和快速排序好像呀？

九九归一。

[TreeZeng]

这代码是不是有点问题 ?
希尔排序应该是像下面这样吧。因为例子中的序列比较长，所以用个少一点的序列来举例，方便一些。
比如，有这么一组序列：7 3 5 9 2 0 8 6，
第一次分组，取step为 8/2= 4，排序后，应该是这样的：2 0 5 6 7 3 8 9
第二次分组，取step为 4/2= 2，排序后，应该是这样的：2 0 5 3 7 6 8 9
第三次分组，取step为 2/2= 1，排序后，应该是这样的： 0 2 3 5 6 7 8 9

而你提供的代码运行结果是这样的：

第一次：[2 3 5 9 7 0 8 6]
第二次：[2 3 5 9 7 0 8 6]
第三次：[0 2 3 5 6 7 8 9]

所以我修改了下代码：

func ShellSort(list []int) {
	// 数组长度
	n := len(list)

	// 每次减半，直到步长为 1
	for step := n / 2; step >= 1; step /= 2 {
		// 开始插入排序，每一轮的步长为 step
		for i := step; i < n; i += step {
			for j := 0; j+step < n; j++ {
				// 满足插入那么交换元素
				if list[j+step] < list[j] {
					list[j], list[j+step] = list[j+step], list[j]
				}
			}
		}
		fmt.Println(list)
	}
}

[hunterhug]

该节有纰漏，已修改了若干次，可以重新阅读。