public class SortDemo {
    public static void main(String[] args) {
     RandomArrays numbers = new RandomArrays(10);
     int [] arrays  = numbers.arrays;
     printArrays(arrays);
     long a = System.currentTimeMillis();
     //selectionSort(arrays);
    // bubbleSort(arrays);
    mergeSort(arrays);
     //insertionSort(arrays);
     long time = System.currentTimeMillis() - a;
     System.out.println();
     printArrays(arrays);
     System.out.println("");
     System.out.println(time);
    }

    /**
    * 冒泡排序
     *复杂度0（n^2）
     *
     *
     * */
  static void bubbleSort(int[] numbers){
      boolean needNextPass = true; //是否已经排序完成
      for (int i = 0; i <numbers.length-1&&needNextPass; i++) {
          needNextPass =  false;
          for (int j = i+1; j <numbers.length ; j++) {

                if(numbers[i]>numbers[j]){
                    swap(numbers,i,j);
                    needNextPass = true;
                }
          }

      }
  }



    /**
     *@param numbers 待排序数组
     *  TODO: 2018-7-17
     * authors zhuwanqi
     * 选择排序 每次排序将剩余待排数组的最小值放到第一个位置
     * 优化后 每次排序将最大值放入最后一个位置
     * 复杂度0(n^2)
     */

        static  void  selectionSort(int[] numbers){
            int minindex ; //目前最小值的位置
            int tempmin;//目前最小值
            int tempmax ;//目前最大值
            int maxindex;//目前最大值所在位置
            for (int i = 0; i <numbers.length/2; i++) {
                minindex = i;
                tempmin = numbers[i];
                tempmax = numbers[numbers.length-i-1];
                maxindex = numbers.length-i-1;
                for (int j = i+1; j < numbers.length-i; j++) {
                    if(tempmin>numbers[j]){
                        tempmin = numbers[j];
                        minindex = j ;
                    }
                    if(tempmax<numbers[numbers.length-j]){
                        tempmax = numbers[numbers.length-j];
                        maxindex = numbers.length-j;
                    }
                }
                swap(numbers,i,minindex);
                swap(numbers,(numbers.length-i-1),maxindex);
            }


    }

    /**
     * 插入排序
     * 将值插入到已经排好顺序的数组中。
     * 复杂度O（n^2）
     * */
    static  void insertionSort(int[] numbers){
        for (int i = 0; i <numbers.length ; i++) {
            int currentElement = numbers[i];
            int j;
            for ( j = i-1; j >=0&& numbers[j]>currentElement ; j--) {
                numbers[j+1]=numbers[j];
            }
            numbers[j+1]  = currentElement;
        }
    }

    /**
     * 归并排序
     * 将数组分为两半分别排序 再合到一起
     *
     * */
    static  void  mergeSort(int[] numbers){
        if(numbers.length>1){
            int[] firstHalf = new int[numbers.length/2];
            System.arraycopy(numbers,0,firstHalf,0,numbers.length/2);
            mergeSort(firstHalf);
            //对第二部分排序
            int secondHalfLength = numbers.length-numbers.length/2;
            int[] secondHalf = new int[secondHalfLength];
            System.arraycopy(numbers,numbers.length/2,secondHalf,0,secondHalfLength);
            mergeSort(secondHalf);
            merge(firstHalf,secondHalf,numbers);


        }

    }
    static  void merge(int[] list1,int[] list2 , int[]  temp){
        int current1 = 0 ; // list1中的位置
        int current2 = 0 ; // list2 中的位置;
        int current3 = 0 ; // list3 中的位置
        while (current1<list1.length&&current2<list2.length){
            if(list1[current1]<list2[current2]){
                temp[current3++] = list1[current1++];
            }else{
                temp[current3++]= list2[current2++];
            }
        }
        while (current1<list1.length){
            temp[current3++]=list1[current1++];
        }
        while (current2<list2.length){
            temp[current3++] = list2[current2++];
        }

    }

    /**
     * 快速排序
     * 选择一个主元 使得第一部分的元素都小于这个元素，后一部分都大于这个元素
     * 再递归地对着2部分进行快速排序
     *
     * */
    static void  quickSort(int[] numbers){


    }
    static  void quickSort(int[] numbers,int first,int last){
        if(last>first){
            int pivotIndex = partition(numbers,first,last);
            quickSort(numbers,first,pivotIndex-1);
            quickSort(numbers,pivotIndex+1,last);
        }
    }
    //找到主元应该在的位置，使得数组左边都比主元小，右边都比主元大。
    static  int partition(int[]numbers,int first,int last){
        //第一个元素的值作为中间点
        int pivot = numbers[first];
        int low = first + 1 ;
        int high = last;
        while(high > low){
            while(low<=high&&numbers[low]<=pivot){
                low++;
            }
            while(low<=high&&numbers[high]>pivot){
                high -- ;
            }
            if(high>low){
                swap(numbers,numbers[high],numbers[low]);
            }
        }

        while(high>first&&numbers[high]>=pivot){
            high -- ;
        }
        if(pivot>numbers[high]){
            numbers[first] =numbers[high];
            numbers[high]=pivot;
            return high;
        }else{
            return  first;
        }


    }



    //交换2个值
    static void swap( int[] e, int a ,int b){
        int temp ;
        temp = e[a];
        e[a] =e[b];
        e[b] = temp;

    }
    //打印数组的值
    static  void printArrays(int[] n){
        for (int i = 0; i <n.length ; i++) {
            System.out.print(n[i]+" ");
        }
    }

}