常見的排序演算法和二分法查找演算法

【排序演算法】

一、冒泡排序

每次對相鄰的兩個元素進行比較，若前者大于后者則進行交換，如此一輪下來最后一輪的就是最大元素，接著進行下一輪的比較，

需要注意的是下一輪的比較要將上一輪確定的最大的那個元素除外，重復以上的步驟，直到沒有要比較的元素，

二、選擇排序

選擇排序(Selection sort)的作業原理是:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再從剩余未排序元素中繼續尋找最小(大)元素,

然后放到已排序序列的末尾，以此類推,直到所有元素均排序完畢，

三、代碼實作

package Test;

public class Sort {
    public static void main(String[] args) {
        traversal(bubble_Sort(create_int_arr(2,5)));
        traversal(selection_Sort(create_int_arr(3,7)));
    }

    public static void traversal(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            if (i == 0) {
                System.out.print("{ " + arr[i]+", ");
            }else if (i == arr.length-1) {
                System.out.println( arr[i]+" }");
            }else {
                System.out.print(arr[i]+", ");
            }
        }
    }

    /**
     * 冒泡排序
     * @param arr 傳入陣列作為引數
     * @return 回傳排好序的陣列
     */
    public static int[] bubble_Sort(int[] arr){
        //外層for用來控制排序的趟數
        for (int i = arr.length-1; i>=0; i--) {
            int tmp;
            //內層for回圈用來控制每趟排序的次數
            for (int j = 0; j < i; j++) {
                if (arr[j]>arr[j+1]) {
                   tmp = arr[j];
                   arr[j] = arr[j+1];
                   arr[j+1] = tmp;
                }
            }
        }
        return arr;
    }

    /**
     * 選擇排序
     * @param arr 傳入一個陣列
     * @return 回傳排好序的陣列
     */
    public static int[] selection_Sort(int[] arr){
        //外層for用來控制排序的趟數
        for (int i = 0 ; i < arr.length - 1; i++) {
            //內層for回圈用來控制每趟排序的次數
            for (int j = i; j < arr.length -1; j++) {
                if(arr[j+1] < arr[i]){
                    int tmp = arr[i];
                    arr[i] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
        }
        return arr;
    }

    public static int[] create_int_arr(int digit,int len){
        int[] arr =  new int[len];
        switch (digit){
            case 1:
                for (int i = 0; i < len ; i++) {
                    arr[i] = (int)(10*Math.random()+1);
                }
                break;
            case 2:
                for (int i = 0; i < len ; i++) {
                    arr[i] = (int)(100*Math.random()+1);
                }
                break;
            case 3:
                for (int i = 0; i < len ; i++) {
                    arr[i] = (int)(1000*Math.random()+1);
                }
                break;
            case 4:
                for (int i = 0; i < len ; i++) {
                    arr[i] = (int)(10000*Math.random()+1);
                }
                break;
        }
        return arr;
    }
}

【查找演算法】

一、二分法查找原理

1、二分法查找的前提條件：
該陣列必須是已經排好序的陣列（有序陣列）
2、二分法查找的原理：
二分法查找演算法又叫折半查找演算法，在一個有序的序列中，根據要查找的目標資料和序列的中間位置上的元素
進行大小比較，比較的結果有三種情況：
1）目標資料 = 中間位置上元素的值，即找到目標元素所在的位置
2）目標資料 > 中間位置上元素的值, 在中間位置的右側查找
3)目標資料 < 中間位置上元素的值, 在中間位置的左側查找
回圈 2）和 3）直到 1）出現
二、二分法查找代碼實作

package Test;

public class BinarySearch {
    public static void main(String[] args) {
        //traversal(create_int_arr((int)(5*Math.random()+1),4));
        //traversal(create_int_arr(3,8));
        int[] arr1 = {13,916,178,861,773,829,92,323};
        int[] arr = selection_Sort(arr1);
        int index = binarySeach(arr,773);
        System.out.println((index == -1)?("要查找的元素不存在"):("要查找的元素的下標為："+index));
    }

    /**
     * 該方法實作有序陣列的二分法查找
     * @param arr 該引數代表傳入的是一個int型別的陣列
     * @param dest_ele 該引數為要查找的目標元素
     * @return 方法的回傳值為-1時，表示沒找到目標元素；回傳值為其他時，表示回傳了目標元素的下標
     */
    public static int binarySeach(int[] arr,int dest_ele){
        int begin_index = 0;
        int end_index = arr.length -1;
        //只要開始元素的下標在結束元素的左邊，就一直回圈
        while(begin_index <= end_index){
            //中間元素下標
            int mid_index = (begin_index + end_index)/2;
            //目標元素剛好在中間位置上
            if (arr[mid_index] == dest_ele) {
                System.out.println("元素："+dest_ele+"的下標為："+mid_index);
                return mid_index;
            //目標元素在中間位置的右側
            }else if(arr[mid_index]<dest_ele){
                begin_index = mid_index + 1;
            //目標元素在中間位置的左側
            }else{
                end_index = mid_index -1;
            }
        }
        return -1;
    }

    public static int[] create_int_arr(int digit,int len){
        int[] arr =  new int[len];
        switch (digit){
            case 1:
                for (int i = 0; i < len ; i++) {
                    arr[i] = (int)(10*Math.random()+1);
                }
                break;
            case 2:
                for (int i = 0; i < len ; i++) {
                    arr[i] = (int)(100*Math.random()+1);
                }
                break;
            case 3:
                for (int i = 0; i < len ; i++) {
                    arr[i] = (int)(1000*Math.random()+1);
                }
                break;
            case 4:
                for (int i = 0; i < len ; i++) {
                    arr[i] = (int)(10000*Math.random()+1);
                }
                break;
        }
        return arr;
    }

    public static int[] selection_Sort(int[] arr){
        //外層for用來控制排序的趟數
        for (int i = 0 ; i < arr.length - 1; i++) {
            //內層for回圈用來控制每趟排序的次數
            for (int j = i; j < arr.length -1; j++) {
                if(arr[j+1] < arr[i]){
                    int tmp = arr[i];
                    arr[i] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
        }
        return arr;
    }

    public static void traversal(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            if (i == 0) {
                System.out.print("{ " + arr[i]+", ");
            }else if (i == arr.length-1) {
                System.out.println( arr[i]+" }");
            }else {
                System.out.print(arr[i]+", ");
            }
        }
    }
}