排序

  1. package sort
  3. // 冒泡排序
  4. func Bubble(param []int) {
  5.     limit := len(param) - 1
  6.     for i := 0; i < len(param); i++ {
  7.         for j := 0; j < limit; j++ {
  8.             if param[j] <= param[j+1] {
  9.                 continue
  10.             }
  11.             param[j], param[j+1] = param[j+1], param[j]
  12.         }
  13.         limit--
  14.     }
  15. }
  17. // 比较两个数组
  18. func CompareIntSlice(param1, param2 []int) bool {
  19.     len1 := len(param1)
  20.     len2 := len(param2)
  21.     if len1 != len2 {
  22.         return false
  23.     }
  25.     for i := range param1 {
  26.         if param1[i] != param2[i] {
  27.             return false
  28.         }
  29.     }
  30.     return true
  31. }
  33. // 插入排序
  34. func Insertion(param []int) {
  35.     for i := 1; i < len(param); i++ {
  36.         curValue := param[i]
  37.         for j := i - 1; j >= 0; j-- {
  38.             if param[j] > curValue {
  39.                 param[j+1] = param[j]
  40.             } else {
  41.                 param[j+1] = curValue
  42.                 break
  43.             }
  44.         }
  45.     }
  46. }
  48. // 选择排序
  49. func Selection(param []int) {
  50.     for i := 0; i < len(param)-1; i++ {
  51.         minValueIdx := i
  52.         for j := i + 1; j < len(param); j++ {
  53.             if param[j] < param[minValueIdx] {
  54.                 minValueIdx = j
  55.             }
  56.         }
  57.         param[i], param[minValueIdx] = param[minValueIdx], param[i]
  58.     }
  59. }
  61. // 归并排序
  62. func Merge(param []int, l, r int) {
  63.     if l >= r {
  64.         return
  65.     }
  67.     m := (l + r) / 2
  68.     Merge(param, l, m)
  69.     Merge(param, m+1, r)
  71.     merge(param, l, m, m+1, r)
  72. }
  74. // 合并
  75. func merge(param []int, l, m, m1, r int) {
  76.     merged := make([]int, r-l+1)
  77.     i, j, k := l, m1, 0
  78.     for i <= m && j <= r {
  79.         if param[i] < param[j] {
  80.             merged[k] = param[i]
  81.             k, i = k+1, i+1
  82.         } else {
  83.             merged[k] = param[j]
  84.             k, j = k+1, j+1
  85.         }
  86.     }
  88.     remainL, remainR := i, m
  89.     if j <= r {
  90.         remainL, remainR = j, r
  91.     }
  92.     copy(merged[k:], param[remainL:remainR+1])
  93.     copy(param[l:r+1], merged)
  94. }
  96. // 快排
  97. func Quick(param []int, l, r int) {
  98.     if l >= r {
  99.         return
  100.     }
  102.     pivot := partition(param, l, r)
  103.     Quick(param, l, pivot-1)
  104.     Quick(param, pivot+1, r)
  105. }
  107. // 分区
  108. func partition(param []int, l, r int) int {
  109.     i, j := l, l
  110.     for j < r {
  111.         if param[j] >= param[r] {
  112.             j++
  113.         } else {
  114.             param[i], param[j] = param[j], param[i]
  115.             i, j = i+1, j+1
  116.         }
  117.     }
  118.     param[i], param[j] = param[j], param[i]
  119.     return i
  120. }

查找

package find

func BinarySearchRecursive(param []int, l, r, target int) int {
    if l > r {
        return -1
    }

    var idx int
    m := (l + r) / 2
    if target < param[m] {
        idx = BinarySearchRecursive(param, l, m-1, target)
    } else if param[m] < target {
        idx = BinarySearchRecursive(param, m+1, r, target)
    } else {
        return m
    }
    return idx
}

func BinarySearchIterate(param []int, l, r, target int) int {
    for l <= r {
        m := (l + r) / 2
        if target < param[m] {
            r = m - 1
        } else if param[m] < target {
            l = m + 1
        } else {
            return m
        }
    }
    return -1
}