精选文章 非递归快排--Java

非递归快排--Java

作者:JingleLiA 时间: 2019-11-11 08:56:29
JingleLiA 2019-11-11 08:56:29

见标题

package test;

import java.util.*;
public class Main {
	static Scanner in = new Scanner(System.in);
    static int partion(int[] array,int low,int high){//合并排序部分
        int tmp = array[low];
        while(low= tmp){
                --high;
            }
            if(low >= high){
                break;
            }else{
                array[low] = array[high];//交换小值去前面
            }
            
            while(low < high && array[low] <= tmp){
                ++low;
            }
            if(low >= high){
                break;
            }else{
                array[high] = array[low];//交换大值去后面
            }
        }
        array[low] = tmp;//枢值归位
        return low;
    }
    static void QuickSort(int[] array){
        int[] stack = new int[array.length];//利用一个栈来保存每次需要排序的左右端点信息
        int top = 0;
        int low = 0;
        int high = array.length-1;
        int par = partion(array, low, high);//得到第一个划分点
        if(par > low+1){//左端点是否存在
            stack[top++] = low;
            stack[top++] = par-1;
        }
        if(par < high-1){//左端点是否存在
            stack[top++] = par+1;
            stack[top++] = high;
        }
        while(top > 0){//过程同上,用循环代替递归
            high = stack[--top];
            low = stack[--top];
            par = partion(array, low, high);
            if(par > low+1){
                stack[top++] = low;
                stack[top++] = par-1;
            }
            if(par < high-1){
                stack[top++] = par+1;
                stack[top++] = high;
            }
        }

    }

    public static void main(String[] args) {
//    	while (in.hasNext()){
    		String[] s=in.nextLine().split(" ");
    		int n = s.length;
			int[] a = new int[n-1];
			for (int i = 1; i < n; i++)
				a[i-1] = Integer.parseInt(s[i]);
			QuickSort(a);
			for (int i = 0; i < n-2; i++)
				System.out.print(a[i]+" ");
			System.out.println(a[n-2]);
//		}
    }

}

 

分享文章到微博
分享文章到朋友圈

上一篇:thinkphp5第35课:表单令牌

下一篇:将本地项目上传到码云,只需这几步,每个步骤都有图文

CSDN

CSDN

中国开发者社区CSDN (Chinese Software Developer Network) 创立于1999年,致力为中国开发者提供知识传播、在线学习、职业发展等全生命周期服务。