搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 程序技术分享 > 快速排序(1)双边循环

快速排序(1)双边循环

程序技术分享 2019-11-08


快速排序-双边循环



01

问题抛出

        对于冒泡排序,时间复杂度为O(n*n),(没办法打出平方),有没有一种好的排序方法比冒泡排序要快。

           答案当然是有的,快速排序,堆排序,归并排序的时间复杂度都比冒泡排序要小。今天我们先介绍快速排序,因为快速排序很冒泡很类似。



02

什么是快速排序

        快速排序和冒泡排序都是交换排序,交换元素的位置,达到有序的效果。只是快速排序是选取基准数,让元素与基准数作比较。大于基准数的在一边,小于基准数的在一边,重复执行,直到有序。

        如一组数,选择任意位置的数作为基准数(一般方便,选取最后和开头的位置),选取三个位置,-1位置表示left指针(小于区域的边界,小于指针位置的数都是小于基准数的),0位置表示current,表示当前位置的数。arr.length-1位置,表示right指针大于基准数的区域边界。


快速排序(1)双边循环

(1)第一次比较,current 指向3。3<4,小于基准数,位置不变,current++; 移动到下一位5,left指针加1,原则上做到指针小于等于left的,都是小于基准数(极端会存在值等于基准数的也会出现在left左侧)如下。

快速排序(1)双边循环

(2)第二次比较,current指向5,5>4,大于基准数,current位置与right-1,位置交换位置。right指针向左移动一位,扩大大于区域的位置

快速排序(1)双边循环

(3)第三次比较,current位置为9,9>4,大于基准数。步骤同上。

快速排序(1)双边循环

(4)第四次比较,current位置为1,1<4,小于基准数。步骤同(1)。

快速排序(1)双边循环

(5)第五次比较,2<4,步骤同上

快速排序(1)双边循环

(6)第六次比较,4=4 ,位置不变,也不交互。current 指针右移动。current==right 结束循环

快速排序(1)双边循环

上面一趟数据的比较之后,数据大致分为如下。

快速排序(1)双边循环

最后一个数和right位置交换,

快速排序(1)双边循环
快速排序(1)双边循环

        每调整一次结束,就能确定选中的基准数应放的位置,因为小于在左边,大于在右边,即使后续递归调整大于基准数的区域和小于基准数的区域的数据位置,基准数位置也不会变化,直到小于区域和大于区域所有数的位置被确定,才做到有序。


public class quickSort { //快速排序 public static void main(String[] args) { int[] arr_sort = new int[]{3, 5,4, 2, 1, 9, 4};
if (arr_sort.length < 2 || arr_sort == null) { return; } sort(arr_sort, 0, arr_sort.length - 1); for (int val : arr_sort) { System.out.println(val); } }
public static void sort(int[] arr, int l, int r) { if (l < r) { int p = parision(arr, l, r); sort(arr, l, p-1 ); sort(arr, p+1, r); } }
//获取相等元素的下标 public static int parision(int[] arr, int l, int r) { int left = l - 1; int right = r; while (l < right) { if (arr[l] > arr[r]) { swap(arr, l, --right); } else { l++; left++; } } swap(arr, right, r); return right; }
public static void swap(int[] arr, int index, int i) { int temp = arr[i]; arr[i] = arr[index]; arr[index] = temp; }}
快速排序(1)双边循环
END
快速排序(1)双边循环





快速排序(1)双边循环
长按扫码关注



  

版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《快速排序(1)双边循环》的版权归原作者「程序技术分享」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注程序技术分享微信公众号

程序技术分享微信公众号:nannanwangno1

程序技术分享

手机扫描上方二维码即可关注程序技术分享微信公众号

程序技术分享最新文章

精品公众号随机推荐