共计 5013 个字符，预计需要花费 13 分钟才能阅读完成。
十大常见的排序算法（go 语言实现）
冒泡排序（Bubble Sort）
抉择排序（Selection Sort）
插入排序（Insertion Sort）
希尔排序（Shell Sort）
归并排序（Merge Sort）
疾速排序（Quick Sort）
堆排序（Heap Sort）
计数排序（Counting Sort）
桶排序（Bucket Sort）
基数排序（Radix Sort）
go 语言实现
package main
import "fmt"
// 冒泡排序
func BubbleSort(arr []int) {n := len(arr)
for i := 0; i < n-1; i++ {
for j := 0; j < n-i-1; j++ {if arr[j] > arr[j+1] {arr[j], arr[j+1] = arr[j+1], arr[j]
}
}
}
}
// 抉择排序
func SelectionSort(arr []int) {n := len(arr)
for i := 0; i < n-1; i++ {
minIndex := i
for j := i + 1; j < n; j++ {if arr[j] < arr[minIndex] {minIndex = j}
}
arr[i], arr[minIndex] = arr[minIndex], arr[i]
}
}
// 插入排序
func InsertionSort(arr []int) {n := len(arr)
for i := 1; i < n; i++ {key := arr[i]
j := i - 1
for j >= 0 && arr[j] > key {arr[j+1] = arr[j]
j--
}
arr[j+1] = key
}
}
// 希尔排序
func ShellSort(arr []int) {n := len(arr)
gap := n / 2
for gap > 0 {
for i := gap; i < n; i++ {
j := i
for j-gap >= 0 && arr[j-gap] > arr[j] {arr[j-gap], arr[j] = arr[j], arr[j-gap]
j -= gap
}
}
gap /= 2
}
}
// 归并排序
func MergeSort(arr []int) []int {if len(arr) <= 1 {return arr}
mid := len(arr) / 2
left := MergeSort(arr[:mid])
right := MergeSort(arr[mid:])
return merge(left, right)
}
func merge(left, right []int) []int {result := make([]int, 0)
i, j := 0, 0
for i < len(left) && j < len(right) {if left[i] < right[j] {result = append(result, left[i])
i++
} else {result = append(result, right[j])
j++
}
}
result = append(result, left[i:]...)
result = append(result, right[j:]...)
return result
}
// 疾速排序
func QuickSort(arr []int) {quickSort(arr, 0, len(arr)-1)
}
func quickSort(arr []int, left, right int) {
if left < right {pivot := partition(arr, left, right)
quickSort(arr, left, pivot-1)
quickSort(arr, pivot+1, right)
}
}
func partition(arr []int, left, right int) int {pivot := arr[right]
i := left - 1
for j := left; j < right; j++ {if arr[j] < pivot {
i++
arr[i], arr[j] = arr[j], arr[i]
}
}
arr[i+1], arr[right] = arr[right], arr[i+1]
return i + 1
}
// 堆排序
func HeapSort(arr []int) {n := len(arr)
for i := n/2 - 1; i >= 0; i-- {heapify(arr, n, i)
}
for i := n - 1; i >= 0; i-- {arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
}
}
func heapify(arr []int, n, i int) {
largest := i
left := 2*i + 1
right := 2*i + 2
if left < n && arr[left] > arr[largest] {largest = left}
if right < n && arr[right] > arr[largest] {largest = right}
if largest != i {arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
}
}
// 计数排序
func CountingSort(arr []int) {n := len(arr)
if n <= 1 {return}
maxVal := arr[0]
for i := 1; i < n; i++ {if arr[i] > maxVal {maxVal = arr[i]
}
}
count := make([]int, maxVal+1)
for i := 0; i < n; i++ {count[arr[i]]++
}
for i, j := 0, 0; i <= maxVal; i++ {for count[i] > 0 {arr[j] = i
j++
count[i]--
}
}
}
// 桶排序
func BucketSort(arr []int) {n := len(arr)
if n <= 1 {return}
maxVal := arr[0]
minVal := arr[0]
for i := 1; i < n; i++ {if arr[i] > maxVal {maxVal = arr[i]
}
if arr[i] < minVal {minVal = arr[i]
}
}
bucketSize := 10
bucketCount := (maxVal-minVal)/bucketSize + 1
buckets := make([][]int, bucketCount)
for i := 0; i < bucketCount; i++ {buckets[i] = make([]int, 0)
}
for i := 0; i < n; i++ {index := (arr[i] - minVal) / bucketSize
buckets[index] = append(buckets[index], arr[i])
}
k := 0
for i := 0; i < bucketCount; i++ {if len(buckets[i]) > 0 {InsertionSort(buckets[i])
copy(arr[k:], buckets[i])
k += len(buckets[i])
}
}
}
// 基数排序
func RadixSort(arr []int) {n := len(arr)
if n <= 1 {return}
maxVal := arr[0]
for i := 1; i < n; i++ {if arr[i] > maxVal {maxVal = arr[i]
}
}
exp := 1
for maxVal/exp > 0 {countingSortForRadix(arr, exp)
exp *= 10
}
}
func countingSortForRadix(arr []int, exp int) {n := len(arr)
count := make([]int, 10)
output := make([]int, n)
for i := 0; i < n; i++ {index := (arr[i] / exp) % 10
count[index]++
}
for i := 1; i < 10; i++ {count[i] += count[i-1]
}
for i := n - 1; i >= 0; i-- {index := (arr[i] / exp) % 10
output[count[index]-1] = arr[i]
count[index]--
}
for i := 0; i < n; i++ {arr[i] = output[i]
}
}
func main() {arr1 := []int{1, 3, 2, 5, 4, 7, 6, 9, 8}
arr2 := []int{1, 3, 2, 5, 4, 7, 6, 9, 8}
arr3 := []int{1, 3, 2, 5, 4, 7, 6, 9, 8}
arr4 := []int{1, 3, 2, 5, 4, 7, 6, 9, 8}
arr5 := []int{1, 3, 2, 5, 4, 7, 6, 9, 8}
arr6 := []int{1, 3, 2, 5, 4, 7, 6, 9, 8}
arr7 := []int{1, 3, 2, 5, 4, 7, 6, 9, 8}
arr8 := []int{1, 3, 2, 5, 4, 7, 6, 9, 8}
arr9 := []int{1, 3, 2, 5, 4, 7, 6, 9, 8}
arr10 := []int{1, 3, 2, 5, 4, 7, 6, 9, 8}
BubbleSort(arr1)
fmt.Printf("arr1: %v\n", arr1)
SelectionSort(arr2)
fmt.Printf("arr2: %v\n", arr2)
InsertionSort(arr3)
fmt.Printf("arr3: %v\n", arr3)
ShellSort(arr4)
fmt.Printf("arr4: %v\n", arr4)
arr5 = MergeSort(arr5)
fmt.Printf("arr5: %v\n", arr5)
QuickSort(arr6)
fmt.Printf("arr6: %v\n", arr6)
HeapSort(arr7)
fmt.Printf("arr7: %v\n", arr7)
CountingSort(arr8)
fmt.Printf("arr8: %v\n", arr8)
BucketSort(arr9)
fmt.Printf("arr9: %v\n", arr9)
RadixSort(arr10)
fmt.Printf("arr10: %v\n", arr10)
}
输入的后果：
$ go run main.go
arr1: [1 2 3 4 5 6 7 8 9]
arr2: [1 2 3 4 5 6 7 8 9]
arr3: [1 2 3 4 5 6 7 8 9]
arr4: [1 2 3 4 5 6 7 8 9]
arr5: [1 2 3 4 5 6 7 8 9]
arr6: [1 2 3 4 5 6 7 8 9]
arr7: [1 2 3 4 5 6 7 8 9]
arr8: [1 2 3 4 5 6 7 8 9]
arr9: [1 2 3 4 5 6 7 8 9]
arr10: [1 2 3 4 5 6 7 8 9]排序算法的原理、执行过程、复杂度和耗时的简要阐明
冒泡排序：
比拟相邻的元素，如果前一个比后一个大，则替换它们的地位。反复这个过程，直到整个序列有序。
工夫复杂度为 O(n^2)，空间复杂度为 O(1)。在最坏状况下，须要进行 n(n-1)/ 2 次比拟和替换操作。
抉择排序：
每次从未排序的序列中抉择最小的元素，将其放到已排序序列的开端。
工夫复杂度为 O(n^2)，空间复杂度为 O(1)。在最坏状况下，须要进行 n(n-1)/ 2 次比拟和 n - 1 次替换操作。
插入排序：
将一个元素插入到已排序序列的适合地位，使得插入后的序列依然有序。
工夫复杂度为 O(n^2)，空间复杂度为 O(1)。在最坏状况下，须要进行 n(n-1)/ 2 次比拟和 n(n-1)/ 2 次挪动操作。
希尔排序：
将序列分成若干个子序列，对每个子序列进行插入排序，而后逐渐放大子序列的长度，最终对整个序列进行插入排序。
工夫复杂度为 O(nlogn)~O(n^2)，空间复杂度为 O(1)。
归并排序：
将序列分成若干个子序列，对每个子序列进行排序，而后将排好序的子序列合并成一个有序序列。工夫复杂度为 O(nlogn)，空间复杂度为 O(n)。
疾速排序：
抉择一个基准元素，将序列分成两个子序列，小于基准元素的放在右边，大于基准元素的放在左边，而后递归地对左右子序列进行疾速排序。
工夫复杂度为 O(nlogn)，空间复杂度为 O(logn)~O(n)。
堆排序：
将序列构建成一个堆，而后顺次取出堆顶元素，将其放到已排序序列的开端。
工夫复杂度为 O(nlogn)，空间复杂度为 O(1)。
计数排序：
统计序列中每个元素呈现的次数，而后依据元素呈现的次数将序列重构。
工夫复杂度为 O(n+k)，空间复杂度为 O(k)，其中 k 为序列中元素的取值范畴。
桶排序：
将序列分成若干个桶，对每个桶进行排序，而后将所有桶中的元素依照程序顺次放到一起。
工夫复杂度为 O(n)，空间复杂度为 O(n)。
基数排序：
将序列依照位数进行排序，从低位到高位顺次进行排序。
工夫复杂度为 O(d(n+r))，空间复杂度为 O(n+r)，其中 d 为最大数的位数，r 为基数。