GO语言实现 一 基本排序

微信扫一扫,分享到朋友圈

GO语言实现 一 基本排序

基本排序包括简单选择排序和插入排序,本文将就这两种排序进行 golang语言实现,并引出希尔排序

一.简单选择排序

简单排序将数组分为两个部分,从左到当前索引的前一个元素为已排序部分,从当前索引到数组的末尾为未排序部分

简单选择排序算法思路如下:

  1. 从未排序部分中选取最小的一个元素 A
  2. 将 A元素与当前索引所在元素交换
  3. 重复 1,2步骤直到未排序部分为空

golang代码如下:

func selection_sort(nums []node) []node {
for i := 0; i < len(nums)-1; i++ {
minIndex := i
for j := i + 1; j < len(nums); j++ {
if (nums[j] < nums[minIndex]) {
minIndex = j
}
}
temp := nums[minIndex]
nums[minIndex] = nums[i]
nums[i] = temp
}
return nums
}

平均情况下:

时间复杂度 O(n^2)

空间复杂度 O(1)

二.插入排序

插入排序维护一个已排序数组,每次从未排序数组中选取第一个元素,然后找到该元素应处的位置,进行插入即可

插入排序算法步骤如下:

  1. 从未排序数组中选取第一个元素
  2. 从排序数组末尾往前找到该元素的插入位置
  3. 在对应位置进行插入
func insert_sort(nums []int) []int {
for i := 0; i < len(nums); i++ {
for j := i; j > 0; j-- {
if nums[j] < nums[j-1] {
temp := nums[j-1]
nums[j-1] = nums[j]
nums[j] = temp
} else {
break
}
}
}
return nums
}

平均情况下:

时间复杂度 O(n^2)

空间复杂度 O(1)

三.shell 排序

我们知道插入排序主要耗时用在数组元素的比较上,接下来,我们介绍一种分组插入排序,又称shell排序

shell排序将数组按照 h间隔分成交错的子数组,子数组内部使用插入排序进行排序。我们先选择大一点的 h间隔进行排序,然后逐渐缩小 h,直到 h=1进行最后一次排序

关于 h的选取非常重要,合适的 h会很好的降低的时间复杂度,比较常见的 h选取如下:

  1. 2的幂:         1,2,4,8,16,32,…
  2. 2的幂-1:      1,3,7,15,31,63,…
  3. 3x+1:           1,4,13,40,121,364,…
  4. Sedgewick:  1,5,19,41,109,209,505,929,2161,3905,…

关于第四种 Sedgewick是一种实际使用中非常优质的 h间隔

Sedgewick的生成方法是两个多项式 (9 ⨉ 4i) – (9 ⨉ 2i) + 1和 4i – (3 ⨉ 2i) + 1 交叉序列

我们在这里选择 3x+1的序列

func shell_sort(nums []int) []int {
N := len(nums)
h := 1
for h < N/3 {
h = 3*h + 1
}
for h >= 1 {
for i := h; i < N; i++ {
for j := i; j >= h && nums[j] < nums[j-h]; j -= h {
temp := nums[j]
nums[j] = nums[j-h]
nums[j-h] = temp
}
}
h /= 3
}
return nums
}

对比插入排序,如果选择合适的 h间隔,shell排序的时间复杂度会降至 O(nlogn)

四.shuffling

接下来,我们介绍一种线性时间内的随机洗牌算法,该洗牌算法又叫做 Knuth shuffle

该洗牌算法从后往前洗牌,算法大致逻辑如下:

算法从后往前洗牌,对于其中的每一张牌,从该牌前面的牌中随机选择一张牌与此牌交换,当前位置的牌就已经洗牌完毕。

算法实现如下:

func knuth_shuffle(nums []int) []int {
Len := len(nums)
for i := Len - 1; i >= 0; i-- {
rand.Seed(time.Now().UnixNano())
index := rand.Intn(i + 1)
temp := nums[i]
nums[i] = nums[index]
nums[index] = temp
}
return nums
}

有疑问加站长微信联系

微信扫一扫,分享到朋友圈

GO语言实现 一 基本排序

InnoDB线程并发检查机制

上一篇

手撸Mysql原生语句--多表

下一篇

你也可能喜欢

GO语言实现 一 基本排序

长按储存图像,分享给朋友