Java 快速排序模板

时间:2022-01-16作者:klpeng分类:IT综合浏览:312评论:0

         首先在数组中找到一个数 X,在数组中小于等于X的放在X左边去,大于等于X的放在X右边去。在X的左边和X的右边依次递归上述操作。

        筛选分治:将X左边都为<=X的,X右边都是>=X的

 public static int partition(int [] nums,int low,int high){
        int pivot = nums[low];  //存好 第一个数
        while(low<high){ //从一段数组的开头和末尾开始找
            while(low<high&&nums[high]>=pivot){ //从数组末尾找小于pivot的数 。找到停下
                high--;
            }
            //第一次的nums[low]被pivot存好了
            nums[low] = nums[high]; //把最右边小于pivot的数放到nums[low]中。
            while(low<high&&nums[low]<=pivot){//从数组开头找大于pivot的数 。找到停下
                low++;
            }
            nums[high] = nums[low]; //把最左边大于nums[low]的数放到num[high]中
        }
        //最后 low == high
        nums[low] = pivot; //最后将pivot放到 “中间”
        return low;
    }

        依次递归X的左右两边递归: 重复上述筛选分治操作

public static void   quick_sort(int nums[],int low ,int high){
        if(low<high){
            int temp = partition(nums,low,high); //找到  X 。
            // 递归排序
            quick_sort(nums,low,temp-1);   //排序小于X的数
            quick_sort(nums,temp+1,high);  //排序大于X的数
            
        }
    }

        代码示例: 输入n个数进行排序 


import java.util.*;
public class Main{
    public static void   quick_sort(int nums[],int low ,int high){
        if(low<high){
            int temp = partition(nums,low,high); //找到  X 。
            // 递归排序
            quick_sort(nums,low,temp-1);   //排序小于X的数
            quick_sort(nums,temp+1,high);  //排序大于X的数
            
        }
    }
    
    public static int partition(int [] nums,int low,int high){
        int pivot = nums[low];  //存好 第一个数
        while(low<high){ //从一段数组的开头和末尾开始找
            while(low<high&&nums[high]>=pivot){ //从数组末尾找小于pivot的数 。找到停下
                high--;
            }
            //第一次的nums[low]被pivot存好了
            nums[low] = nums[high]; //把最右边小于pivot的数放到nums[low]中。
            while(low<high&&nums[low]<=pivot){//从数组开头找大于pivot的数 。找到停下
                low++;
            }
            nums[high] = nums[low]; //把最左边大于nums[low]的数放到num[high]中
        }
        //最后 low == high
        nums[low] = pivot; //最后将pivot放到 “中间”
        return low;
    }
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int nums[] = new int[n];
        for(int i =0 ;i<n;i++){
            nums[i] = sc.nextInt();
        }
        quick_sort(nums,0,n-1);

        for(int i =0 ;i<n;i++){
            System.out.print(nums[i]+" ");
        }


    }


}

打赏
文章版权声明:除非注明,否则均为彭超的博客原创文章,转载或复制请以超链接形式并注明出处。
相关推荐

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

猜你喜欢