图解快速排序：Go 实现 _快速排序

文章插图

算法05:Golang快速排序Quick Sort
1.什么是快速排序(Quick Sort)快速排序是由东尼·霍尔所发展的一种排序算法.在平均状况下,排序 n 个项目要 Ο(nlogn) 次比较.在最坏状况下则需要 Ο(n2) 次比较,但这种状况并不常见. 事实上,快速排序通常明显比其他 Ο(nlogn) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来.
快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists).
快速排序又是一种分而治之思想在排序算法上的典型应用.本质上来看,快速排序应该算是在冒泡排序基础上的递归分治法
2.算法步骤

文章插图

img

从数列中挑出一个元素,称为 “基准”(pivot)
重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边).在这个分区退出之后,该基准就处于数列的中间位置.这个称为分区(partition)操作；
递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序；

递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了. 虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去.
3. Golang代码实现

文章插图

【图解快速排序：Go 实现】img

func partition(list []int, low, high int) int { pivot := list[low] //导致 low 位置值为空 for low < high {  //high指针值 >= pivot high指针移  for low < high && pivot <= list[high] {   high--  }  //填补low位置空值  //high指针值 < pivot high值 移到low位置  //high 位置值空  list[low] = list[high]  //low指针值 <= pivot low指针移  for low < high && pivot >= list[low] {   low++  }  //填补high位置空值  //low指针值 > pivot low值 移到high位置  //low位置值空  list[high] = list[low] } //pivot 填补 low位置的空值 list[low] = pivot return low}func QuickSort(list []int,low,high int)  { if high > low{  //位置划分  pivot := partition(list,low,high)  //左边部分排序  QuickSort(list,low,pivot-1)  //右边排序  QuickSort(list,pivot+1,high) }}func TestQuickSort(t *testing.T) { list := []int{2,44,4,8,33,1,22,-11,6,34,55,54,9} QuickSort(list,0,len(list)-1) t.Log(list)}