golang 排序_算法手撕-八大排序Go版本(上)

func bubbleSort1(arr []int) []int {
 // 代码中会大量用到len(arr)，为了减少重复计算，可以用一个变量来存储
 n := len(arr)
 for i := 0; i < n-1; i++ {
  for k := 0; k < n-1-i; k++ {
   if arr[k] > arr[k+1] {
    arr[k], arr[k+1] = arr[k+1], arr[k]
   }
  }
 }
 return arr
}
 

func bubbleSort2(arr []int) []int {
 n := len(arr)
 for i := 0; i < n-1; i++ {
  flag := 0
  for k := 0; k < n-1-i; k++ {
   if arr[k] > arr[k+1] {
    arr[k], arr[k+1] = arr[k+1], arr[k]
    flag += 1
   }
  }
  // 当遍历了一遍，flag仍然为0，说明原数组本身有序，所以不用再遍历，复杂度为O(n)
  if flag == 0 {
   break
  }
 }
 return arr
}
 

func selectSort(arr []int) []int {
 n := len(arr)
 for i := 0; i < n; i++ {
  // k=i+1，表示下一个数
  for k := i + 1; k < n; k++ {
   if arr[i] > arr[k] {
    arr[i], arr[k] = arr[k], arr[i]
   }
  }
 }
 return arr
}
 

func insertSort1(arr []int) []int {
 n := len(arr)
 for i := 1; i < n; i++ {
  idx := i
  for idx > 0 {
   if arr[idx] < arr[idx-1] {
    arr[idx], arr[idx-1] = arr[idx-1], arr[idx]
   }
   // 通过这里，我们可以看到插入排序是往后比较的
   idx -= 1
  }
 }
 return arr
}

func insertSort2(arr []int) []int {
 n := len(arr)
 for i := 1; i < n; i++ {
  idx := i
  for idx > 0 {
   if arr[idx] < arr[idx-1] {
    arr[idx], arr[idx-1] = arr[idx-1], arr[idx]
    idx -= 1
    // 当要插入的值，比排好序的数组的最后一个值大，则不用再比较
   } else {
    break
   }
  }
 }
 return arr
}
 

func quickSort(arr []int) []int {
 n := len(arr)
 if n <= 1 {
  return arr
 }
 left, right := []int{}, []int{}
 // 挑选基准值，这里以第一个元素为基准值
 base := arr[0]
 arr = arr[1:]
 // 对数组进行分割
 for _, num := range arr {
  if num < base {
   left = append(left, num)
  }else{
   right = append(right, num)
  }
 }
 // 这两行代码等价于 quickSort(left) + [base] + quickSort(right)
 result := append(quickSort(left), base)
 result = append(result, quickSort(right)...)
 return result
}
 

// 对数组进行划分，并返回下次划分的基准值
func partition(arr []int, startIdx, endIdx int) int {
 // 基准值
 base := arr[endIdx]
 i := startIdx - 1
 // 这一步把小于基准值的元素都挪到前面
 for j := startIdx; j < endIdx; j++ {
  if arr[j] < base {
   i++
   arr[j], arr[i] = arr[i], arr[j]
  }
 }
 // 这一步把基准值放到比它小的元素的后面
 arr[i+1], arr[endIdx] = arr[endIdx], arr[i+1]
 return i + 1
}
 
func quickSort2(arr []int, startIdx, endIdx int) {
 // 递归截止条件
 if startIdx >= endIdx {
  return
 }
 p := partition(arr, startIdx, endIdx)
 quickSort2(arr, startIdx, p-1)
 quickSort2(arr, p+1, endIdx)
}
 
// 如果对partition函数不理解的，建议使用下面的数组调试一遍，应该会更理解一些
func main() {
 arr := []int{3, 2, 1, 6, 8, 5, 4}
 quickSort2(arr, 0, len(arr) - 1)
 fmt.Println(arr)
}
 

// 合并
func merge(left []int, right []int) []int {
 leftIdx, rightIdx := 0, 0
 result := []int{}
 for leftIdx < len(left) && rightIdx < len(right) {
  if left[leftIdx] <= right[rightIdx] {
   result = append(result, left[leftIdx])
   leftIdx += 1
  } else {
   result = append(result, right[rightIdx])
   rightIdx += 1
  }
 }
 // 上述for循环有两种情况：
 // 1.left数组和right数组长度一致
 // 2.left数组和right数组长度不一致，则必定有一方有多余元素，需要把这些多余元素复制到队尾
 result = append(result, left[leftIdx:]...)
 result = append(result, right[rightIdx:]...)
 return result
}
 
func mergeSort(arr []int) []int {
 n := len(arr)
 if n <= 1 {
  return arr
 }
 
 split := n / 2
 left := mergeSort(arr[:split])
 right := mergeSort(arr[split:])
 return merge(left, right)
}