【Java快速排序】

自己总结的一个快速排序算法及思想:

package main.com.xia.test3;


import java.util.Arrays;

public class Answer1{
    /* 采用分治思想将数组进行排序,通过获取基数的中间位置将数组分成左右两个数组。分别再对两个数组进行调用分治思想排序算法。
    我们假定从数组左边选择一个数作为基数,寻找其在数组的应该位置,该位置在数组中左边比基数小,右边比基数大。
    为了获取基数的中间位置,我们设定两个哨兵,数组最左边的一个哨兵,数组右边一个哨兵。然后将哨兵与基数比较大小。算法寻找基数的位置的算法如下:
    从右边寻找一个比基数小的值,然后与左哨兵更换值,。然后从右面哨兵起步,寻找一个比基数大的与右面的哨兵进行交换值。结束后,判断start是否比end小,如果是,继续本循环;
    不是,退出循环。并且将基数的值赋给start。返回start的数值*/
    public  static void main(String[] args){
        int[] test2 = new int[]{10,1,2,9,6,3,7,8,4,5};
        quickSort(0,test2.length - 1,test2);
        System.out.println(Arrays.toString(test2));
    }
    public static void quickSort(int start,int end,int[] array){
        if(start < end){
            int partion = getPosition(start,end,array);
            quickSort(start,partion,array);
            quickSort(partion + 1,end,array);
        }
    }
    public static int getPosition(int start,int end,int[] array){
        int tmp = array[start];
        while(start < end){
            //从数组右面开始寻找一个比tmp小的值。
            while(start < end && array[end] >= tmp){
                end--;
            }
            array[start] = array[end];
            //从数组右面开始寻找一个比tmp小的值。
            while(start <end && array[start] <= tmp){
                start++;
            }
            array[end] = array[start];
        }
        array[start] = tmp;
        return start;

    }
}

大家仔细观察getPosition()的内容是不是很面熟。不错和普通的交换算法很相似

    public static int getPosition(int start,int end,int[] array){
        int tmp = array[start];
        while(start < end){
            //从数组右面开始寻找一个比tmp小的值。
            while(start < end && array[end] >= tmp){
                end--;
            }
            array[start] = array[end];
            //从数组右面开始寻找一个比tmp小的值。
            while(start <end && array[start] <= tmp){
                start++;
            }
            array[end] = array[start];
        }
        array[start] = tmp;
        return start;

    }
如果把函数中的while循环注释掉,方法就变成了。
public static int getPosition(int start,int end,int[] array){
        int tmp = array[start];
//        while(start < end){
            //从数组右面开始寻找一个比tmp小的值。
//            while(start < end && array[end] >= tmp){
//                end--;
//            }
            array[start] = array[end];
            //从数组右面开始寻找一个比tmp小的值。
//            while(start <end && array[start] <= tmp){
//                start++;
//            }
            array[end] = array[start];
//        }
        array[start] = tmp;
        return start;
    }

普通冒泡算法:截图
【Java快速排序】

上一篇:中国冷弯设备行业需求态势及供需格局分析报告2022-2027年


下一篇:中国临床电子病历市场趋势报告、技术动态创新及市场预测