内容简介:1.先从数组里找出基准数。2.分治,将数组中比基准数小的放一边,比基准数大的放另外一边(这样的话就是以基准数为中心,将数组分成了两段了)。3.将分出的左右区间继续上面1,2的步骤,直到每个区间都有一个数字。这里简单看看上面的思路就可以看得出,快排其实也是用了分治法的思维来排序,从而达到了O(nlogn)的时间复杂度。假设现在有一个待排序的数组
思路
1.先从数组里找出基准数。2.分治,将数组中比基准数小的放一边,比基准数大的放另外一边(这样的话就是以基准数为中心,将数组分成了两段了)。3.将分出的左右区间继续上面1,2的步骤,直到每个区间都有一个数字。
这里简单看看上面的思路就可以看得出,快排其实也是用了分治法的思维来排序,从而达到了O(nlogn)的时间复杂度。
接着我用图来一步一步解释一下快速 排序 的步骤
假设现在有一个待排序的数组
int[] arr = {7, 5, 6, 9, 3, 1, 4};
找基准数(这里假设我们把每次的最左边的数来作为基准数) 这里以7作为基准数,然后用双指针标记数组的左边和右边,依次往中间判断。
第一步是4比7小,将4赋值给左指针,紧接着往右移动被赋值好的指针。
第二步是5比7小,继续后移指针。
第三步是6比7小,继续后移指针。
第四步是9比7大,将9赋值给右指针,同时右指针向前移动。
第五步是1比7小,将1赋值给左指针,同时左指针向后移动。
第六步是3比7小,指针直接往后移动。
第七步发现指针重叠了(其实就是找到了基准数的位置了,把7放在重叠的位置)
这样第一轮的基准数就找到了,接下来只需要将数组按新的基准数分区,找到新的基准数,然后一直重复上面的步骤就可以完成快速排序了。
问题
快速排序的话如果一直按以最左边来作为基准数的话是有问题的,假如说数组本身就是倒序的
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)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 图形化排序算法比较:快速排序、插入排序、选择排序、冒泡排序
- 排序算法下——桶排序、计数排序和基数排序
- 算法之常见排序算法-冒泡排序、归并排序、快速排序
- 【JS面试向】选择排序、桶排序、冒泡排序和快速排序简介
- 计数排序vs基数排序vs桶排序
- 排序算法--冒泡排序
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。