美文网首页
快排算法

快排算法

作者: MikeShine | 来源:发表于2019-04-01 22:05 被阅读0次

这里对快速排序做一下总结(之前在写时间复杂度和空间复杂度时候想到的。)

1. 思想

快排的思想就是说,选定数组中第一个数参考值 key ,然后用两个指针,分别从前往后,从后往前,把比 key 大的放在后边,比 key 小的放在前边。两个指针相遇之后,把 key 和 这个停止点的值交换。至此完成一趟排序,到这里,比key大的都在key后面,比key小的都在key前面。
对 key 左边的子组迭代,对key右边的子组迭代,直到子组只含有一个数字为止。
这里用图来给出直观的展示:


快排图示

2. 代码

public class QuickSort {

    public void sort(int[] nums,int start,int end) {
        // 递归停止条件
        if(start>end) return;
        int left=start,right=end,key=nums[start];
        int temp=0;
        while(left<right){
            // 这里顺序很重要,要先从右边找。为了避免找过了的情况,还要限制 left<right
            while(left<right && nums[right]>=key)
                right--;
            while (left<right && nums[left]<=key)
                left++;
            temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            }

        nums[start] = nums[left];
        nums[left] = key;

        sort(nums,start,left-1);  // 这里对子组求一个递归即可
        sort(nums,left+1,end);
        }

    public static void main(String args[]){
        int a[] = {6,1,2,7,9,3,4,5,10,8};
        QuickSort q = new QuickSort();
        q.sort(a,0,a.length-1);
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]);
        }
    }
}

3. 关键点

  • 是递归的,对子数组
  • 递归停止条件是 start>end
  • 一趟中,要从右向左找
  • 同时为了避免找过了的情况,还要限制 left<right 指针

时间复杂度 nlogn

相关文章

  • 快排算法

    转:微信公众号:程序员小灰 快排算法 是按分治算法的思路进行排序的。 选定参照元素后,每次比较都按分治算法将小的移...

  • 快排算法

    本文摘自https://blog.csdn.net/yzllz001/article/details/509828...

  • 快排算法

    这里对快速排序做一下总结(之前在写时间复杂度和空间复杂度时候想到的。) 1. 思想 快排的思想就是说,选定数组中第...

  • 【算法】快排

    1.时间复杂度 2.快排

  • 2018-07-13

    快速排序算法 快排普通版本: 快排优化版本: 测试代码:

  • Java算法——快排算法

  • all

    算法与数据结构 常见算法类型 排序算法(冒泡、插入、选择、快排、希尔、堆排、归并、桶排、基数、计数)、字符串操作、...

  • 排序算法-快排

    1. 快排基本特征: 时间复杂度:O(nlogn)最坏:O(n^2) 空间复杂度: O(nlogn) 不稳定排序 ...

  • 快排【算法导论】

    注:学习算法导论,按照标准伪代码理解翻译为java实现,如有兴趣理解整个过程的细节,建议阅读《算法导论》第7章:快...

  • 归并、快排算法

    1. 归并算法 将一个待排序数组从中间分成 2 部分,分别将这 2 部分排好序,然后再将之合并。这是一个递归的过程...

网友评论

      本文标题:快排算法

      本文链接:https://www.haomeiwen.com/subject/onxibqtx.html