package com.firewolf.sort;

public class MySort {

 /**
  * @param args
  */
 public static void main(String[] args) {
  int array[] = {45,32,54,12,43,65,11,3,43,6,33,90,44,1,178};
  MySort mySort = new MySort();
  mySort.insertSort(array);
  System.out.print("插入排序結果 ：  ");
  mySort.printArray(array);
  System.out.println();
  mySort.bubbleSort(array);
  System.out.print("冒泡排序結果 ：  ");
  mySort.printArray(array);
  mySort.qsort(array);
  System.out.println();
  System.out.print("快速排序結果 ：  ");
  mySort.printArray(array);
  mySort.shellSort(array);
  System.out.println();
  System.out.print("希爾排序結果 ：  ");
  mySort.printArray(array);
  mySort.selectSort(array);
  System.out.println();
  System.out.print("選擇排序結果 ：  ");
  mySort.printArray(array);
 }

 /**
  * 直接插入排序
  * 基本思想：在要排序的一組數中，假設前面(n-1)[n>=2] 個數已經是排好順序的，現在要把第n個數插到前面的有序數中，使得這n個數也是排好順序的。如此反復循環，直到全部排好順序
  */
 public void insertSort(int[] array){
  int temp=0; 
     for(int i=1;i<array.length;i++){ 
        int j=i-1; 
        temp=array[i]; 
        for(;j>=0&&temp<array[j];j--){ 
         array[j+1]=array[j];                       //將大于temp的值整體后移一個單位 
        } 
        array[j+1]=temp; 
     }
 }

 /**
  * 冒泡排序
  * 基本思想：在要排序的一組數中，對當前還未排好序的范圍內的全部數，自上而下對相鄰的兩個數依次進行比較和調整，讓較大的數往下沉，較小的往上冒。即：每當兩相鄰的數比較后發現它們的排序與排序要求相反時，就將它們互換。
  */
 public void bubbleSort(int[] array) {
     int temp;
     for(int i=0;i<array.length;i++){//趟數
       for(int j=0;j<array.length-i-1;j++){//比較次數
         if(array[j]>array[j+1]){
           temp=array[j];
           array[j]=array[j+1];
           array[j+1]=temp;
         }
       }
     }
    }

 /**
  * 快速排序
  * 基本思想：選擇一個基準元素,通常選擇第一個元素或者最后一個元素,通過一趟掃描，將待排序列分成兩部分,一部分比基準元素小,一部分大于等于基準元素,此時基準元素在其排好序后的正確位置,然后再用同樣的方法遞歸地排序劃分的兩部分。
  * @param array
  */
 public void qsort(int array[]){
  if(array.length>1){
   _qsort(array,0,array.length-1);
  }
 }
 /**
  * 一趟快速排序
  * @param array
  */
 private void _qsort(int[] array,int low,int high){
  if(low < high){
   int middle = getMiddle(array, low, high);
   _qsort(array,low,middle-1);
   _qsort(array, middle+1, high);
  }
 }
 /**
  * 得到中間值
  */
 private int getMiddle(int[] array,int low,int high){
  int tmp = array[low];
  while(low < high){
   while(low < high && array[high] >= tmp)
    high--;
   array[low] = array[high];
   while(low<high && array[low]<=tmp)
    low++;
   array[high] = array[low];
  }
  array[low] = tmp;
  return low;
 }

 /**
  * 簡單選擇排序
  * 基本思想：在要排序的一組數中，選出最小的一個數與第一個位置的數交換；然后在剩下的數當中再找最小的與第二個位置的數交換，如此循環到倒數第二個數和最后一個數比較為止。
  * @param array
  */
 public void selectSort(int[] array){
  int position=0; 
        for(int i=0;i<array.length;i++){ 

            int j=i+1; 
            position=i; 
            int temp=array[i]; 
            for(;j<array.length;j++){ 
            if(array[j]<temp){ 
                temp=array[j]; 
                position=j; 
            } 
            } 
            array[position]=array[i]; 
            array[i]=temp; 
        }
 }

 /**
  * 希爾排序（最小增量排序）
  * 基本思想：算法先將要排序的一組數按某個增量d（n/2,n為要排序數的個數）分成若干組，每組中記錄的下標相差d.對每組中全部元素進行直接插入排序，然后再用一個較小的增量（d/2）對它進行分組，在每組中再進行直接插入排序。當增量減到1時，進行直接插入排序后，排序完成。
  * @param array
  */
 public  void shellSort(int[] array){ 
     double d1=array.length; 
     int temp=0; 
     while(true){ 
         d1= Math.ceil(d1/2); 
         int d=(int) d1; 
         for(int x=0;x<d;x++){ 
             for(int i=x+d;i<array.length;i+=d){ 
                 int j=i-d; 
                 temp=array[i]; 
                 for(;j>=0&&temp<array[j];j-=d){ 
                  array[j+d]=array[j]; 
                 } 
                 array[j+d]=temp; 
             } 
         } 
         if(d==1) 
             break; 
     } 
 } 

 /**
  * 打印數組中的所有元素
  */

 public void printArray(int[] array){
  for (int i = 0; i < array.length; i++) {
   System.out.print(array[i]+" ");
  }
 }
}

import java.util.Arrays;
public class Test2{
        public static void main(String[] args){
                int[] a={5,4,2,4,9,1};
                Arrays.sort(a);  //進行排序
                for(int i: a){
                        System.out.print(i);
                }
        }
}

public static int[] bubbleSort(int[] args){//冒泡排序算法
                for(int i=0;i<args.length-1;i++){
                        for(int j=i+1;j<args.length;j++){
                                if (args[i]>args[j]){
                                        int temp=args[i];
                                        args[i]=args[j];
                                        args[j]=temp;
                                }
                        }
                }
                return args;
        }

public static int[] selectSort(int[] args){//選擇排序算法
                for (int i=0;i<args.length-1 ;i++ ){
                        int min=i;
                        for (int j=i+1;j<args.length ;j++ ){
                                if (args[min]>args[j]){
                                        min=j;
                                }
                        }
                        if (min!=i){
                        int temp=args[i];
                        args[i]=args[min];
                        args[min]=temp;       
                        }
                }
                return args;
        }

public static int[] insertSort(int[] args){//插入排序算法
                for(int i=1;i<args.length;i++){
                        for(int j=i;j>0;j--){
                                if (args[j]<args[j-1]){
                                        int temp=args[j-1];
                                        args[j-1]=args[j];
                                        args[j]=temp;       
                                }else break;
                        }
                }
                return args;
        }