快速排序 (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)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

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

GOOGLE HACKS

GOOGLE HACKS

Rael Dornfest、Tara Calishain / 卞军、谢伟华、朱炜 / 电子工业 / 2006-1 / 49.00元

GOOGLE HACKS巧妙使用网络搜索的技巧和工具(第二版)一起来看看 《GOOGLE HACKS》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换