Java教程

算法基础之快速排序

本文主要是介绍算法基础之快速排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

快速排序(QuickSort)

基本思想

1、选定Pivot中心轴( 选取一个数作为基准数,一般取第一个数)
2、将大于Pivot的数字放在Pivot的右边
3、将小于Pivot的数字放在Pivot的左边 
4、分别对左右子序列重复前三步操作,直到各区间只有一个数

排序过程解析

例:[7,3,29,5,9]
第一次:
    选取第一个元素7为Pivot
    定义左右指针,分别指向第一个和最后一个元素
    将右指针指向元素9与7比较
    比元素7大,所以9还是放到右指针位置不动,右指针向前移动一位
    将右指针指向元素5与7比较
    比元素7小,所以5移动到左指针位置,左指针向后移动一位
    将左指针指向元素3与7比较
    比元素3小,所以3还是放到左指针位置不动,左指针向后移动一位
    将左指针指向元素29与7比较
    比元素7大,所以29移动到右指针位置,右指针向前移动一位
    左右指针相遇,第一次排序结束:
    结果 = [5、3、7、29、9]
    
递:
    左 [5、3],右 [29、9]
    重复上面步骤...
    左 [3、5],右 [9、29]

归:
    [3,5,7,9,29]

复杂度

最好时间复杂度为:O(nlogn) 最差 O(n^2) 空间复杂度 log(n) 快排是一种非稳定排序

代码解析

func QuickSort(list []int,begin int,end int)  {
if begin < end{
	// 切分排序
	loc := partition(list,begin,end)
	// 递归排序左边
	QuickSort(list,begin,loc-1)
	// 递归排序右边
	QuickSort(list,loc+1,end)
  }
}
  
// 将数组进行快速排序,返回排序后的中间元素索引
func partition(list []int,begin int,end int) int {
// list[being]为基准元素,用来比较
// 定义左右指针
left := begin + 1
right := end
// 当左右两指针重合时结束
for left < right{
        // 判断左指针元素是否大于基准元素,如果大于基准元素则左右指针元素交换位置,右指针--,否则左指针++
    if list[left] > list[begin] {
	list[left],list[right] = list[right],list[left]
	right--
    }else{
        left++
    }
}

// 当前左右指针重合,指向元素左边的都是小于基准元素的,右边的都是大于基准元素的
// 这里需要判断,指向元素是否比基准元素大,如果大于等于基准元素,那么left左移一格,将基准元素与比他小的元素替换位置
// 如果小于基准元素,那么不需要移动,直接将指向元素和基准元素替换位置即可
if list[left] >= list[begin]{
	left--
}

list[begin],list[left] = list[left],list[begin]

return left
}
这篇关于算法基础之快速排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!