前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布

快排

作者头像
用户6055494
发布2019-10-13 08:36:45
7070
发布2019-10-13 08:36:45
举报
文章被收录于专栏:AVAJ

快速排序

思路:快速排序每次都是定位一个元素在数组中的绝对位置,简单说就是一个元素,在排好序后他的位置是一定的(当然快排是不稳定的),你每次选定一个元素,然后定位其排好序后的位置,再把这个元素从数组中去掉,就绪递归定位其他元素。最好的情况下就是每次选的元素都在最中间,这样就递归次数就少了(nlog2n),最坏情况就是每次都选在俩端(n^2)。

代码:

代码语言:javascript
复制
// 递归 每次找出标准值的位置 然后排除它 继续递归其他元素public static void quickSort(int[] arr,int start,int end) {    if(arr == null || arr.length < 1) {        return;    }    // 递归退出的标志    if (start >= end) {        return;    }    // 标准值    int standard = findStandard(arr, start, end);    // 左边递归    quickSort(arr,start,standard - 1);    // 右边递归    quickSort(arr,standard + 1,end);
}public static int findStandard(int[] arr,int start,int end) {    int left = start;    int right = end;    // 这里就随意一点啦选第一个作为标准值    int standard = arr[start];    while (left < right) {        // 在左边寻找一个比标志值大的        while (left <= right && standard >= arr[left]) {left++;}        // 在右边寻找一个比标准值小的        while (left <= right && standard <= arr[right]) {right--;}        // 交换它们        if (left < right) {            swap(arr,left,right);        }    }    // 定位到标准值后 交换    swap(arr,start,right);    // 返回    return right;}public static void swap(int [] a,int i,int j) {    int temp = a[i];    a[i] = a[j];    a[j] = temp;}

总结:利用这种寻找标准值的方法可用到其他算法中去比如要求使数组中的元素奇数在前偶数在后等。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-10-02,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员面试鸭 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档