排序算法 (桶、冒泡、快速)

以下模块以Golang调试

桶排序(简化版)

桶排序，受限于所需要排序的数字区间，也就是说，当所需要排序的数字足够大的时候，就需要申请足够容纳数字最大值长度的内容空间，只需要对数字区间内的几个数字做排序；浪费空间；
复杂度：O(M+N)

  func bucketSort() {
      var (
          input  = []int{1, 8, 3, 5, 2, 4, 5}
          result = []int{}
      )
      for i := 0; i <= 10; i++ {
          result = append(result, 0)
      }
      for _, value := range input {
          result[value] += 1
      }
      for index, value := range result {
          if value > 0 {
              for i := 0; i < value; i++ {
                  if i < len(result)-1 {
                      fmt.Printf(" %v ", index)
                  } else {
                      fmt.Printf(" %v \n", index)
                  }
              }
          }
      }
  }

冒泡排序

每相邻的两位数进行排序，每次便利需要比较数组长度次数的数字，以上称为趟，总共需要比较数组长度-1趟；
排序复杂度：O(N2)

  func bubbleSort() {
      var (
          input = []int{1, 8, 3, 5, 2, 4, 5}
      )
      fmt.Printf("before sort input : %v\n", input)
      for index := 1; index <= len(input)-1; index++ {
          for i, j := 0, 1; j < len(input); i, j = i+1, j+1 {
              x, y := input[i], input[j]
              if x < y {
                  tmp := x
                  input[i] = y
                  input[j] = tmp
              }
          }
      }
      fmt.Printf("after sort input : %v\n", input)
  }

快速排序

快速排序，基于二分思想，以一个基准对象为分割，分割对象左右两边分别冒泡兑换，结果变成分割对象左右两边分别是大、小对象集合；然后再将两个集合依照上述的二分方式再次分割，直至全部排序，此处实现需要用到递归算法；
排序复杂度：O(N2), 平均时间复杂度：O(NlogN)

  func main() {
      var (
          input = []int{6, 1, 2, 7, 9, 3, 4, 5, 10, 8}
      )
      fastSort(input)
      fmt.Println("=========================> ", input)
  }


  func fastSort(arr []int) {
      if len(arr) > 1 {
          var (
              base  = arr[0]
              focus int
          )
          for j := len(arr) - 1; j >= 0; j-- {
              if j == focus {
                  break
              }
              if arr[j] < base {
                  for i := focus; i <= j; i++ {
                      if arr[i] > base {
                          tmp := arr[i]
                          arr[i] = arr[j]
                          arr[j] = tmp
                          focus = i
                          break
                      }
                      focus = i
                  }
              }
          }
          tmp := arr[focus]
          arr[focus] = arr[0]
          arr[0] = tmp


          fmt.Println("=========================> ", arr)


          fastSort(arr[:focus])
          fastSort(arr[focus+1:])
      }
  }

// 结果:
// =========================>  [3 1 2 5 4 6 9 7 10 8]
// =========================>  [2 1 3 5 4]
// =========================>  [1 2]
// =========================>  [4 5]
// =========================>  [8 7 9 10]
// =========================>  [7 8]
// =========================>  [1 2 3 4 5 6 7 8 9 10]

Note：转载注明出处！