golang快速排序算法

快速排序算法原理：

设置分水岭，把小于分水岭的数排到分水岭左侧，其余的排到右侧，递归的对分水岭两侧的元素做同样的处理

package qsort

func quickSort(values []int, left int, right int) {
	if left < right {

		// 设置分水岭
		temp := values[left]

		// 设置哨兵
		i, j := left, right
		for {
			// 从右向左找，找到第一个比分水岭小的数
			for values[j] >= temp && i < j {
				j--
			}

			// 从左向右找，找到第一个比分水岭大的数
			for values[i] <= temp && i < j {
				i++
			}

			// 如果哨兵相遇，则退出循环
			if i >= j {
				break
			}

			// 交换左右两侧的值
			values[i], values[j] = values[j], values[i]
		}

		// 将分水岭移到哨兵相遇点
		values[left] = values[i]
		values[i] = temp

		// 递归，左右两侧分别排序
		quickSort(values, left, i-1)
		quickSort(values, i+1, right)
	}
}

func QuickSort(values []int) {
	quickSort(values, 0, len(values)-1)
}

更简洁的版本：

package main

import "fmt"

func main() {
   numbers := []int{6, 2, 7, 7, 3, 8, 9}
   //fmt.Println(numbers)
   QuickSort(numbers)

   fmt.Println(numbers)
}

func QuickSort(values []int) {
   length := len(values)
   if length <= 1 {
      return
   }
   mid, i := values[0], 1    // 取第一个元素作为分水岭，i下标初始为1，即分水岭右侧的第一个元素的下标
   head, tail := 0, length-1 // 头尾的下标

   // 如果头和尾没有相遇，就会一直触发交换
   for head < tail {
      fmt.Println(values, head, tail, i)
      if values[i] > mid {
         // 如果分水岭右侧的元素大于分水岭，就将右侧的尾部元素和分水岭右侧元素交换
         values[i], values[tail] = values[tail], values[i]
         tail-- // 尾下标左移一位
      } else {
         // 如果分水岭右侧的元素小于等于分水岭，就将分水岭右移一位
         values[i], values[head] = values[head], values[i]
         head++ // 头下标右移一位
         i++    // i下标右移一位
      }
      fmt.Printf("----{head:%d,tail:%d,i:%d,mid:%d} values:%vn", head, tail, i, mid, values)
   }

   // 分水岭左右的元素递归做同样处理
   QuickSort(values[:head])
   QuickSort(values[head+1:])
}

更容易理解的版本

package main

import "fmt"

func main() {
    arr := []int{5, 4, 3, 6, 7, 8}
    rs := qsort(arr)
    fmt.Println(rs)
    // [3 4 5 6 7 8]
}

// 快速排序
func qsort(arr []int) []int {
    if len(arr) < 2 {
        return arr
    } else {
        pivot := arr[0]
        var less []int
        var greater []int
        for _, value := range arr[1:] {
            if value <= pivot {
                less = append(less, value)
            } else {
                greater = append(greater, value)
            }
        }

        var result []int
        result = append(result, qsort(less)...)
        result = append(result, pivot)
        result = append(result, qsort(greater)...)
        return result
    }
}

作者：golang中国

PHP面试网 站点 QQ交谈