简单排序

• 选择排序
  1、选择排序的思想
  选择整个数组中最小的元素和第一个位置交换，然后在剩下的元素中选择最小的元素和第二个位置交换，以此类推
  2、复杂度 n^2
• 插入排序
  1、插入排序的思想
  2、复杂度 n^2
  当前索引（哨兵）左边的元素都是有序的，但是他们最终位置还不确定，为了给更小的元素腾出空间，他们可能会被移动
• 希尔排序
  1、希尔排序的思想
  使数组中任意间隔为h的数组都是有序的
  2、希尔排序为什么快？
  他权衡了子数组的规模和有序性
  3、希尔排序的复杂度
  小于n^2
• 归并排序
  1、归并排序的思想
  将数组递归不断的分成两半，分别排序，再把最后的结果合并起来，是一种分治的思想
  2、复杂度： 线性对数
  3、缺点：需要额外的空间，额外的空间和数组长度成正比
• 快排
• 三分向快排

package com.javalearn.suanfa;

import java.util.Arrays;

/**
 * Created by buguniao on 16/2/21.
 */
public class QuickSort extends SuanFaTemplate {
    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        double[] arr = quickSort.getRandomArray(100000);
        long time = quickSort.run(arr);
        System.out.println("time cost : " + time);
//        System.out.println(Arrays.toString(arr));
    }

    @Override
    public long run(double[] arr) {
        long t1= System.currentTimeMillis();
        sort(arr,0,arr.length-1);
        long t2=System.currentTimeMillis();
        return t2-t1;
    }

    public void sort(double[] arr,int lo,int hi){
        if(lo>hi){
            return;
        }
        double v= arr[lo];
        int i=lo;
        int j=hi;

        while(i!=j){
            while(i<j && arr[j]>=v){
                j--;
            }
            while(i<j && arr[i]<=v){
                i++;
            }
            if(i<j){
                exchange(arr,i,j);
            }
        }
        double t = arr[i];
        arr[i]=v;
        arr[lo]=t;

        sort(arr,lo,i-1);
        sort(arr,i+1,hi);
    }
}

package com.javalearn.suanfa;

/**
 * Created by buguniao on 16/2/21.
 */
public class QuickSort3Way extends SuanFaTemplate {
    public static void main(String[] args) {
        QuickSort3Way quickSort = new QuickSort3Way();
        double[] arr = quickSort.getRandomArray(1000000000);
        long time = quickSort.run(arr);
        System.out.println("time cost : " + time);
    }

    @Override
    public long run(double[] arr) {
        long t1=System.currentTimeMillis();
        sort(arr,0,arr.length-1);
        long t2=System.currentTimeMillis();
        return t2-t1;
    }
    public void sort(double[] arr,int lo,int hi){
        if(lo>=hi){
            return;
        }
        int lt=lo;
        int gt=hi;
        int i=lo+1;

        double v = arr[lo];

        while(i<=gt){
            if(arr[i]>v){
                exchange(arr,i,gt--);
            }else if(arr[i]<v){
                exchange(arr,lt++,i++);
            }else{
                i++;
            }
        }
        sort(arr,lo,lt-1);
        sort(arr,gt+1,hi);
    }
}