八大排序
须知
- 以对
arr = [2, 5, 3, 6, 1, 8, 9, 0]进行升序排序为例，阐述排序算法的思想。 - 稳定排序。排序前后，数组中相同元素的相对位置不变。是否稳定，关键看是否发生了跨元素交换（即非相邻元素发生了交换）。
比较排序
通过决策树可以证明，所有基于比较的算法的时间复杂度的下界是
。
冒泡排序
算法思想：从左到右，两两比较，较大者往后放，一轮下来，最大的数已经放到了数组末尾，对于前面剩下的元素重复上述操作。
for i := 0; i < len(arr)-1; i++ {for j := 0; j < len(arr)-1-i; j++ {if arr[j] > arr[j+1] {arr[j], arr[j+1] = arr[j+1], arr[j]}}}
交换发生在相邻元素，因此是稳定排序。
时间复杂度为
，空间复杂度为
。
选择排序
算法思想：从左到右，两两比较，记录最小值的下标，将最小值放到数组开头，对于后面剩下的元素重复上述操作。
for i := 0; i < len(arr); i++ {
minLoc := i // 最小值的下标
for j := i; j < len(arr); j++ { // 通过比较无序序列中的每个元素，寻找最小值的下标
if arr[minLoc] > arr[j] {
minLoc = j
}
}
arr[i], arr[minLoc] = arr[minLoc], arr[i]
}
可能发生跨元素交换，因此是不稳定排序。
时间复杂度为，空间复杂度为。
插入排序
算法思想：维护一个有序序列，对于无序序列中的每一个元素，在有序序列中寻找它插入的位置。
for i := 0; i < len(arr); i++ { // 对于无序序列中的每一个元素
for j := i; j > 0; j-- { // 通过两两比较交换位置到达应该插入的位置
if arr[j-1] > arr[j] {
arr[j-1], arr[j] = arr[j], arr[j-1]
} else {
break
}
}
}
交换发生在相邻元素，因此是稳定排序。
时间复杂度为，空间复杂度为。
希尔排序
算法思想：按步长递减的方式采用插入排序。
for inc := len(arr) / 2; inc > 0; inc /= 2 { // 步长
for gap := 0; gap < inc; gap++ { // 分为 inc 组
// 每一组里使用插入排序
for i := gap; i < len(arr); i += inc {
for j := i; j > gap; j -= inc {
if arr[j-inc] > arr[j] {
arr[j-inc], arr[j] = arr[j], arr[j-inc]
} else {
break
}
}
}
}
}
可能发生跨元素交换，因此是不稳定排序。
时间复杂度为，空间复杂度为。
归并排序
算法思想：采用分治思想进行排序（采用递归实现）
- 划分子问题：把数组对半分。
- 解决子问题：一直划分，直到数组长度为 1，把它当作有序数组（递归出口）
- 合并子问题：把两个有序的数组合并成一个有序数组。
```go
/ MergeSort 归并排序
func MergeSort(arr []int) {
// 是否需要排序
if NeedSorted(arr) == false {
} temp := MergeSortHelp(arr) copy(arr, temp) }return
// MergeSortHelp 归并排序的辅助函数 func MergeSortHelp(arr []int) []int { // 递归出口 if len(arr) < 2 { return arr }
// 拆分子问题
mid := len(arr) / 2
left := make([]int, mid)
copy(left, arr)
right := make([]int, len(arr)-mid)
copy(right, arr[mid:])
// 合并子问题
return merge(MergeSortHelp(left), MergeSortHelp(right))
}
// merge 双指针法合并 func merge(left []int, right []int) []int { res := make([]int, len(left)+len(right)) i, j, k := 0, 0, 0 for i < len(left) && j < len(right) { if left[i] < right[j] { res[k] = left[i] k, i = k+1, i+1 } else { res[k] = right[j] k, j = k+1, j+1 } }
for i < len(left) {
res[k] = left[i]
k, i = k+1, i+1
}
for j < len(right) {
res[k] = right[j]
k, j = k+1, j+1
}
return res
}
交换发生在相邻元素，因此是稳定排序。<br />时间复杂度为，空间复杂度为。<br />递归式：<br />由主定理法解得：
<a name="XcILt"></a>
### 快速排序
算法思想：采用分治思想进行排序（递归实现）：
1. 任选一个轴值 pivot。
1. 根据 pivot 把数组分成小于 pivot 和大于 pivot 的两部分。
1. 对上述两部分继续采用相同的分治方法，直至部分的长度为 1 则认为有序（递归出口）。
```go
// QuickSort 快速排序
func QuickSort(arr []int) {
if NeedSorted(arr) == false {
return
}
quickSortHelp(arr, 0, len(arr)-1)
}
// quickSortHelp 快排辅助函数
func quickSortHelp(arr []int, left int, right int) {
if left < right {
base := partition(arr, left, right)
quickSortHelp(arr, left, base-1)
quickSortHelp(arr, base+1, right)
}
}
// 根据轴值划分两部分
func partition(arr []int, left int, right int) int {
pivot := arr[left]
for left < right {
for left < right && arr[right] >= pivot {
right--
}
arr[left] = arr[right]
for left < right && arr[left] <= pivot {
left++
}
arr[right] = arr[left]
}
arr[left] = pivot
return left
}
可能发生跨元素交换，因此是不稳定排序。
时间复杂度为，空间复杂度为。
递归式：
由主定理法解得：
堆排序
算法思想：依次删除最大堆的堆顶元素，可以得到一个升序序列。
因此问题转化为如何把一个数组转化为最大堆，以及删除堆顶元素后，维持最大堆的性质。
// HeapSort 堆排序
func HeapSort(arr []int) {
if NeedSorted(arr) == false {
return
}
size := len(arr)
for i := size - 1; i >= 0; i-- {
arr[0], arr[i] = arr[i], arr[0]
size--
heapify(arr, 0, size)
}
}
// 构建最大堆
func buildMaxHeap(arr []int, size int) {
// 只有非叶子节点才需要采取下拉操作
for i := int(size / 2); i >= 0; i-- {
heapify(arr, i, size)
}
}
// 下来操作，维护最大堆的性质
func heapify(arr []int, i int, size int) {
left := 2*i + 1 // 左子节点
right := 2*i + 2 // 右子节点
largest := i // 最大值节点
if left < size && arr[left] > arr[largest] {
largest = left
}
if right < size && arr[right] > arr[largest] {
largest = right
}
// 最大值不是根节点
if largest != i {
arr[i], arr[largest] = arr[largest], arr[i] // 发生交换
heapify(arr, largest, size) //由于发生交换可能让原本是最大堆的子树不再是最大堆，递归调整
}
}
非比较排序
若有收获，就点个赞吧
0 人点赞
