通过leetcode学习常见排序算法及其Go实现

酒肉穿肠过 · · 496 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

问题描述

75. Sort Colors
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

冒泡排序

算法描述

1 遍历待排序序列
2 比较相邻两个数,不相等则交换位置把大数放在小数后面
3 重复以上步骤,直到待排序序列为空,或无交换发生,说明排序完成

代码实现

/**
 * 最差时间复杂度 O(n^2)
 * 最优时间复杂度 O(n)
 * 平均时间复杂度 O(n^2)
 * 所需辅助空间  O(1)
 * 稳定性 稳定
 **/
func sortColors(nums []int) {
    length := len(nums)
    if length <= 1 {
        return
    }
    swapFlag := false
    temp := 0
    for i := 0; i < length; i++ {
        swapFlag = false
        for j := 0; j < length-i-1; j++ {
            if nums[j] > nums[j+1] {
                temp = nums[j]
                nums[j] = nums[j+1]
                nums[j+1] = temp
                swapFlag = true
            }
        }
        if !swapFlag { // 说明已经排好序
            break
        }
    }
}

选择排序

算法描述

1 初始时在序列中找到最小元素,放到序列的起始位置作为已排序序列
2 再从剩余未排序元素中继续寻找最小元素,放到已排序序列的末尾
3 重复以上步骤,直到所有元素均排序完毕

代码实现

/**
 * 最差时间复杂度 O(n^2)
 * 最优时间复杂度 O(n^2)
 * 平均时间复杂度 O(n^2)
 * 所需辅助空间  O(1)
 * 稳定性 不稳定
 **/
func sortColors(nums []int)  {
    if len(nums) <= 0 {
        return
    }
    
    temp, index := 0, 0
    for i := 0; i < len(nums); i++ { // 已排序列
        index = i
        for j := i + 1; j < len(nums); j++ { // 未排序列
            if nums[j] < nums[index] {
                index = j
                temp = nums[i]
            }
        }
        if index != i {
            nums[i] = nums[index]
            nums[index] = temp
        }
    } 
}

插入排序

算法描述

1 从第一个元素开始,该元素可以认为已排好序
2 取出下一个元素,在已排序列中从后向前遍历
3 若已排序列大于新元素,将已排元素移到下一位置
4 重复步骤3,直到找到已排元素小于或者等于新元素的位置
5 将新元素插入到该位置后,重复步骤2~5

代码实现

/**
 * 最差时间复杂度 O(n^2)
 * 最优时间复杂度 O(n)
 * 平均时间复杂度 O(n^2)
 * 所需辅助空间  O(1)
 * 稳定性 稳定
 **/
func sortColors(nums []int)  {
    if len(nums) <= 0 {
        return
    }
    
    temp := 0
    for i := 1; i < len(nums); i++ {
        temp = nums[i]
        j := i - 1
        for ; j >= 0 && nums[j] > temp; {
            nums[j+1] = nums[j]
            j--
        }
        nums[j+1] = temp
    } 
}

有疑问加站长微信联系(非本文作者)

本文来自:Segmentfault

感谢作者:酒肉穿肠过

查看原文:通过leetcode学习常见排序算法及其Go实现

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

496 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传