通过leetcode学习常见排序算法及其Go实现
问题描述75. Sort Colors Here,we will use the integers 0,1,and 2 to represent the color red,white,and blue respectively. 冒泡排序算法描述1 遍历待排序序列 代码实现/** * 最差时间复杂度 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 初始时在序列中找到最小元素,放到序列的起始位置作为已排序序列 代码实现/** * 最差时间复杂度 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 从第一个元素开始,该元素可以认为已排好序 代码实现/** * 最差时间复杂度 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 } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |