import java.util.*;

class SortUtilityTools{
    public static void main(String[] args){
        int[] arr = {3,5,13,8,4,2,1,20,19,14,17};
        SortUtilityTools.HeapSort(arr);
        for(int a:arr){
            System.out.println(a);
        }
        int a1 = SortUtilityTools.binarySearch(arr,13);
        System.out.println(a1);
    }

    //冒泡排序,從小到大
    public static int[] BubbleSort(int[] arr){
        //邊界檢查
        if(arr == null) return null;
        //BubbleSort
        int length = arr.length;
        int temp;
        for(int i = 0;i < length;++i){
            for(int j = 0;j < length-(i+1);++j){
                if(arr[j] > arr[j+1]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        
        return arr;
    }
    //選擇排序
    public static int[] SelectSort(int[] arr){
        //邊界檢查
        if(arr == null) return null;
        //SelectSort
        int length = arr.length;
        int min = Integer.MAX_VALUE;
        int temp = 0;
        int tempNum;
        for(int i = 0;i < length;++i){
            for(int j = i;j < length;++j){
                if(arr[j] < min){
                    min = arr[j];
                    temp = j;
                }
            }
            tempNum = arr[temp];
            arr[temp] = arr[i];
            arr[i] = tempNum;
            min = Integer.MAX_VALUE;
        }
        return arr;
    }
    
    //插入排序
    public static int[] InsertSort(int[] arr){
        //邊界檢查
        if(arr == null) return null;
        //InsertSort
        int length = arr.length;
        int temp;
        for(int i = 0; i < length;++i){
            for(int j = i;j > 0;j--){
                if(arr[j] < arr[j-1]){
                    temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }else if(arr[j] > arr[j-1]){
                    break;
                }
            }
        }
        return arr;
    }
    
    //歸并排序，遞歸版本,第二遍
    public static void MergeSort(int[] arr,int l,int r){
        //邊界處理
        if(arr == null) return;
        //MergeSort
        if(l < r){
            int m = (l+r) >> 1;
            MergeSort(arr,l,m);
            MergeSort(arr,m+1,r);
            Merge(arr,l,m,r);
        }
    }
    
    private static void Merge(int[] arr,int l,int m,int r){
        //L and R
        int[] L = new int[m-l+2];
        int[] R = new int[r-m+1];
        int i,j;
        for(i = 0;i < L.length-1;++i){
            L[i] = arr[l+i];
        }
        L[i] = Integer.MAX_VALUE;
        i = 0;
        for(j = 0;j < R.length-1;++j){
            R[j] = arr[m+1+j];
        }
        R[j] = Integer.MAX_VALUE;
        j = 0;
        //compare L and R
        while(l <= r){
            if(L[i] <= R[j]){
                arr[l++] = L[i++];
            }else{
                arr[l++] = R[j++];
            }
        }
    }
    
    //快速排序，第二遍
    public static void Quick(int[] arr,int l,int r){
        //邊界檢查
        if(arr == null) return;
        int x;
        if(l < r){
            x = R_Quick(arr,l,r);
            Quick(arr,l,x-1);
            Quick(arr,x+1,r);
        }
    }
    
    private static int QuickSort(int[] arr,int l,int r){
        //i and j
        int i = l - 1;
        int j;
        //pivot
        int p = arr[r];
        int temp;
        for(j = l;j < r;++j){
            if(arr[j] < p){
                i++;
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        temp = arr[i+1];
        arr[i+1] = arr[r];
        arr[r] = temp;
        return i+1;
    }
    
    
    //R-Quick
    public static int R_Quick(int[] arr,int l,int r){
        int temp;
        Random random = new Random();
        int i = random.nextInt(r-l) + l;
        temp = arr[r];
        arr[r] = arr[i];
        arr[i] = temp;
        return QuickSort(arr,l,r);
    }
    
    //建堆
    private static int BuildMaxHeap(int[] arr){
        int heapSize = arr.length;
        int length = arr.length;
        for(int i = length >> 1;i >= 0;i--){
            Max_Heapify(arr,i,heapSize);
        }
        return heapSize;
    }
    
    private static void Max_Heapify(int[] arr,int i,int heapSize){
        //判斷左右孩子是否符合最大堆性質(zhì)
        int l = (i << 1) + 1;
        int r = (i << 1) + 2;
        int largest = i;
        int temp;
        if(l < heapSize && arr[l] > arr[i]){
            largest = l;
        }
        if(r < heapSize && arr[r] > arr[largest]){
            largest = r;
        }
        if(largest != i){
            temp = arr[largest];
            arr[largest] = arr[i];
            arr[i] = temp;
            Max_Heapify(arr,largest,heapSize);
        }
    }
    //堆排序
    public static void HeapSort(int[] arr){
        if(arr == null) return;
        
        int heapSize = BuildMaxHeap(arr);
        int temp;
        while(heapSize > 1){
            temp = arr[0];
            arr[0] = arr[heapSize-1];
            arr[heapSize-1] = temp;
            heapSize--;
            Max_Heapify(arr,0,heapSize);
        }
    }
    
    
    

    //Array的二分查找,返回－1代表沒有找到　
    public static int binarySearch(int[] arr,int target){
        //邊界檢查
        if(arr == null) return -1;
        //折半查找
        int length = arr.length;
        int left = 0;
        int right = length - 1;
        int mid;
        int midNum;
        while(length >= 1 && left <= right){
            mid = (left + right) >> 1;
            midNum = arr[mid];
            if(target == midNum){
                return mid;
            }else if(target < arr[mid]){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return -1;
    }

}