排序算法

二分查找法：O(log2n)

public class demo01 {
    public static int binarySearch(int[] nums,int star,int end,int key){
        if(star > end){
            return -1000;
        }else {
            int mid = ( end + star ) / 2;
            if(nums[mid] == key){
                return mid;
            }else if(nums[mid] > key){
                return binarySearch(nums,star,mid-1,key);
            }else if(nums[mid] < key){
                return binarySearch(nums,mid+1,end,key);
            }else {
                return -1000;
            }
        }

    }
    public static void main(String[] args) {
        int[] a = {1,2,3,4,5,6,7,8,9,10};
        System.out.println(binarySearch(a,0,a.length-1,6));
    }
}

简单排序效率：冒泡 < 选择 < 插入
高级排序：
分析：用交换次数作比较，冒泡排序每一次都交换，而选择排序只记录最值，交换一次。插入排序会让数组不断接近有序，并且对基本有序的数组排序更快。
冒泡排序：时间复杂度 O(n^2)

public class Bubble {
    public static void bubbleSort(int[] nums){
        for(int i = 1 ; i < nums.length ; i++){
            int mark = 0;
            for(int j = 0 ; j < nums.length - i ; j++){
                if (nums[j] > nums[j+1]) {
                    nums[j] ^= nums[j + 1];
                    nums[j + 1] ^= nums[j];
                    nums[j] ^= nums[j + 1];
                    mark = 1;
                }
            }
            if (mark == 0) {
                return;
            }
        }
    }

    public static void main(String[] args) {
        int[] a = {21,4563,113,0,12,4,9,35,667};
        bubbleSort(a);
        for (int i = 0 ; i < a.length ; i++){
            System.out.print(a[i]+" ");
        }
    }
}

选择排序：O(n^2)

public class Select {
    public static void selectSort(int[] a){
        for(int i = 0 ; i < a.length ; i++ ){
            int max = a.length-1-i;
            for (int j = 0 ; j < a.length-1-i ;j++){
                if (a[j] > a[max]){
                    max = j;
                }
            }
            if(max!=a.length-1-i){
                a[max] ^= a[a.length-1-i];
                a[a.length-1-i] ^= a[max];
                a[max] ^= a[a.length-1-i];
            }
        }
    }


    public static void main(String[] args) {
        int a[] = {7, 6, 9, 8, 5,1};
        selectSort(a);
        for (int i = 0 ; i < a.length ; i++){
            System.out.print(a[i]+" ");
        }
    }
}

插入排序:O(n^2)

public class Insert {
    public static void insertSort(int[] nums){
        for (int i = 1 ; i < nums.length ; i++ ){
            int mark = nums[i];
            for (int j = i-1 ; j >= 0 ; j-- ){
                if( mark < nums[j] ){
                    nums[j+1] ^= nums[j];
                    nums[j] ^= nums[j+1];
                    nums[j+1] ^= nums[j];
                }
            }
        }
    }

    public static void main(String[] args) {
        int a[] = {7, 6, 9, 8, 5,1,0};
        insertSort(a);
        for (int i = 0 ; i < a.length ; i++){
            System.out.print(a[i]+" ");
        }
    }
}

快速排序：O(nlogn) ~ O(n^2)

public class Fast {
    public static void fastSort(int[] nums,int begin,int end){
        if ( begin >= end ) {
            return;
        }
        int b = begin;
        int e = end;
        int mark = nums[begin];
        while ( begin < end ){
            while ( begin < end && nums[end] > mark ){
                end--;
            }
            nums[begin] = nums[end];
            while ( begin < end && nums[begin] <= mark ){
                begin++;
            }
            nums[end] = nums[begin];
        }
        nums[begin] = mark;
        fastSort(nums,b,begin-1);
        fastSort(nums,begin+1,e);
    }

    public static void main(String[] args) {
        int a[] = {7, 6, 9, 8, 5,1};
        fastSort(a,0,a.length-1);
        for (int i = 0 ; i < a.length ; i++){
            System.out.print(a[i]+" ");
        }
    }
}

二分法排序：O(nlogn)

public class Merge {
    public static void mergeSort(int[] nums,int begin,int end){
        if( end <= begin ){
            return;
        }else {
            int mid =( begin + end ) /2;
            mergeSort(nums,begin,mid);
            mergeSort(nums,mid+1,end);
            merge(nums,begin,mid+1,end);
        }
    }

    private static void merge(int[] nums, int begin, int mid, int end) {
        int[] temp = new int[end-begin+1];
        int pos = begin,dest = mid,i=0;

        while ( pos <= end && dest <= end ){
            if( nums[pos] <= nums[dest] ){
                temp[i++] = nums[pos++];
            }else {
                temp[i++] = nums[dest++];
            }
        }
        if( pos > end ){
            System.arraycopy(nums,dest,temp,i,temp.length-i);
        }else {
            System.arraycopy(nums,pos,temp,i,temp.length-i);
        }
        System.arraycopy(temp,0,nums,begin,end-begin+1);

    }

    public static void main(String[] args) {
        int a[] = {7, 6, 9, 8, 5,1,1,2,2};
        mergeSort(a,0,a.length-1);
        for (int i = 0 ; i < a.length ; i++){
            System.out.print(a[i]+" ");
        }
    }
}