排序算法分类


排序算法建议结合动画学习，手机有相应的动画学习APP

  • 算法动画图解
  • 数据结构与算法教程

    冒泡排序

    Bubble Sort 是一种简单排序算法。它重复的走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行到到没有再需要交换的。

冒泡排序算法的运作如下：

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

冒泡排序算法实现
package main
import (
“fmt”
)
// 冒泡排序
type bubbleSort struct {
numList []int
}
func (b bubbleSort) sort() {
n := len(b.numList)
count1 := 0
count2 := 0
isChange := true
for i := 0; i < n-1; i++ { // 控制内层检查次数，最大长度-1次
count1++
isChange = false
for j := 0; j if b.numList[j] > b.numList[j+1]{
count2++
b.swap(j, j+1)
isChange = true
}
}
if !isChange { // 优化，最优时，如果没有交换，跳出循环
break
}
}
fmt.Printf(“共检查%d次, 交换%d次.\n”, count1, count2)
}
func (b bubbleSort) swap(i, j int) {
b.numList[i], b.numList[j] = b.numList[j], b.numList[i]
}

选择排序

选择排序改进了冒泡排序，每次遍历列表只做一次交换。为了做到这一点，一个选择排序在遍历时查找max值，并在完成遍历后，将max放到正确的位置。
与冒泡一样，第一次遍历后，max在正确的位置，第二次后，next max 就位。遍历 n-1 次排序 n个项，因为最终项必须在第（n-1）次遍历之后。

思路：

  • 首先，找到数组中最小的元素，
  • 其次，将它和数组的第一个元素交换位置
  • 再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。
  • 如此往复，直到将整个数组排序。

这种方法叫选择排序，因为它在不断地选择剩余元素之中的最小值
算法实现
选择排序算法实现
package main
import (
“math/rand”
. “fmt”
)
// 选择排序
type selection struct {
numList []int
}
func (s selection) sort() {
length := len(s.numList)
for i:=0; i min := i
for j := i+1; j if s.numList[j] < s.numList[min] {
min = j
}
}
// swap
if min != 1 {
s.swap(i, min)
}

}
}
func (s selection) swap (i int, j int) {
s.numList[j], s.numList[i] = s.numList[i], s.numList[j]
}
func main() {
s := selection{}
for i:=0; i<10; i++ {
s.numList = append(s.numList, rand.Intn(30))
}
Printf(“排序前 %+v\n”, s)
s.sort()
Printf(“排序后 %+v\n”, s)
}
/ output
C:\Users\lite\go\src\go42\05_scope>go run scope.go
{numList:[11 27 17 29 1 18 25 20 16 0]}
{numList:[0 1 11 16 17 18 20 25 27 29]}
/
算法题1：无序数组查找第Top k元素。手写代码实现
算法题2：并查集。手写代码实现
算法题3：链表反转。手写代码实现
算法题4：枚举给定数组中的所有非递减子序列。敲代码运行
算法题5：枚举给定数组的全排列。敲代码运行
算法题6:图的邻接矩阵和邻接表的表示，邻接表的数据结构。敲代码不运行
算法题7：给定二叉树，假设相连接的两结点间距离为1，求所有结点中距离其他所有结点距离和最小的结点。敲代码运行