package com.holly.wang.lintcode;

import java.util.Arrays;

public class SortIntegers {
     /**
      * 给一组整数，按照升序排序，使用选择排序，冒泡排序，插入排序或者任何 O(n2) 的排序算法。
     * @param A an integer array
     * @return void
     */
    public static void sortIntegers(int[] A) {
        for (int i = 0; i < A.length; i++) {
            int min = A[i];
            int temp;
            int index =i;
            for (int j = A.length-1; j > i; j--) {
                if(A[j] < min) {
                    min = A[j]; 
                    index =j;
                }
            }
            temp = A[i];
            A[i] = min;
            A[index] = temp;
        }
    }
    public static void popUpSortIntegers(int[] A) {
        for (int i = 0; i < A.length; i++) {
            int temp = 0;
            for (int j = 0; j < A.length; j++) {
                if(A[j] <A[j-1]) {
                    temp = A[j];
                    A[j] = A[j-1];
                    A[j-1] = temp;
                }
            }
        }
    }
    /**
     * 冒泡排序改进 如果已经是有序的则不再进行循环
     * @param A
     * void
     */
    public static void bubbleSortIntegers(int[] A) {
        boolean exchange;
        for (int i = 0; i < A.length; i++) {
            int temp = 0;
            exchange =false;
            for (int j= A.length-1; j>i; j--) {
                if(A[j] <A[j-1]) {
                    temp = A[j];
                    A[j] = A[j-1];
                    A[j-1] = temp;
                    exchange =true;
                }
                System.out.println(Arrays.toString(A));
            }
            if(!exchange) {
                break;
            }
        }
        System.out.println(A);
    }
    /**
     * 插入排序
     * @param a
     * void
     */
    public static void insertSort(int[] a) {  
        for(int i=1;i<a.length;i++){//从头部第一个当做已经排好序的，把后面的一个一个的插到已经排好的列表中去。  
            if(a[i]<a[i-1]){  
                int j;  
                int x=a[i];//x为待插入元素  
                a[i]=a[i-1];  
                for(j=i-1;  j>=0 && x<a[j];j--){//通过循环，逐个后移一位找到要插入的位置。  
                    a[j+1]=a[j];  
                    System.out.println(Arrays.toString(a));
                }  
                a[j+1]=x;//插入  
            }  
                  
        }  
          
    }  
    public static void insertsort2(int a[]) {  
        int i, j;  
        for (i = 1; i <a.length; i++)  
            if (a[i] < a[i - 1])  
            {  
                int temp = a[i];  
                for (j = i - 1; j >= 0 && a[j] > temp; j--)  
                    a[j + 1] = a[j];  
                a[j + 1] = temp;  
            }  
    }
    
    private void shellSort(int[] a) {  
        int dk = a.length/2;   
        while( dk >= 1  ){    
           ShellInsertSort(a, dk);    
           dk = dk/2;  
        }  
   }  
   private void ShellInsertSort(int[] a, int dk) {//类似插入排序，只是插入排序增量是1，这里增量是dk,把1换成dk就可以了  
       for(int i=dk;i<a.length;i++){  
           if(a[i]<a[i-dk]){  
               int j;  
               int x=a[i];//x为待插入元素  
               a[i]=a[i-dk];  
               for(j=i-dk;  j>=0 && x<a[j];j=j-dk){//通过循环，逐个后移一位找到要插入的位置。  
                   a[j+dk]=a[j];  
               }  
               a[j+dk]=x;//插入  
           }  
                 
       }  
         
   }  
   private static void selectSort(int[] a) {  
       for(int i=0;i<a.length;i++){  
           int k=i;//k存放最小值下标。每次循环最小值下标+1  
           for(int j=i+1;j<a.length;j++){//找到最小值下标  
               if(a[k]>a[j])  
                   k=j;  
           }  
           swap(a,k,i);//把最小值放到它该放的位置上  
       }  
   }  
 
    public static void swap(int[] data, int i, int j) {    
           if (i == j) {    
               return;    
           }    
           data[i] = data[i] + data[j];    
           data[j] = data[i] - data[j];    
           data[i] = data[i] - data[j];    
       }    
    
    public static void main(String[] args) {
        /*int[] A ={5,9,7,4,2,8,6};
        bubbleSortIntegers(A);*/
        /*int a[] = {3,1,5,7,2,4,9,6,10,8}; 
        insertSort(a);*/
//      int A []= {3,2,1,4,5};
        int A []=  {3,1,5,7,2,4,9,6,10,8};
        sortIntegers(A);
        System.out.println(Arrays.toString(A));
    }
}