快速排序

快速排序思路

快速排序通过分支法的思想,从一个数组中选取一个基准元素pivot,把这个数组中小于pivot的移动到左边,把大于pivot的移动到右边。然后再分别对左右两边数组进行快速排序。

双边循环法

思路

设置两个指针left和right,最初分别指向数组的左右两端。比较right指针指向元素和pivot元素,如果right元素大于pivot元素,right指针左移一位,再和pivot进行比较,如果right元素小于pivot元素的话停止移动,换到left指针。
left指针的操作是,left指针指向的元素和pivot元素比较,如果left指向元素小于或等于pivot,left指针右移,如果left元素大于pivot元素,停止移动。
左右都停止移动后,交换left和right指向的元素,这样left指针指向的是一个小于pivot的元素,right指向的是一个大于pivot的元素。
当left和right重叠的时候结束比较,将第一个元素和left,right指向的元素做交换,完成一轮排序

代码

func partition(arr []int, startIndex, endIndex int) int {
 var (
 pivot = arr[startIndex]
 left = startIndex
 right = endIndex
 )
 for left != right {
 for left < right && pivot < arr[right] {
 right--
 }
 for left < right && pivot >= arr[left] {
 left++
 }
 if left < right {
 arr[left], arr[right] = arr[right], arr[left]
 }
 }
 arr[startIndex], arr[left] = arr[left], arr[startIndex]
 return left
}

单边循环法

思路

单边循环代码实现简单。
通过一个mark指针,指向小于pivot的集合的最后一个元素,最后把第一个元素和mark指向的元素做交换,进行下一轮。
mark指针开始指向第一个元素,然后开始遍历数组,如果当前元素比pivot大,继续遍历,如果比pivot小,mark指针右移,将mark指向元素和当前遍历元素交换。

代码

func partitionv2(arr []int, startIndex, endIndex int) int {
 var (
 mark = startIndex
 pivot = arr[startIndex]
 point = startIndex + 1
 )
 for point < len(arr) {
 if arr[point] < pivot {
 mark++
 arr[mark], arr[point] = arr[point], arr[mark]
 }
 point++
 }
 arr[startIndex], arr[mark] = arr[mark], arr[startIndex]
 return mark
}

pivot选择

有数组5,4,3,2,1要进行排序,如果选择第一个元素作为pivot的话,,每次选择的都是该数组中的最大值或最小值,每次进行排序只确定了一个元素的位置,导致时间复杂度退化成O(n^2)
在选择pivot时,可以用随机选择的方式选择,即在当前数组中随机选择一个元素来作为pivot,减少选择到最大值或最小值的几率。

非递归方法

思路

将递归改为循环和栈的方式,以下代码中的栈是自己实现的。

代码

func QuickSortNonRecursive(arr []int, startIndex, endIndex int) {
 var (
 s = v1.NewStack()
 m = make(map[string]int)
 start = "start_index"
 end = "end_index"
 )
 m[start] = startIndex
 m[end] = endIndex
 s.Push(m)
 for !s.IsEmpty() {
 param := s.Pop().(map[string]int)
 pivotIndex := partitionv2(arr, param[start], param[end])
 if param[start] < pivotIndex-1 {
 leftParam := make(map[string]int)
 leftParam[start] = param[start]
 leftParam[end] = pivotIndex - 1
 s.Push(leftParam)
 }
 if param[end] > pivotIndex+1 {
 rightParam := make(map[string]int)
 rightParam[start] = pivotIndex + 1
 rightParam[end] = param[end]
 s.Push(rightParam)
 }
 }
}

总结

全部代码

package sort
import (
 v1 "xiawan/algorithm/stack/v1"
)
func QuickSort(arr []int, startIndex, endIndex int) {
 if startIndex >= endIndex {
 return
 }
 pivotIndex := partitionv2(arr, startIndex, endIndex)
 QuickSort(arr, startIndex, pivotIndex-1)
 QuickSort(arr, pivotIndex+1, endIndex)
}
//双边循环,从右侧开始
func partition(arr []int, startIndex, endIndex int) int {
 var (
 pivot = arr[startIndex]
 left = startIndex
 right = endIndex
 )
 for left != right {
 for left < right && pivot < arr[right] {
 right--
 }
 for left < right && pivot >= arr[left] {
 left++
 }
 if left < right {
 arr[left], arr[right] = arr[right], arr[left]
 }
 }
 arr[startIndex], arr[left] = arr[left], arr[startIndex]
 return left
}
//单边循环
func partitionv2(arr []int, startIndex, endIndex int) int {
 var (
 mark = startIndex
 pivot = arr[startIndex]
 point = startIndex + 1
 )
 for point < len(arr) {
 if arr[point] < pivot {
 mark++
 arr[mark], arr[point] = arr[point], arr[mark]
 }
 point++
 }
 arr[startIndex], arr[mark] = arr[mark], arr[startIndex]
 return mark
}
func QuickSortNonRecursive(arr []int, startIndex, endIndex int) {
 var (
 s = v1.NewStack()
 m = make(map[string]int)
 start = "start_index"
 end = "end_index"
 )
 m[start] = startIndex
 m[end] = endIndex
 s.Push(m)
 for !s.IsEmpty() {
 param := s.Pop().(map[string]int)
 pivotIndex := partitionv2(arr, param[start], param[end])
 if param[start] < pivotIndex-1 {
 leftParam := make(map[string]int)
 leftParam[start] = param[start]
 leftParam[end] = pivotIndex - 1
 s.Push(leftParam)
 }
 if param[end] > pivotIndex+1 {
 rightParam := make(map[string]int)
 rightParam[start] = pivotIndex + 1
 rightParam[end] = param[end]
 s.Push(rightParam)
 }
 }
}

本文来自:Segmentfault

感谢作者:黄淑宁

查看原文:快速排序及golang实现

• 编辑
• 预览