快速排序 (Quick Sort)

栏目: IT技术 · 发布时间: 4年前

内容简介:1.先从数组里找出基准数。2.分治,将数组中比基准数小的放一边,比基准数大的放另外一边(这样的话就是以基准数为中心,将数组分成了两段了)。3.将分出的左右区间继续上面1,2的步骤,直到每个区间都有一个数字。这里简单看看上面的思路就可以看得出,快排其实也是用了分治法的思维来排序,从而达到了O(nlogn)的时间复杂度。假设现在有一个待排序的数组

思路

1.先从数组里找出基准数。2.分治,将数组中比基准数小的放一边,比基准数大的放另外一边(这样的话就是以基准数为中心,将数组分成了两段了)。3.将分出的左右区间继续上面1,2的步骤,直到每个区间都有一个数字。

这里简单看看上面的思路就可以看得出,快排其实也是用了分治法的思维来排序,从而达到了O(nlogn)的时间复杂度。

接着我用图来一步一步解释一下快速 排序 的步骤

假设现在有一个待排序的数组

int[] arr = {7, 5, 6, 9, 3, 1, 4};

找基准数(这里假设我们把每次的最左边的数来作为基准数) 这里以7作为基准数,然后用双指针标记数组的左边和右边,依次往中间判断。 快速排序 (Quick Sort)

第一步是4比7小,将4赋值给左指针,紧接着往右移动被赋值好的指针。 快速排序 (Quick Sort)

第二步是5比7小,继续后移指针。 快速排序 (Quick Sort)

第三步是6比7小,继续后移指针。 快速排序 (Quick Sort)

第四步是9比7大,将9赋值给右指针,同时右指针向前移动。 快速排序 (Quick Sort)

第五步是1比7小,将1赋值给左指针,同时左指针向后移动。 快速排序 (Quick Sort)

第六步是3比7小,指针直接往后移动。 快速排序 (Quick Sort)

第七步发现指针重叠了(其实就是找到了基准数的位置了,把7放在重叠的位置) 快速排序 (Quick Sort)

这样第一轮的基准数就找到了,接下来只需要将数组按新的基准数分区,找到新的基准数,然后一直重复上面的步骤就可以完成快速排序了。

问题

快速排序的话如果一直按以最左边来作为基准数的话是有问题的,假如说数组本身就是倒序的

int[] arr = { 9, 8, 7, 6, 5, 4};

那么其实这么找的话,快速排序的时间复杂度就跟O(n2)没什么区别,所以这里的话是最好把每次选择的基准数作为随机数来选择。这里的话我简单就用了下中位数来作为基准数。

代码

public class QuickSort {

public static void main(String[] args) {

int[] arr = { 7, 5, 6, 9, 3, 1, 4 };

quickSort(arr, 0, arr.length - 1);


System.out.println("排序后:");

for (int i : arr) {

System.out.println(i);

}

}


private static void quickSort(int[] arr, int left, int right) {

// 在左右指针没有重合的时候继续分治的找

if(left < right) {


// 这里找到基准数

int index = getIndex(arr, left, right);

// 根据基准数继续分成左右两个区间找(分治法的思维)

quickSort(arr, left, index-1);

quickSort(arr, index+1, right);

}

}


private static int getIndex(int[] arr, int left, int right) {


swap(arr, left, left + (right-left)/2);


int temp = arr[left];

while (left<right) {

while(left<right && arr[right] >= temp) {

right--;

}

arr[left] = arr[right];

while (left < right && arr[left] <= temp) {

left++;

}

arr[right] = arr[left];

}


arr[left] = temp;


return left;

}

}

最后

其实还有别的基准数选择方式,这里需要大家去自行挖掘了!

掘金地址:https://juejin.im/post/5e63c2b7f265da57127e5480


以上所述就是小编给大家介绍的《快速排序 (Quick Sort)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

研究之美

研究之美

[美] Donald E. Knuth / 高博 / 电子工业出版社 / 2012-1-1 / 49.00元

《研究之美》是计算机科学大师、“算法分析之父”高德纳(Donald E.Knuth)在20世纪70年代旅居挪威时撰写的适用于计算机科学的一种全新基础数学结构的情景小品。全书以一对追求自由精神生活的青年男女为主人公,展开了一段对于该种全新结构的发现和构造的对白。在此过程中,本书充分展示了计算机科学的从业人员进行全新领域探索时所必备的怀疑、立论、构造、证明、归纳、演绎等逻辑推理和深入反思的能力。《研究......一起来看看 《研究之美》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具