首页 > 其他分享 >快速排序

快速排序

时间:2022-11-01 19:24:22浏览次数:42  
标签:right int partition array 排序 快速 public left

public class QuickSort {

    /**
     * 场景1
     * 给定一个数组,确定一个数字N,小于N的数组放最左边,大于N的放最右边
     */
    public static void splitNum(int[] array){
        int cur = 0;
        int lessIndex = 0;
        int len = array.length;
        while (cur < len) {
            if(array[cur] <= array[len-1]) {
                swap(array,cur,lessIndex++);
            }
            cur++;
        }
    }
    /**
     * 场景2
     * 给定一个数组,确定一个数字N,小于N的数组放最左边,大于N的放最右边,等于的放中间
     */
    public static void splitNum2(int[] array){
        int cur = 0;
        int lessIndex = -1;
        int len = array.length;
        int bigIndex = len - 1;
        while (cur < bigIndex) {
            if(array[cur] < array[len-1]) {
                swap(array,cur++,++lessIndex);
            } else if(array[cur] > array[len-1]){
                swap(array,cur,--bigIndex);  //这个不能交换后不能自增,因为交换过来的value还没进行判断
            } else {
                cur++;
            }
        }
        swap(array,bigIndex,len-1);
    }

    /**
     * 场景3
     * 快速排序
     * ans:递归实现
     */
    public static void quickSort(int[] array){
        if(array == null || array.length < 2) {
            return;
        }
        process(array,0,array.length-1);
    }
    public static void process(int[] array,int left,int right){
        if(left >= right) {
            return;
        }
        //取最后一个数,遍历数组,如果数比这个值小,放区域最左边,比这个数大,放区域最右边
        //相等的放中间,执行完成后返回相等值的左右边界坐标 (其实就相当于mid)
        //然后划分左右两片分区 进行递归
        int[] partition = partition(array, left, right);
        //左边
        process(array,left,partition[0]-1);
        //右边
        process(array,partition[1]+1,right);
    }
    public static int[] partition(int[] array,int left,int right){
        int lessIndex = left - 1;
        int bigIndex = right;
        while (left < bigIndex) {
            if(array[left] < array[right]) {
                swap(array,left++,++lessIndex);
            } else if(array[left] > array[right]){
                swap(array,left,--bigIndex);  //这个不能交换后不能自增,因为交换过来的value还没进行判断
            } else {
                left++;
            }
        }
        swap(array,bigIndex,right);
        return new int[]{lessIndex+1,bigIndex};
    }

    public static void swap(int[] array, int i, int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    /**
     * 场景4
     * 快速排序
     * ans2:非递归实现
     */
    public static void quickSortByStack(int[] array){
        if(array == null || array.length < 2) {
            return;
        }
        //把整个大数组的排序看成一个job
        Job job = new Job(0,array.length-1);
        Stack<Job> stack = new Stack<>();
        stack.push(job);
        while (!stack.isEmpty()) {
            Job exeuteJob = stack.pop();
            int[] partition = partition(array, exeuteJob.left, exeuteJob.right); //分区
            if(partition[0] > exeuteJob.left) {  //说明左边有值
                stack.push(new Job(exeuteJob.left,partition[0]-1));
            }
            if(partition[1] < exeuteJob.right) { //右边有值
                stack.push(new Job(partition[0]+1,exeuteJob.right));
            }
        }
    }
    public static class Job{
        int left;
        int right;
        public Job(int left,int right){
            this.left = left;
            this.right = right;
        }
    }
    public static void main(String[] args) {

        //ArrayUtil.testArraySorted(100000,50,50,QuickSort.class,"quickSort");
        ArrayUtil.testArraySorted(1000000,50,50,QuickSort.class,"quickSortByStack");
    }
}

标签:right,int,partition,array,排序,快速,public,left
From: https://www.cnblogs.com/xinay/p/16848863.html

相关文章

  • 归并排序
    publicclassMergeSort{/***ans2:非递归实现*/publicstaticvoidmergeSort2(int[]array){if(array==null||array.length<2......
  • Win11 使用Hyper-V快速安装Win10
    由于我的电脑更新成了win11,很多东西还不如win10找了半天没有找到hyper-v,于是就搜索记录一下过程过程安装hyper-v打开新建一个Hyper-V.cmd文件,将下面的内容粘入保存。......
  • 插入排序
    插入排序是基础简单,同时效率也不高的排序voidinsertion_sort(vector<int>&nums){ intn=nums.size(); //把第一个当作是有序序列,从第二个开始操作 for(inti=......
  • 用C语言实现的对单链表进行快速排序的算法
    typedefstructLinkNode{intdata;structLinkNode*next;}LinkNode,*LinkList;voidquickSortLinkList(LinkListlist,LinkNode*end){LinkNode......
  • 企业网站如何快速被搜索引擎收录
    对SEO推广很多人并不陌生,很多站长遇到类似的问题,就是网站的排名没有,特别是一个刚刚接手的新站,网站排名都没有。因此,要怎样才可实现新站排名和收录增长?开源字节将与大家......
  • Redis 中两个字段排序
    参考:Redis中两个字段排序 redis如何实现多字段排序1.多个维度使用数据库查询排序输出,目前使用的方式。 Redis用一个SortedSet解决按两个字段排序的问题,也就是......
  • C# 如何在一张大图片中快速找到另外一张图片(两种方式)?
    自己写了一种,速度不是很快,但是能够实现varfindpic=newFindPic();varrec=findpic.FindPicture(@"C:\Users\zaranet\Desktop\xiao.......
  • 阿里云配置负载均衡快速入门
    慎选监听配置的高级配置“开启会话保持”功能,单机测试负截均衡,看不到调度IP切换效果负载均衡从诞生到现在也随着网络业务的变化而不断的进化,逐渐发展成为现在云化的负......
  • AJAX基础+Axios快速入门+JSON使用+综合案例
    目录1、AJAX1.1概述1.1.1作用1.1.2同步和异步1.2快速入门1.2.1服务端实现1.2.2客户端实现1.3案例1.3.1需求1.3.2分析1.3.2后端实现1.3.3前端实现2、Axios异步......
  • 剑指offer——数字在排序数组中出现的次数
    题目描述:统计给定数字k在排序数组中出现的次数思路1:最容易想到但是效率不高的一个方法就是遍历整个数组,统计k出现的次数(for循环就能解决,不赘述)思路2:由于题目给出是排序......