image frame

XiShng Blog

既往拼搏，守护一生所爱

堆排序

算法 / 排序算法

堆排序

堆分为最小堆和最大堆两种，我们这里只记录下最小堆：

最小堆排序，插入元素

最小堆排序，插入元素

堆排序示意图

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
package main

import "fmt"

func heapsort(nums []int) []int {
	lenght := len(nums)
	if lenght == 0 {
		return nil
	}
	for i := 0; i < lenght; i++ {
		// 第一下 使得第一个元素最小，接下来就从第二个来构造，使得下一个最小，
		miniHeap(nums[i:])
	}
	return nums
}

// 使得每次操作完毕 堆顶的元素就是最小的，由于堆的特性，我们只需要从倒数第二层开始就可以了
func miniHeap(nums []int) {
	length := len(nums)
	floor := length/2 - 1
	for i := floor; i >= 0; i-- {
		// 然后比较的每一个节点与其两个孩子节点的大小，使得爸爸永远是最小的
		// 有一种特殊情况，就是最后一个节点的孩子节点可能不存在，和可能只有一个，所以需要加上一个判断
		baba := i
		left := 2*i + 1
		right := 2*i + 2

		if right < length && nums[baba] > nums[right] {
			nums[baba], nums[right] = nums[right], nums[baba]
		}

		if left < length && nums[baba] > nums[left] {
			nums[baba], nums[left] = nums[left], nums[baba]
		}

		//if left < length && right < length && nums[left] > nums[right]{
		//	nums[left], nums[right] = nums[right], nums[left]
		//}
	}
}

func top10() {
	// 30 * 10 = 300
	bigData := []int{
		3, 231, 321, 1, 7, 3, 45, 6, 2, 23,
		1, 31, 23, 1, 312, 67, 45, 3, 43, 435,
		32, 13, 56, 78, 500, 467, 321, 543, 23, 10,
		12, 12, 32, 321, 321, 43, 54, 65, 76, 45,
		67, 8, 45, 87, 32, 78, 4, 90, 45, 34,
		32, 13, 56, 78, 510, 467, 321, 543, 23, 11,
		12, 12, 32, 321, 301, 43, 55, 65, 76, 45,
		12, 12, 32, 321, 31, 43, 54, 65, 76, 45,
		12, 12, 32, 321, 321, 4, 54, 65, 76, 45,
		12, 12, 32, 321, 321, 43, 54, 65, 76, 45,
		12, 12, 32, 321, 321, 43, 4, 65, 76, 45,
		2, 12, 32, 321, 321, 43, 54, 65, 76, 45,
		12, 12, 32, 321, 321, 43, 54, 65, 76, 45,
		12, 12, 32, 321, 321, 43, 4, 65, 7, 45,
		12, 12, 32, 321, 321, 43, 5, 65, 6, 45,
		12, 12, 32, 321, 321, 43, 54, 65, 76, 45,
		12, 12, 32, 301, 321, 43, 4, 65, 76, 45,
		712, 32, 32, 321, 321, 43, 54, 65, 7, 45,
		612, 12, 32, 321, 321, 43, 54, 65, 76, 45,
		512, 12, 32, 401, 321, 43, 54, 65, 76, 45,
		212, 12, 32, 1, 321, 43, 54, 65, 76, 45,
		12, 12, 32, 321, 321, 43, 54, 65, 76, 45,
		12, 12, 32, 371, 321, 43, 54, 65, 76, 45,
		12, 12, 32, 321, 321, 453, 54, 65, 76, 45,
		12, 12, 32, 321, 321, 43, 554, 65, 76, 45,
		12, 172, 32, 301, 321, 43, 54, 65, 76, 45,
		12, 192, 32, 321, 321, 43, 564, 65, 76, 45,
		12, 142, 32, 321, 321, 43, 54, 65, 76, 45,
		12, 12, 32, 21, 321, 43, 54, 605, 76, 45,
		12, 122, 632, 321, 301, 43, 54, 65, 76, 495,
	}
	fmt.Println("the big data is ", bigData)
	startNums := bigData[:10]
	miniHeap(startNums)
	for _, data := range bigData[10:] {
		if data <= startNums[0] {
			continue
		} else {
			startNums[0] = data
			miniHeap(startNums)
		}
	}
	fmt.Println("top10 is ", heapsort(startNums))
}

from: golang:排序-堆排序-解决百万数据top100问题

插入排序算法

算法 / 排序算法

插入排序算法

算法思想：左端的数字已经完成排序。取出那些尚未操作的最左端的数字将这个数字与已经完成排序的数字进行比较如果左边的数字较大则交换两个数字的位置。重复此操作直到出现一个比当前较小的数字或者数字已经到达最左端。 如下图所示

时间复杂度：最坏情况下时间复杂度为O(n^2)。最好情况下为O(n)

插入排序示意图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package main

import "fmt"

func main() {
    numbers := []int{6, 2, 7, 3, 8, 5}
    InsertSort(numbers)

    fmt.Println(numbers)
}

func InsertSort(values []int) {
    length := len(values)
    if length <= 1 {
        return
    }

    for i := 1; i < length; i++ {
        tmp := values[i] // 从第二个数开始，从左向右依次取数
        key := i - 1     // 下标从0开始，依次从左向右

        // 每次取到的数都跟左侧的数做比较，如果左侧的数比取的数大，就将左侧的数右移一位，直至左侧没有数字比取的数大为止
        for key >= 0 && tmp < values[key] {
            values[key+1] = values[key]
            key--
            //fmt.Println(values)
        }

        // 将取到的数插入到不小于左侧数的位置
        if key+1 != i {
            values[key+1] = tmp
        }
        //fmt.Println(values)
    }
}

归并排序算法

算法 / 排序算法

归并排序算法

算法思想：

  • 第一步：将数字分成两半，重复此步骤直到每个数字成为一部分。
  • 第二步：合并数字，合并时按照数字的升序移动，使得合并后的数字在组内按升序排列。递归的重复组的合并操作，直到所有数字都在一个组中。

时间复杂度：O(nlogn)

归并排序示意图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
package main

import "fmt"

func main() {
	// 生成排序队列
	length := 20
	A := make([]int, length)
	j := length
	for i := 0; i < length; i++ {
		A[i] = j
		j--
	}
	// 打印输出前的队列
	fmt.Println("排序前", A)

	//进行排序
	MergeSort(A, 0, length-1)

	// 打进排序后的队列
	fmt.Println("排序后", A)
}

/*
MergeSort 归并排序
*/
func MergeSort(Arrary []int, left int, right int) {
	if left < right {
		median := 0
		if (right-median+1)%2 == 0 {
			median = (left + right - 1) / 2
		} else {
			median = (left + right) / 2
		}

		MergeSort(Arrary, left, median)
		MergeSort(Arrary, median+1, right)
		Merge(Arrary, left, median, right)
	}
}

/*
Merge 两列已排序的数组合并
*/
func Merge(Arrary []int, left int, median int, right int) {
	n1 := median - left + 1
	n2 := right - median

	L_Arr := make([]int, n1+1)
	R_Arr := make([]int, n2+1)

	for i := 0; i < n1; i++ {
		L_Arr[i] = Arrary[left+i]
	}
	L_Arr[n1] = 1000

	for i := 0; i < n2; i++ {
		R_Arr[i] = Arrary[median+1+i]
	}
	R_Arr[n2] = 1000
	leftNum := 0
	rightNum := 0
	for i := left; i < right+1; i++ {
		if L_Arr[leftNum] < R_Arr[rightNum] {
			Arrary[i] = L_Arr[leftNum]
			leftNum++
		} else {
			Arrary[i] = R_Arr[rightNum]
			rightNum++
		}
	}
}

请我喝杯咖啡吧~

支付宝
微信