O(N^2)排序

冒泡排序

选择排序

插入排序

O(logN)排序

快速排序

  1. func quickSort(nums []int) {
  2.     lth := len(nums)
  3.     if lth < 2 {
  4.         return
  5.     }
  6.     pivotN := nums[0]
  7.     left, right := 0, lth-1
  8.     for left < right {
  9.         for left < right && pivotN  <= nums[right] {
  10.             right--
  11.         }
  12.         for left < right && nums[left] <= pivotN {
  13.             left++
  14.         }
  15.         nums[left], nums[right] = nums[right], nums[left]
  16.     }
  17.     nums[left] = pivotN
  18.     quickSort(nums[:left])
  19.     quickSort(nums[left+1:])
  20. }

归并排序

  1. func mergesort(s []int) []int {
  2.     if len(s) < 2 {
  3.         return s
  4.     }
  5.     mid := len(s) / 2
  6.     l := mergesort(s[:mid])
  7.     r := mergesort(s[mid:])
  8.     return merge(l, r)
  9. }
  11. func merge(l, r []int) []int {
  12.     var s []int
  13.     for i, j := 0, 0; ; {
  14.         if i == len(l) {
  15.             return append(s, r[j:]...)
  16.         }
  17.         if j == len(r) {
  18.             return append(s, l[i:]...)
  19.         }
  20.         if l[i] < r[j] {
  21.             s = append(s, l[i])
  22.             i++
  23.         } else {
  24.             s = append(s, r[j])
  25.             j++
  26.         }
  27.     }
  28. }

堆排序

以将无序数列排列为从小到大序列为例：

  1. 从最后一个非叶子节点开始堆化，构建一个大顶堆；
  2. pop()出来一个最大元素加入有序部分的第一个位置，有序部分+1，无序部分-1；
  3. 重复步骤2，直到整个数组有序； ```go func sortArray(nums []int) []int { end := len(nums) - 1 // 从最后一个非叶子节点自下而上构造一个大顶堆 for i := len(nums)/2; i >= 0; i— {
    1.  heapify(nums, i, end)
    } // 不断构造有序部分，缩小堆大小 for i := end; i >= 0; i— {
    1.  // 将无需部分最大值移动到有序部分最前方，以构造递增序列
    2.  nums[i], nums[0] = nums[0], nums[i]
    3.  end--
    4.  heapify(nums, 0, end)
    } return nums }

// 将 nums 下标范围为 [root, end] 的节点构造为堆 func heapify(nums []int, root, end int) { for { maxChild := root * 2 + 1 // maxChild指向子节点中较大的一个 if maxChild > end { return } if maxChild + 1 <= end && nums[maxChild] < nums[maxChild+1] { maxChild++ } if nums[root] > nums[maxChild] { return } nums[root], nums[maxChild] = nums[maxChild], nums[root] root = maxChild } } ```

O(N)排序

桶排序