0、排序算法说明0.1 排序的定义
对一序列对象根据某个关键字进行排序。
0.2 术语说明
- 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
- 不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
- 内排序：所有排序操作都在内存中完成；
- 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
- 时间复杂度： 一个算法执行所耗费的时间。
- 空间复杂度：运行完一个程序所需内存的大小。
0.3 算法总结
image.png
图片名词解释：
- n: 数据规模
- k: “桶”的个数
- In-place: 占用常数内存，不占用额外内存
- Out-place: 占用额外内存
package suanfa
import (
"fmt"
"testing"
)
func getMaxValue(arr []int) int {
if arr == nil {
return 0
}
max := 0
for _, val := range arr {
if val > max {
max = val
}
}
return max
}
//1、冒泡排序 - 依次比较相邻两元素，若前一元素大于后一元素则交换之，直至最后一个元素即为最大；
// 然后重新从首元素开始重复同样的操作，直至倒数第二个元素即为次大元素；依次类推。如同水中的气泡，依次将最大或最小元素气泡浮出水面。
//
//时间复杂度：O(N2) 稳定性：稳定
func bubbleSort(arr []int) {
if len(arr) <= 1 {
return
}
begin := 0
end := len(arr) - 1
isLoop := true
for i := end; true == isLoop && i > begin; i-- {
isLoop = false
for j := begin + 1; j < i; j++ {
if arr[j] < arr[j-1] {
arr[j], arr[j-1] = arr[j-1], arr[j]
isLoop = true
}
}
}
}
func TestBubble(t *testing.T) {
arr := []int{1, 41, 5, 63, 2, 3, 44, 7, 88}
bubbleSort(arr)
fmt.Println(arr)
}
//选择排序 - 首先初始化最小元素索引值为首元素，依次遍历待排序数列，若遇到小于该最小索引位置处的元素则刷新最小索引为该较小元素的位置，
// 直至遇到尾元素，结束一次遍历，并将最小索引处元素与首元素交换；然后，初始化最小索引值为第二个待排序数列元素位置，同样的操作，可得到数列第二个元素即为次小元素；以此类推。
//
//时间复杂度：O(N2) 稳定性：不稳定
func selectSort(arr []int) {
if len(arr) <= 1 {
return
}
begin := 0
end := len(arr) - 1
for i := begin; i < end; i++ {
minIndex := i
for j := i + 1; j < end; j++ {
if arr[j] < arr[minIndex] {
minIndex = j
}
}
if minIndex != i {
arr[i], arr[minIndex] = arr[minIndex], arr[i]
}
}
}
func TestSelect(t *testing.T) {
arr := []int{1, 41, 5, 63, 2, 3, 44, 7, 88}
selectSort(arr)
fmt.Println(arr)
}
//3、快速排序 - （类似于选择排序的定位思想）选一基准元素，依次将剩余元素中小于该基准元素的值放置其左侧，大于等于该基准元素的值放置其右侧；
// 然后，取基准元素的前半部分和后半部分分别进行同样的处理；以此类推，直至各子序列剩余一个元素时，即排序完成（类比二叉树的思想，from up to down）
//
//时间复杂度：O(NlogN) 稳定性：不稳定
func quickSort(arr []int) {
if len(arr) <= 1 {
return
}
mid, i := arr[0], 1
head, tail := 0, len(arr)-1
for head < tail {
fmt.Println(arr)
if arr[i] > mid {
arr[i], arr[tail] = arr[tail], arr[i]
tail--
} else {
arr[i], arr[head] = arr[head], arr[i]
head++
i++
}
}
arr[head] = mid
quickSort(arr[:head])
quickSort(arr[head+1:])
}
func TestQuick(t *testing.T) {
arr := []int{1, 41, 5, 63, 2, 3, 44, 7, 88}
quickSort(arr)
fmt.Println(arr)
}
//插入排序 - 数列前面部分看为有序，依次将后面的无序数列元素插入到前面的有序数列中，初始状态有序数列仅有一个元素，即首元素。
// 在将无序数列元素插入有序数列的过程中，采用了逆序遍历有序数列，相较于顺序遍历会稍显繁琐，但当数列本身已近排序状态效率会更高。
//
//时间复杂度：O(N2) 稳定性：稳定
func inserSort(arr []int) {
if len(arr) <= 1 {
return
}
j := 0
end := len(arr) - 1
for i := 1; i < end; i++ {
temp := arr[i]
for j = i; j > 0 && arr[j-1] > temp; j-- {
arr[j] = arr[j-1]
}
arr[j] = temp
}
}
func TestInsert(t *testing.T) {
arr := []int{1, 41, 5, 63, 2, 3, 44, 7, 88}
inserSort(arr)
fmt.Println(arr)
}
//希尔排序 - 插入排序的改进版。为了减少数据的移动次数，在初始序列较大时取较大的步长，通常取序列长度的一半，此时只有两个元素比较，交换一次；
// 之后步长依次减半直至步长为1，即为插入排序，由于此时序列已接近有序，故插入元素时数据移动的次数会相对较少，效率得到了提高。
//
//时间复杂度：通常认为是O(N3/2) ，未验证 稳定性：不稳定
func shellSort(arr []int) {
step := len(arr) / 2
temp := len(arr) / 2
for step > 0 {
for i := step; i < len(arr); i++ {
temp = arr[i]
preIndex := i - step
for preIndex >= 0 && arr[preIndex] > temp {
arr[preIndex+step] = arr[preIndex]
preIndex -= step
}
arr[preIndex+step] = temp
}
step /= 2
}
}
func TestShell(t *testing.T) {
arr := []int{1, 41, 5, 63, 2, 3, 44, 7, 88}
shellSort(arr)
fmt.Println(arr)
}
//6、桶排序 - 实现线性排序，但当元素间值得大小有较大差距时会带来内存空间的较大浪费。首先，找出待排序列中得最大元素max，申请内存大小为max + 1的桶（数组）并初始化为0；
// 然后，遍历排序数列，并依次将每个元素作为下标的桶元素值自增1；最后，遍历桶元素，并依次将值非0的元素下标值载入排序数列（桶元素>1表明有值大小相等的元素，此时依次将他们载入排序数列），遍历完成，排序数列便为有序数列。
//
//时间复杂度：O(x*N) 稳定性：稳定
func bucketSort(arr []int) {
max := getMaxValue(arr)
newArr := make([]int, max+1, max+1)
for _, value := range arr {
newArr[value] = newArr[value] + 1
}
for i, j := 0, 0; i <= max; i++ {
for newArr[i] > 0 {
arr[j] = i
j++
newArr[i] -= 1
}
}
}
func TestBucket(t *testing.T) {
arr := []int{1, 41, 5, 63, 2, 3, 44, 7, 88}
bucketSort(arr)
fmt.Println(arr)
}
//8、归并排序 - 采用了分治和递归的思想，递归&分治-排序整个数列如同排序两个有序数列，依次执行这个过程直至排序末端的两个元素，
// 再依次向上层输送排序好的两个子列进行排序直至整个数列有序（类比二叉树的思想，from down to up）。
//
//时间复杂度：O(NlogN) 稳定性：稳定
func mergeSort(arr []int) []int {
if len(arr) < 2 {
return arr
}
mid := len(arr) / 2
left := arr[:mid]
right := arr[mid:]
return merge(mergeSort(left), mergeSort(right))
}
func merge(left, right []int) []int {
result := make([]int, len(left)+len(right))
for index, i, j := 0, 0, 0; index < len(result); index++ {
if i >= len(left) {
result[index] = right[j]
j++
} else if j > len(right) {
result[index] = left[i]
i++
} else if left[i] > right[j] {
result[index] = right[j]
j++
} else {
result[index] = left[i]
i++
}
}
return result
}
func TestMerge(t *testing.T) {
arr := []int{1, 41, 5, 63, 2, 3, 44, 7, 88}
result := mergeSort(arr)
fmt.Println(result)
}
//9、堆排序 - 堆排序的思想借助于二叉堆中的最大堆得以实现。首先，将待排序数列抽象为二叉树，并构造出最大堆；
// 然后，依次将最大元素（即根节点元素）与待排序数列的最后一个元素交换（即二叉树最深层最右边的叶子结点元素）；
// 每次遍历，刷新最后一个元素的位置（自减1），直至其与首元素相交，即完成排序。
//
//时间复杂度：O(NlogN) 稳定性：不稳定
func downToMaXhEAP(arr []int, begin, end int) {
child := 0
parent := begin
child = parent*2 + 1
for child < end {
if (child < (end - 1)) && (arr[child] < arr[child+1]) {
child++
}
if arr[child] > arr[parent] {
arr[child], arr[parent] = arr[parent], arr[child]
} else {
break
}
parent = child
}
}
func buildMaxHeap(arr []int) {
end := len(arr) - 1
parent := end/2 - 1
for parent >= 0 {
downToMaXhEAP(arr, parent, end)
parent--
}
}
func heapSort(arr []int) {
buildMaxHeap(arr)
end := len(arr) - 1
for end > 1 {
end--
arr[0], arr[end] = arr[end], arr[0]
downToMaXhEAP(arr, 0, end)
}
}
func TestHeap(t *testing.T) {
arr := []int{1, 41, 5, 63, 2, 3, 44, 7, 88}
heapSort(arr)
fmt.Println(arr)
}
