常见排序算法原理——Go语言实现

冒泡排序——Bubble Sort

算法原理

它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。

算法描述

  1. 比较相邻的元素。如果第一个比第二个大,就交换它们两个;
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
  3. 针对所有的元素重复以上的步骤,除了最后一个;
  4. 重复步骤1~3,直到排序完成。
package main

import "fmt"

func main() {
    arr := []int{1, 3, 45, 32, 74, 33, 22, 8, 23, 75, 44, 26, 9}
    result := bubbleSort(arr)
    fmt.Println(result)
}

func bubbleSort(arr []int) []int {
    for i := 0; i < len(arr)-1; i++ {
        for j := 0; j < len(arr)-1-i; j++ {
            //相邻元素两两对比
            if arr[j] > arr[j+1] {
                // 元素交换
                temp := arr[j+1]
                arr[j+1] = arr[j]
                arr[j] = temp
            }
        }
    }
    return arr
}

选择排序——Selection Sort

算法原理

首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

算法描述

  1. 初始状态:无序区为R[1..n],有序区为空;
  2. 第i趟排序(i=1,2,3…n-1)开始时,当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中-选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区;
  3. n-1趟结束,数组有序化了
package main

import "fmt"

func main() {
    arr := []int{1, 3, 45, 32, 74, 33, 22, 8, 23, 75, 44, 26, 9}
    result := selectionSort(arr)
    fmt.Println(result)
}

func selectionSort(arr []int) []int {
    var minIndex, temp int
    for i := 0; i < len(arr)-1; i++ {
        minIndex = i
        for j := i + 1; j < len(arr); j++ {
            // 寻找最小的数,将最小数的索引保存
            if arr[j] < arr[minIndex] {
                minIndex = j
            }
        }
        //将最小数放到当前的遍历位置
        temp = arr[i]
        arr[i] = arr[minIndex]
        arr[minIndex] = temp
    }
    return arr
}

插入排序——Insertion Sort

算法原理

通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

算法描述

  1. 从第一个元素开始,该元素可以认为已经被排序;
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描;
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置;
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
  5. 将新元素插入到该位置后;
  6. 重复步骤2~5。
package main

import "fmt"

func main() {
    arr := []int{3, 1, 45, 32, 74, 33, 22, 8, 23, 75, 44, 26, 9}
    result := insertionSort(arr)
    fmt.Println(result)
}

func insertionSort(arr []int) []int {
    for i := 1; i < len(arr); i++ {
        current := arr[i]
        index := i
        //从前一位开始遍历
        for j := i - 1; j >= 0; j-- {
            //如果前一位的数值比当前的小,则将前一位的数赋值到当前位
            if arr[j] > current {
                //将前一位的数赋值到当前位
                arr[j+1] = arr[j]
                //将前一位的索引设置为当前数值应该存在的位置
                index = j
            } else {
                break
            }
        }
        arr[index] = current
    }
    return arr
}

快速排序——quick Sort

算法原理

通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

算法描述

  1. 从数列中挑出第一个元素,称为中位数;
  2. 重新排序数列,所有元素比基准值小的摆放在基准前面,称为左区间。所有元素比基准值大的摆在基准的后面,称为右区间(相同的数可以到任一边);
  3. 对左区间进行快速排序
  4. 对右区间进行快速排序
  5. 重新合并左区间、中位数、右区间
package main

import "fmt"

func main() {
    arr := []int{3, 1, 45, 32, 74, 33, 22, 8, 23, 75, 44, 26, 9}
    result := quickSort(arr)
    fmt.Println(result)
}

func quickSort(arr []int) []int {
    length := len(arr)
    if length <= 1 {
        return arr
    }
    //设定基数
    middle := arr[0]
    left := []int{}
    right := []int{}
    //划分区间,左边都比中位数小,右边都比中位数大
    for i := 1; i < length; i++ {
        if middle < arr[i] {
            right = append(right, arr[i])
        } else {
            left = append(left, arr[i])
        }
    }
    //左边区间递归进行快速排序
    left = quickSort(left)
    //右边区间递归进行快速排序
    right = quickSort(right)
    result := append(append(left, middle), right...)
    return result
}

归并排序——Merge Sort

算法原理

将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。

算法描述

  1. 把长度为n的输入序列分成两个长度为n/2的子序列;
  2. 对这两个子序列分别采用归并排序;
  3. 将两个排序好的子序列合并成一个最终的排序序列。
package main

import "fmt"

func main() {
    arr := []int{3, 1, 45, 32, 74, 33, 22, 8, 23, 75, 44, 26, 9}
    result := mergeSort(arr)
    fmt.Println(result)
}

func mergeSort(arr []int) []int {
    if len(arr) < 2 {
        return arr
    }
    i := len(arr) / 2
    left := mergeSort(arr[0:i])
    right := mergeSort(arr[i:])
    result := merge(left, right)
    return result
}

func merge(left, right []int) []int {
    result := make([]int, 0)
    m, n := 0, 0 // left和right的index位置
    l, r := len(left), len(right)
    for m < l && n < r {
        if left[m] > right[n] {
            result = append(result, right[n])
            n++
            continue
        }
        result = append(result, left[m])
        m++
    }
    result = append(result, right[n:]...)
    result = append(result, left[m:]...)
    return result
}

计数排序——Counting Sort

算法原理

计数排序不是基于比较的排序算法,其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。

算法描述

  1. 找出待排序的数组中最大和最小的元素;
  2. 统计数组中每个值为i的元素出现的次数,存入数组C的第i项;
  3. 对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加);
  4. 反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1。
package main

import "fmt"

func main() {
    arr := []int{3, 1, 45, 32, 74, 33, 22, 8, 23, 75, 44, 26, 9}
    result := countingSort(arr)
    fmt.Println(result)
}

func countingSort(arr []int) []int {
    maxValue := arr[0]
    //找到最大值
    for _, val := range arr {
        if val > maxValue {
            maxValue = val
        }
    }
    //初始化计数桶
    bucketLen := maxValue + 1
    bucket := make([]int, bucketLen)
    //入桶
    for _, val := range arr {
        bucket[val] += 1
    }
    //获取排序结果
    sortedIndex := 0
    for j := 0; j < bucketLen; j++ {
        for bucket[j] > 0 {
            arr[sortedIndex] = j
            sortedIndex += 1
            bucket[j] -= 1
        }
    }
    return arr
}

算法复杂度

排序算法 时间复杂度(平均) 时间复杂度(最坏) 时间复杂度(最好) 空间复杂度 稳定性
冒泡排序 O(n2) O(n2) O(n) O(1) 不稳定
选择排序 O(n2) O(n2) O(n2) O(1) 不稳定
插入排序 O(n2) O(n2) O(n) O(1) 稳定
快速排序 O(nlog2n) O(n2) O(nlog2n) O(nlog2n) 不稳定
归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n) 稳定
计数排序 O(n+k) O(n+k) O(n+k) O(n+k) 稳定

参考资料

分类

开发
    --go (9)
    --java (5)
    --php (11)
    --mysql (9)
    --javascript (3)
    --html (1)
    --算法 (6)
架构
    --理论 (9)
    --网络 (3)
    --服务器 (2)
    --消息队列 (3)
    --容器 (5)
    --监控 (1)
    --搜索引擎 (3)
    --大数据 (0)
    --测试 (1)
系统
    --linux (10)
    --mac (2)
    --windows (1)
足球
    --世界杯 (60)
    --欧洲杯 (28)
    --文迷 (3)
大学时光
    --校园生活 (96)
    --假期生活 (17)
    --广院杯那些事 (14)
    --北京奥运 (6)
    --胡思乱写 (17)


最近发布

零拷贝技术介绍

服务网格技术简介

C语言标准和标准库简介

Kubernetes简介及环境搭建

Go语言开发的顶级项目


归档

2006 (109)
2007 (40)
2008 (47)
2009 (10)
2010 (6)
2012 (10)
2013 (14)
2014 (27)
2015 (15)
2016 (6)
2017 (8)
2018 (11)
2019 (17)
2020 (5)