Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
197 lines (148 sloc) 5.38 KB

+++ title = "简单排序算法" author = "BroQiang" github_url = "https://broqiang.com" head_img = "" created_at = 2019-06-25T09:47:58 updated_at = 2019-06-25T09:47:58 description = "" tags = ["go", "算法"] +++

这里记录了几种常用、基础的排序算法, 包括: 冒泡排序、插入排序、选择排序

冒泡排序

冒泡排序 算法的原理:

  • 比较相邻的元素。如果第一个比第二个大,就交换他们两个。

  • 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。

  • 针对所有的元素重复以上的步骤,除了最后一个。

  • 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

时间复杂度: O(n^2) 、空间复杂度 O(1) 。

冒泡排序是稳定排序算法(不会改变元素的相对位置)。

示例代码 1:

func bubbleSort(s []int) {
    n := len(s)

    if n < 2 {
        return
    }

    for i := 0; i < n; i++ {
        for j := 1; j < n; j++ {
            if s[j-1] > s[j] {
                s[j-1], s[j] = s[j], s[j-1]
            }
        }
    }
}

示例代码 2:

和上面的基本相同, 不过上面的代码稍微有点傻, 无论数据是否已经有序, 它都会将所有元素遍历 n * n 遍, 下面的方法加了一个 flag, 当它知道数据已经是有序的了, 就不会再遍历,将退出循环。 假设传入的数据是一个已经排序好的数据, 那它就只会遍历一遍数据, 复杂度就会降低到 O(n) 。

func bubbleSort(s []int) {
    n := len(s)

    if n < 2 {
        return
    }

    for i := 0; i < n; i++ {
        flag := true // 每次外层循环开始时, 我们都假装数据是已经有序
        for j := 1; j < n; j++ {
            if s[j-1] > s[j] {
                s[j-1], s[j] = s[j], s[j-1]
                // 如果移动过元素, 就证明数据还不是有序的, 标记
                flag = false
            }
        }
        // 内存循环结束时判断下,是否移动过数据, 如果一次没移动过, 就结束整个循环
        if flag {
            break
        }
    }
}

插入排序

插入排序 算法原理:

  • 从第一个元素开始,该元素可以认为已经被排序

  • 取出下一个元素,在已经排序的元素序列中从后向前扫描

  • 如果该元素(已排序)大于新元素,将该元素移到下一位置

  • 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置

  • 将新元素插入到该位置后

  • 重复步骤2~5

插入排序是稳定排序算法。

示例代码:

插入排序也是很简单的, 比冒泡稍微难理解一点, 已经在代码中添加了注释

// 这里的排序结果是从小到大排序
func insertionSort(s []int) {
    n := len(s)

    if n <= 1 {
        return
    }

    // 从第一个元素开始拿出, 假设第一个元素就是有序的了
    // 以后 i 前面的都是有序的
    for i := 1; i < n; i++ {
        // 拿出第 i 个元素, 记录到临时变量, 否则移动后就找不到了
        temp := s[i]

        // 拿 temp 和 i 前面的已经有序的元素进行比较
        j := i
        for ; j > 0 && temp < s[j-1]; j-- {
            // 如果 temp 比它前面的元素小, 它前面的元素就要向右移动一位
            // 最终留出需要插入的位置
            s[j] = s[j-1]
        }

        // 已经腾出位置了, 可以将元素插入(因为上个循环退出的时候还是执行一次 -- 操作)
        s[j] = temp
    }
}

选择排序

选择排序 原理:

  • 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置

  • 再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。

  • 以此类推,直到所有元素均排序完毕。

选择排序不是稳定排序算法(因为交换位置的时候会改变元素的相对位置)

示例代码 1:

func slelectionSort(s []int) {
    n := len(s)
    if n < 2 {
        return
    }

    // 遍历所有元素
    for i := 0; i < n-1; i++ {
        // 用后面所有位置和 第 i 个元素进行比较, 如果比 i 小, 进行交换
        // 第 1 次 s[0] 和后面比较, 交换完成后 s[0], 就是最小的了, 索引+1
        // 第 2 次 s[1] 和后面比较 ……
        // 直到最后一个结束
        for j := i + 1; j < n; j++ {
            if s[j] < s[i] {
                s[j], s[i] = s[i], s[j]
            }
        }
    }
}

示例代码 2:

和示例 1 基本相同, 不过在比较的时候只记录最小值的下标, 这样可以减少交换元素的次数

func slelectionSort(s []int) {
    n := len(s)
    if n < 2 {
        return
    }

    // 遍历所有元素
    for i := 0; i < n-1; i++ {
        // 记录一个最小值的坐标, 第一次是 0, 第二次是 1 ……
        min := i

        for j := i + 1; j < n; j++ {
            if s[j] < s[min] {
                min = j
            }
        }
        // 全部遍历完再进行数据的替换
        s[i], s[min] = s[min], s[i]
    }
}
You can’t perform that action at this time.