经典内部排序算法 | Go实现
内部排序的所有排序操作都在内存中完成,不需要额外的磁盘或其他存储设备的辅助。这适用于数据量小到足以完全加载到内存中的情况。常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序等。外部排序通常涉及到数据的分区处理,部分数据被暂时存储在外部磁盘等存储设备上。常见的外部排序算法有计数排序、基数排序、桶排序。
冒泡排序
描述:对于要排序的数组,从第一位开始从前往后比较相邻两个数字,若前者大,则交换两数字位置,然后比较位向右移动一位。记录前一轮交换的最终位置,该位置之后的元素为已排序状态,下一轮的交换只需执行到该处,每一轮的比较将使得当前未排序数字中的最大者被排序,未排序数字总数减 1。第 $arr.length - 1$ 轮结束后排序完成。
稳定性:稳定
优化:当某一轮比较均未发生交换,说明排序已完成,可设置一个布尔值记录一轮排序是否有发生交换,若无则提前退出循环结束程序。
时间复杂度分析:有序数组为O($n$),无序数组为O($n^2$)
空间复杂度:O(1)
代码:
func bubbleSort(arr []int) { n := len(arr) for i := 0; i < n-1; i++ { swapped := false for j := 0; j < n-i-1; j++ { if arr[j] > arr[j+1] { arr[j], arr[j+1] = arr[j+1], arr[j] swapped = true } } // 如果一轮遍历没有发生交换,说明数组已经有序,可以提前退出 if !swapped { break } } }
选择排序
描述:对于要排序的数组,设置一个 $minIdx$ 记录最小数字下标。先假设第 1 个数字最小,此时 minIdx = 0 ,将 $arr[minIdx]$ 与后续数字逐一比较,当遇到更小的数字时,使 $minIdx$ 等于该数字下标,第1轮比较将找出此时数组中最小的数字。找到后将 $minIdx$ 下标的数字与第 1 个数字交换,此时称一个数字已被排序。然后开始第2轮比较,令 minIdx = 1,重复上述过程。每一轮的比较将使得当前未排序数字中的最小者被排序,未排序数字总数减 1。第 $arr.length - 1$ 轮结束后排序完成。
稳定性:不稳定。存在跨越交换。找到本轮次最小值之后,将其与本轮起始数字交换,此时若中间有与起始元素同值的元素,将打破稳定性。例: 7 7 2 。第一轮交换第一个 7 和 2,则两个 7 位置关系改变。
时间复杂度分析:O($n^2$)(选择排序的交换次数是 $O(n)$,而冒泡排序的平均交换次数是O($n^2$))
空间复杂度:O(1)
代码:
//单元选择
func selectSort(nums []int){
minIndex := 0
for i := 0; i < len(nums) - 1; i++{
//查找最小值
for j := i+1; j < len(nums); j++{
if nums[minIndex] > nums[j]{
minIndex = j
}
}
//更新最小值
if nums[i] != nums[minIndex]{
nums[i], nums[minIndex] = nums[minIndex], nums[i]
}
minIndex = i + 1
}
}
//双元选择 在遍历寻找最小值下标时,可以同时寻找最大值下标
func biSelectSort(nums []int) {
minIndex := 0
for i := 0; i < len(nums)- i- 1; i++ {
maxIndex := len(nums) - i - 1
if nums[maxIndex] < nums[minIndex] {
nums[minIndex], nums[maxIndex] = nums[maxIndex], nums[minIndex]
}
//查找最大值,最小值
for j := i + 1; j < len(nums)-i-1; j++ {
if nums[minIndex] > nums[j] {
minIndex = j
}
if nums[maxIndex] < nums[j] {
maxIndex = j
}
}
//更新最大值,最小值
if nums[i] != nums[minIndex] {
nums[i], nums[minIndex] = nums[minIndex], nums[i]
}
if nums[maxIndex] != nums[len(nums)-i-1] {
nums[maxIndex], nums[len(nums)-i-1] = nums[len(nums)-i-1], nums[maxIndex]
}
minIndex = i + 1
}
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0许可协议,转载请注明出处
本文链接:https://blog.redamancy.tech/technique/42