【算法笔记】排序

//泡沫排序
func BubbleSort() {
 data := []int{8, 100, 99, 50, 22, 15, 16, 2, 99, 1000, 999, 1}

 for i := 0; i < len(data); i++ {
  for j := 0; j < len(data)-1-i; j++ {
   if data[j] > data[j+1] {
    v := data[j]
    data[j] = data[j+1]
    data[j+1] = v
   }
  }
 }

 fmt.Println(data)
}

//选择排序
func SelectionSort() {
 data := []int{8, 100, 99, 50, 22, 15, 16, 2, 99, 1000, 999, 1}

 var book int
 for i := 0; i < len(data); i++ {
  book = i
  for j := i; j < len(data); j++ {
   if data[book] > data[j] {
    book = j
   }
  }
  v := data[i]
  data[i] = data[book]
  data[book] = v
 }

 fmt.Println(data)
}

//直接插入排序。因为我太不喜欢直接串改数组数据，所以写的有点像倒过来的冒泡排序
func InsertionSort() {
 data := []int{8, 100, 99, 50, 22, 15, 16, 2, 99, 1000, 999, 1}

 var v int
 for i := 0; i < len(data); i++ {
  for j := i; j > 0; j-- {
   if data[j] < data[j-1] {
    v = data[j]
    data[j] = data[j-1]
    data[j-1] = v
   } else {
    break
   }
  }
 }

 fmt.Println(data)
}

//网上的优雅的写法
func ShellSort() {
 data := []int{8, 100, 99, 50, 22, 15, 16, 2, 99, 1000, 999, 1}

 for step := len(data) / 2; step > 0; step /= 2 {
  //开始插入排序
  for i := step; i < len(data); i++ {
   //满足条件则插入
   for j := i - step; j >= 0 && data[j+step] < data[j]; j -= step {
    data[j], data[j+step] = data[j+step], data[j]
   }
  }
 }

 fmt.Println(data)
}

//我自己琢磨了半天才写出来的复杂版..ㅠㅠ
func ShellSort1() {
 data := []int{8, 100, 99, 50, 22, 15, 16, 2, 99, 1000, 999, 1}

 //先按照增量循环
 for step := len(data) / 2; step > 0; step = step / 2 {
  //每次增量的循环数
  for i := 0; i < step; i++ {
   //插入排序
   for j := i; j < len(data); j = j + step {
    for k := i; k < j; k = k + step {
     if data[k] > data[j] {
      v := data[j]
      //为了插入往右挪数据
      for l := j; l > k; l = l - step {
       data[l] = data[l-step]
      }
      data[k] = v
     }
    }

   }
  }
 }

 fmt.Println(data)
}