十大常见的排序算法（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 为基数。