排序算法分类实现

冒泡排序

  • 时间复杂度：O(n^2)
  • 空间复杂度：O(1)
  • 稳定性：稳定
  • 特点：简单易懂，但效率较低，适用于数据量较小的情况。

排序过程：

从第一个元素开始，依次比较相邻的两个元素，如果前一个元素大于后一个元素，则交换它们的位置，直到最后一个元素。重复以上步骤，直到所有元素都排序完成。

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] {temp := arr[j]arr[j] = arr[j+1]arr[j+1] = temp}}}
}

快速排序

  • 时间复杂度：O(nlogn)
  • 空间复杂度：O(logn)
  • 稳定性：不稳定
  • 特点：效率高，但需要额外的空间，适用于数据量较大的情况。

排序过程：

选择一个基准元素，将小于基准元素的放在左边，大于基准元素的放在右边，然后对左右两边的子序列进行递归排序。

func quickSort(arr []int, left int, right int) {if left < right {i, j, x := left, right, arr[left]for i < j {for i < j && arr[j] >= x {j--}if i < j {arr[i] = arr[j]i++}for i < j && arr[i] < x {i++}if i < j {arr[j] = arr[i]j--}}arr[i] = xquickSort(arr, left, i-1)quickSort(arr, i+1, right)}
}

插入排序

  • 时间复杂度：O(n^2)
  • 空间复杂度：O(1)
  • 稳定性：稳定
  • 特点：适用于数据量较小的情况，对于基本有序的数据效率较高。

排序过程：

从第二个元素开始，将该元素插入到已排序的序列中的正确位置，直到所有元素都排序完成。

func insertionSort(arr []int) {n := len(arr)for i := 1; i < n; i++ {key := arr[i]j := i - 1for j >= 0 && arr[j] > key {arr[j+1] = arr[j]j--}arr[j+1] = key}
}

选择排序

  • 时间复杂度：O(n^2)
  • 空间复杂度：O(1)
  • 稳定性：不稳定
  • 特点：简单易懂，但效率较低，适用于数据量较小的情况。

排序过程：

从第一个元素开始，依次选择最小的元素，放在已排序序列的末尾，直到所有元素都排序完成。

func selectionSort(arr []int) {n := len(arr)for i := 0; i < n-1; i++ {minIndex := ifor j := i + 1; j < n; j++ {if arr[j] < arr[minIndex] {minIndex = j}}temp := arr[i]arr[i] = arr[minIndex]arr[minIndex] = temp}
}

希尔排序

  • 时间复杂度：O(nlogn) ~ O(n^2)
  • 空间复杂度：O(1)
  • 稳定性：不稳定
  • 特点：是插入排序的改进版，适用于数据量较大的情况。

排序过程：

将待排序序列按照一定的间隔分成若干个子序列，对每个子序列进行插入排序，然后逐步缩小间隔，直到间隔为1，对整个序列进行插入排序。

func shellSort(arr []int) {n := len(arr)for gap := n / 2; gap > 0; gap /= 2 {for i := gap; i < n; i++ {j := itemp := arr[j]if arr[j] < arr[j-gap] {for j-gap >= 0 && temp < arr[j-gap] {arr[j] = arr[j-gap]j -= gap}arr[j] = temp}}}
}

归并排序

  • 时间复杂度：O(nlogn)
  • 空间复杂度：O(n)
  • 稳定性：稳定
  • 特点：效率高，但需要额外的空间，适用于数据量较大的情况。

排序过程：

将待排序序列分成两个子序列，对每个子序列进行递归排序，然后将两个有序子序列合并成一个有序序列。

func mergeSort(arr []int, left int, right int) {if left < right {mid := (left + right) / 2mergeSort(arr, left, mid)mergeSort(arr, mid+1, right)merge(arr, left, mid, right)}
}func merge(arr []int, left int, mid int, right int) {temp := make([]int, right-left+1)i, j, k := left, mid+1, 0for i <= mid && j <= right {if arr[i] <= arr[j] {temp[k] = arr[i]k++i++} else {temp[k] = arr[j]k++j++}}for i <= mid {temp[k] = arr[i]k++i++}for j <= right {temp[k] = arr[j]k++j++}for p := 0; p < len(temp); p++ {arr[left+p] = temp[p]}
}

堆排序

  • 时间复杂度：O(nlogn)
  • 空间复杂度：O(1)
  • 稳定性：不稳定
  • 特点：效率高，但需要额外的空间，适用于数据量较大的情况。

排序过程：

将待排序序列构建成一个大根堆，然后将堆顶元素与最后一个元素交换，再将前n-1个元素重新构建成一个大根堆，重复以上步骤，直到所有元素都排序完成。

func heapSort(arr []int) {n := len(arr)for i := n/2 - 1; i >= 0; i-- {adjustHeap(arr, i, n)}for i := n - 1; i > 0; i-- {temp := arr[0]arr[0] = arr[i]arr[i] = tempadjustHeap(arr, 0, i)}
}func adjustHeap(arr []int, i int, length int) {temp := arr[i]for k := i*2 + 1; k < length; k = k*2 + 1 {if k+1 < length && arr[k] < arr[k+1] {k++}if arr[k] > temp {arr[i] = arr[k]i = k} else {break}}arr[i] = temp
}

计数排序

  • 时间复杂度：O(n+k)
  • 空间复杂度：O(k)
  • 稳定性：稳定

排序过程：

统计待排序序列中每个元素出现的次数，然后根据元素出现的次数，将元素放入相应的位置，最终得到有序序列。

func countingSort(arr []int) {n := len(arr)if n <= 1 {return}max := arr[0]for i := 1; i < n; i++ {if arr[i] > max {max = arr[i]}}c := make([]int, max+1)for i := 0; i < n; i++ {c[arr[i]]++}for i := 1; i <= max; i++ {c[i] += c[i-1]}r := make([]int, n)for i := n - 1; i >= 0; i-- {index := c[arr[i]] - 1r[index] = arr[i]c[arr[i]]--}for i := 0; i < n; i++ {arr[i] = r[i]}
}
十类排序方法汇总调试 
package mainimport ("fmt"
)func main() {arr := []int{5, 2, 8, 4, 9, 1, 3, 7, 6, 10}fmt.Println("冒泡排序: ")fmt.Println(bubbleSort(arr))fmt.Println("快速排序: ")fmt.Println(quickSort(arr))fmt.Println("插入排序: ")fmt.Println(insertionSort(arr))fmt.Println("选择排序: ")fmt.Println(selectionSort(arr))fmt.Println("希尔排序: ")fmt.Println(shellSort(arr))fmt.Println("归并排序: ")fmt.Println(mergeSort(arr))fmt.Println("堆排序: ")fmt.Println(heapSort(arr))fmt.Println("计数排序: ")fmt.Println(countingSort(arr))fmt.Println("桶排序: ")fmt.Println(bucketSort(arr))fmt.Println("基数排序: ")fmt.Println(radixSort(arr))
}/*** 冒泡排序* @param arr 待排序数组* 时间复杂度：O(n^2)* 空间复杂度：O(1)* 算法优点：实现简单，空间复杂度低* 算法缺点：时间复杂度高，不适用于大规模数据排序*/
func bubbleSort(arr []int) []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]}}}return arr
}/*** 快速排序* @param arr 待排序数组* @param low 起始下标* @param high 结束下标* 时间复杂度：O(nlogn)* 空间复杂度：O(logn)* 算法优点：时间复杂度低，适用于大规模数据排序* 算法缺点：实现较为复杂，空间复杂度高*/
func quickSort(arr []int) []int {if len(arr) <= 1 {return arr}pivot := arr[0]var left, right []intfor i := 1; i < len(arr); i++ {if arr[i] < pivot {left = append(left, arr[i])} else {right = append(right, arr[i])}}left = quickSort(left)right = quickSort(right)return append(append(left, pivot), right...)
}/*** 插入排序* @param arr 待排序数组* 时间复杂度：O(n^2)* 空间复杂度：O(1)* 算法优点：实现简单，适用于小规模数据排序* 算法缺点：时间复杂度高，不适用于大规模数据排序*/
func insertionSort(arr []int) []int {n := len(arr)for i := 1; i < n; i++ {key := arr[i]j := i - 1for j >= 0 && arr[j] > key {arr[j+1] = arr[j]j = j - 1}arr[j+1] = key}return arr
}/*** 选择排序* @param arr 待排序数组* 时间复杂度：O(n^2)* 空间复杂度：O(1)* 算法优点：实现简单，空间复杂度低* 算法缺点：时间复杂度高，不适用于大规模数据排序*/
func selectionSort(arr []int) []int {n := len(arr)for i := 0; i < n-1; i++ {min_idx := ifor j := i + 1; j < n; j++ {if arr[j] < arr[min_idx] {min_idx = j}}arr[i], arr[min_idx] = arr[min_idx], arr[i]}return arr
}/*** 希尔排序* @param arr 待排序数组* 时间复杂度：O(nlogn)* 空间复杂度：O(1)* 算法优点：时间复杂度低，适用于中等规模数据排序* 算法缺点：实现较为复杂*/
func shellSort(arr []int) []int {n := len(arr)for gap := n / 2; gap > 0; gap /= 2 {for i := gap; i < n; i += 1 {temp := arr[i]j := ifor j >= gap && arr[j-gap] > temp {arr[j] = arr[j-gap]j -= gap}arr[j] = temp}}return arr
}/*** 归并排序* @param arr 待排序数组* @param l 左边界* @param r 右边界* 时间复杂度：O(nlogn)* 空间复杂度：O(n)* 算法优点：时间复杂度低，适用于大规模数据排序* 算法缺点：空间复杂度高*/
func mergeSort(arr []int) []int {if len(arr) <= 1 {return arr}mid := len(arr) / 2left := mergeSort(arr[:mid])right := mergeSort(arr[mid:])return merge(left, right)
}/*** 归并排序辅助函数* @param arr 待排序数组* @param l 左边界* @param mid 中间点* @param r 右边界*/
func merge(left, right []int) []int {var res []intfor len(left) > 0 && len(right) > 0 {if left[0] <= right[0] {res = append(res, left[0])left = left[1:]} else {res = append(res, right[0])right = right[1:]}}if len(left) > 0 {res = append(res, left...)}if len(right) > 0 {res = append(res, right...)}return res
}/*** 堆排序* @param arr 待排序数组* 时间复杂度：O(nlogn)* 空间复杂度：O(1)* 算法优点：时间复杂度低，适用于大规模数据排序* 算法缺点：实现较为复杂*/
func heapSort(arr []int) []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)}return arr
}/*** 堆排序辅助函数* @param arr 待排序数组* @param n 堆大小* @param i 根节点下标*/
func heapify(arr []int, n, i int) {largest := il := 2*i + 1r := 2*i + 2if l < n && arr[l] > arr[largest] {largest = l}if r < n && arr[r] > arr[largest] {largest = r}if largest != i {arr[i], arr[largest] = arr[largest], arr[i]heapify(arr, n, largest)}
}/*** 计数排序* @param arr 待排序数组* 时间复杂度：O(n+k)* 空间复杂度：O(k)* 算法优点：时间复杂度低，适用于数据范围较小的排序* 算法缺点：数据范围过大时，空间复杂度过高*/
func countingSort(arr []int) []int {max := arr[0]min := arr[0]for i := 1; i < len(arr); i++ {if arr[i] > max {max = arr[i]}if arr[i] < min {min = arr[i]}}count := make([]int, max-min+1)for i := 0; i < len(arr); i++ {count[arr[i]-min]++}index := 0for i := 0; i < len(count); i++ {for count[i] > 0 {arr[index] = i + minindex++count[i]--}}return arr
}/*** 桶排序* @param arr 待排序数组* 时间复杂度：O(n)* 空间复杂度：O(n)* 算法优点：时间复杂度低，适用于数据范围较小的排序* 算法缺点：数据范围过大时，空间复杂度过高*/
func bucketSort(arr []int) []int {max := arr[0]min := arr[0]for i := 1; i < len(arr); i++ {if arr[i] > max {max = arr[i]}if arr[i] < min {min = arr[i]}}bucketNum := (max - min) / len(arr) + 1bucketArr := make([][]int, bucketNum)for i := 0; i < bucketNum; i++ {bucketArr[i] = make([]int, 0)}for i := 0; i < len(arr); i++ {num := (arr[i] - min) / len(arr)bucketArr[num] = append(bucketArr[num], arr[i])}for i := 0; i < len(bucketArr); i++ {sort.Ints(bucketArr[i])}index := 0for _, v := range bucketArr {for _, vv := range v {arr[index] = vvindex++}}return arr
}/*** 基数排序* @param arr 待排序数组* 时间复杂度：O(nk)* 空间复杂度：O(n+k)* 算法优点：时间复杂度低，适用于数据范围较小的排序* 算法缺点：数据范围过大时，空间复杂度过高*/
func radixSort(arr []int) []int {max := arr[0]for i := 1; i < len(arr); i++ {if arr[i] > max {max = arr[i]}}for exp := 1; max/exp > 0; exp *= 10 {countingSort(arr, exp)}return arr
}/*** 基数排序辅助函数* @param arr 待排序数组* @param exp 指数*/
func countingSort(arr []int, exp int) {output := make([]int, len(arr))count := make([]int, 10)for i := 0; i < len(arr); i++ {count[(arr[i]/exp)%10]++}for i := 1; i < 10; i++ {count[i] += count[i-1]}for i := len(arr) - 1; i >= 0; i-- {output[count[(arr[i]/exp)%10]-1] = arr[i]count[(arr[i]/exp)%10]--}for i := 0; i < len(arr); i++ {arr[i] = output[i]}
}