面试常用算法之排序(3)

2019-08-26 06:40:27来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

面试常用算法之排序(3)

快速排序

package algorithm.sort;

/**
 * 快速排序
 * 思想:类似于归并排序,但是不同于归并排序每次排序寻找一次子数组中点的是,寻找一个更恰当的分区点
 *
 * @Author 28370
 * @Date 2019-5-13
 **/
public class QuickSort {
    public static void main(String[] args) {
        int[] a= {1,7,4,8,5,3,9,2};
        quickSort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);


        }
    }

    public static void quickSort(int[] a){
        quickSortInternally(a, 0, a.length-1);
    }

    private static void quickSortInternally(int[] a, int p, int r) {
        if(p >= r){
            return ;
        }
        int q = partition(a, p, r);
        quickSortInternally(a, p, q-1);
        quickSortInternally(a, q+1, r);
    }

    //获取分区点
    private static int partition(int[] a, int p, int r) {
        int pivot = a[r];
        System.out.println(pivot);
        int i = p;
        for (int j = p; j < r; ++j) {
            System.out.println("j="+j+",a[j]="+a[j]);
            System.out.println("i="+i+",a[i]="+a[i]);
            if(a[j] < pivot){
                if(i == j){
                    ++i;
                }else{
                    int temp = a[i];
                    a[i++] = a[j];
                    a[j] = temp;
                }
            }
        }
        int tmp = a[i];
        a[i] = a[r];
        a[r] = tmp;
        System.out.println("i="+i);
        String str ="";
        for (int j = 0; j < a.length; j++) {
            str+=a[j];
        }
        System.out.println(str);
        return i;
    }
}

原文链接:https://www.cnblogs.com/pipicai96/p/11407579.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:《Java 8 in Action》Chapter 3:Lambda表达式

下一篇:JDK1.6 对 synchronized 的锁优化