首页 > 代码库 > 快速排序
快速排序
一、什么是快速排序?
把一个无序的数组,第一趟排序后将数组分隔成两部分,若把前半部分和后半部分的相交元素称为中间元素。前半部分的所有元素小于中间元素,后半部分的所有元素大于中间元素。再对前半部分和后半部分分别进行上述递归操作。最终得到一个有序数组。
二、如何进行快速排序?
最近正好我在学习Go语言,决定用Go语言自己描述一遍。
func QuickSort(arr []int) { if len(arr) <= 1 { return } mid, i := arr[0], 1 left, right := 0, len(arr)-1 for left < right { if arr[i] > mid { arr[i], arr[right] = arr[right], arr[i] right-- } else { arr[i], arr[left] = arr[left], arr[i] left++ i++ } } arr[left] = mid QuickSort(arr[:left]) QuickSort(arr[left+1:]) }
但是,上面的代码会存在交换次数过多的问题,这个问题可以使用下面代码进行优化。
func QuickSort(arr []int) { if len(arr) <= 1 { return } mid := arr[0] left, right := 0, len(arr)-1 for left < right { if left < right && arr[right] >= mid { right-- } arr[left++] = arr[right] if left < right && arr[left] <= mid { left++ } arr[right--] = arr[left] } arr[left] = mid QuickSort(arr[:left]) QuickSort(arr[left+1:]) }
快速排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。