地球仪的BLOG

go 快速排序

package main
import (
 "fmt"
)
func main() {
 var arr = []int{9, 4, 7, 6, 8, 3, 2, 5, 1}
 fmt.Println("before", arr)
 quickSort(arr, 0, len(arr)-1)
 fmt.Println("after ", arr)
}
/*****************************************************************************
* \author
* \date
* \brief       递归快排
* \param[in]    arr：待排序切片 startIndex，endIndex：起始，结束索引
* \param[out]
* \return      输入返回值描述
* \ingroup     输入所属组
* \remarks
*****************************************************************************/
func quickSort(arr []int, startIndex, endIndex int) {
 // 递归结束条件：startIndex大等于endIndex的时候
 if startIndex >= endIndex {
  return
 }
 // 得到基准元素位置
 var pivotIndex = partition(arr, startIndex, endIndex)
 // 根据基准元素，分成两部分递归排序(分治法)
 quickSort(arr, startIndex, pivotIndex-1)
 quickSort(arr, pivotIndex+1, endIndex)
 return
}
func partition(arr []int, startIndex, endIndex int) int {
 // 取第一个位置的元素作为基准元素
 var pivot = arr[startIndex]
 var left = startIndex // 0
 var right = endIndex  // 8
 for left != right {
  //控制right指针比较并左移
  for left < right && arr[right] > pivot {
   right--
  }
  //控制right指针比较并右移
  for left < right && arr[left] <= pivot {
   left++
  }
  //交换left和right指向的元素
  if left < right {
   arr[left], arr[right] = arr[right], arr[left]
  }
 }
 //pivot和指针重合点交换
 arr[left], arr[startIndex] = arr[startIndex], arr[left]
 return left
}