Open hello2dj opened 5 years ago
因为我们在把头尾index往里缩时我们判断的是小于和不小于(大于同理),比如我们把pivot 5 放在中间,当我们的头index判断不小于时,若是到了pivot条件也是成立的就跳到了pivot右侧,此时若是尾index也在右边发现了小于pivot的值在交换时就会出现,小于pivot的值出现在pivot的右侧,当然我们也可以做额外操作,判断若是头index到了pivot的位置时则不再继续
1. | | V V 4, 5, 8, 2 头 尾 2. | | V V 4, 5, 2, 8 头 尾 3. 此时找到了大于以及小于的pivot的值交换 4,5,2,8, 显然出问题了 、、、、、、 但是若是5在头部 5,4,8,2, 交换就没事了,因为接下来会有把pivot和low或者high交换的过程
2,1,2,1,3,4,5
上述3已经在正确位置了,再接下来的排序应当是4,5和2,1,2,1两组进行排序而不是3,4,5和2,1,2,1或者4,5和2,1,2,1, 3进行排序, 因为3已经是在正确位置了,没必要再排一次。
解析:元素较少时,大家都差不多,反而是希尔排序这样的好一些,好在哪啊? 我们都知道快排在元素基本有序时是最慢的最坏能达到o(n^2),所以当序列基本有序时我们可以采用堆排序
package main import ( "fmt" ) // threads 线程标识创建线程的个数 func quicksort(nums []int, length int) { if length <= 1 { return } left := 1 right := length - 1 pivot := nums[0] for{ for; left < right && nums[right] > pivot; right--{ } for; left < right && nums[left] <= pivot; left++ { } if left >= right { break } nums[left], nums[right] = nums[right], nums[left] } nums[0], nums[left] = nums[left], nums[0] quicksort(nums[0:left], left) //分任务 temp := nums[left + 1: length] quicksort(temp, len(temp)) return } func main() { x := []int{3, 41, 24, 76, 11, 45, 3, 3, 64, 21, 69, 19, 36} quicksort(x[:], len(x)) fmt.Println(x); }
quicksort([]) -> []; quicksort([Pivot|Rest]) -> {Smaller, Larger} = partition(Pivot, Rest, [], []), quicksort(Smaller) ++ [Pivot] ++ quicksort(Larger). partition(_, [], Smaller, Larger) -> {Smaller, Larger}; partition(Pivot, [H|T], Smaller, Larger) -> if H =< Pivot -> partition(Pivot, T, [H|Smaller], Larger); H > Pivot -> partition(Pivot, T, Smaller, [H|Larger]) end.
erlang版的快排,很清晰的告诉了我们快排的核心思想~一次确定一个数字的位置
每种语言总是有自己发光的地方,就好比普通的你我
快速排序时为什么一定要把pivot放到头或尾最后在放回去呢?
因为我们在把头尾index往里缩时我们判断的是小于和不小于(大于同理),比如我们把pivot 5 放在中间,当我们的头index判断不小于时,若是到了pivot条件也是成立的就跳到了pivot右侧,此时若是尾index也在右边发现了小于pivot的值在交换时就会出现,小于pivot的值出现在pivot的右侧,当然我们也可以做额外操作,判断若是头index到了pivot的位置时则不再继续
我们每进行一次交换就会找到一个元素的正确位置,此时接下来再排序时就不要再把他算进去了
上述3已经在正确位置了,再接下来的排序应当是4,5和2,1,2,1两组进行排序而不是3,4,5和2,1,2,1或者4,5和2,1,2,1, 3进行排序, 因为3已经是在正确位置了,没必要再排一次。
我们可看看golang源码的排序
解析:元素较少时,大家都差不多,反而是希尔排序这样的好一些,好在哪啊? 我们都知道快排在元素基本有序时是最慢的最坏能达到o(n^2),所以当序列基本有序时我们可以采用堆排序
一个简单的快排版本
用函数式编程语言来写快排,不可变数据属性,反而使得思想明了
erlang版的快排,很清晰的告诉了我们快排的核心思想~一次确定一个数字的位置