goa.c
goa.c copied to clipboard
hunterhug
希尔排序
https://hunterhug.github.io/goa.c/#/algorithm/sort/shell_sort
Description
作者你好，在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)
}
作者你好，在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) }
确实，里面是通过交换，而不是挪位来插入的，如果你看过插入排序那一章的逻辑，是元素向右挪位，然后找到位置插进去，其实我们也可以改成那样。
多次分组进行插入排序，使得最后对整个列表排序时，列表已经是大致有序的，那么最后一次插入排序就会时间复杂度就趋向线性的。
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
}
}
}
多次分组进行插入排序，使得最后对整个列表排序时，列表已经是大致有序的，那么最后一次插入排序就会时间复杂度就趋向线性的。
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
多次分组进行插入排序，使得最后对整个列表排序时，列表已经是大致有序的，那么最后一次插入排序就会时间复杂度就趋向线性的。
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
多次分组进行插入排序，使得最后对整个列表排序时，列表已经是大致有序的，那么最后一次插入排序就会时间复杂度就趋向线性的。
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 的直接插入排序，数列已经是相对有序了，所以时间复杂度会稍好一点。
感觉这个分组排序的想法和快速排序好像呀？
九九归一。
这代码是不是有点问题 ? 希尔排序应该是像下面这样吧。因为例子中的序列比较长，所以用个少一点的序列来举例，方便一些。 比如，有这么一组序列：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)
}
}
