荷兰国旗

荷兰国旗问题

• 问题描述: 给定一个无序数组和一个值, 将数组划分为小于该数, 等于该数, 大于该数的三部分

• 思路: 使用改进快速排序的思想, 来对数组进行划分

• 代码:

  func Partition(arr []int, value int) (int, int) {
  	if arr == nil || len(arr) < 2 {
  		return -1, -1
  	}
  	left, right := -1, len(arr)
  	current := 0
  	for current < right {
  		if arr[current] == value {
  			current++
  		} else if arr[current] < value {
  			arr[left + 1], arr[current] = arr[current], arr[left + 1]
  			left++
  			current++
  		} else {
  			arr[right - 1], arr[current] = arr[current], arr[right - 1]
  			right--
  		}
  	}
  	return left + 1, right - 1
  }