冒泡排序

注：本文已发布超过一年，请注意您所使用工具的相关版本是否适用

冒泡排序

定义

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

步骤：

  1. 比较相邻的元素（从后往前）。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
    (如果这一步没有出现任何一次交换，那么说明所有的元素已经有序，不需要再进行下面的步骤了)
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

程序示例（go）

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
func SortInt(a []int) ([]int, int) {
	//交换次数，计数
	n := 0

	aLen := len(a)

	for i := aLen - 1; i >= 0; i-- {
		//标记，如果flag一次冒泡之后没有改变，那么证明排序已完成，不需要再次排序，直接退出
		flag := 0

		//一次冒泡
		for j := 0; j < i; j++ {
			if a[j] > a[j+1] {
				//交换两个变量的值，无需引入临时变量
				a[j], a[j+1] = a[j+1], a[j]

				n++

				//有交换，flag=1
				flag = 1
			}
		}

		//判断一次冒泡，是否存在交换
		if flag == 0 {
			break
		}

	}

	return a, n
}

关注我获取更新

wechat
知乎
github

猜你喜欢

Go数据结构与算法 二、排序算法
Go 排序

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处，禁止全文转载