Java常用排序算法/程序員必須掌握的 8大排序算法

自定義方法實現(xiàn)冒泡排序算法

//冒泡排序
    public static void bubble(int[] arr){
        //1.使用外層循環(huán)控制比較的輪數(shù)
        for(int i = 1; i < arr.length; i++){
            //使用變量作為當前輪是否發(fā)生交換的標志
            boolean flag = true;
            //2.使用內(nèi)層循環(huán)控制比較的元素下標范圍
            for(int j = 0; j < arr.length-i; j++){
                //3.如果左邊元素大，則交換
                if(arr[j] > arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    flag = false;
                }
            }
            //到這個位置flag還是true，證明當前輪沒有發(fā)生任何的交換
            if(flag){
                break;
            }
        }
    }

插入排序

public static void insert(int[] arr){
        //1.使用外層循環(huán)負責一個個取出元素
        for(int i = 1; i < arr.length; i++){
            //2.單獨保存每一次取出的元素，防止被覆蓋
            int temp = arr[i];
            //3.使用內(nèi)層循環(huán)負責讓取出的元素與左邊的元素一個個比較，
            //如果左邊有元素并且大于取出的元素則左邊元素右移
            int j = 0;
            for(j = i; j >= 1 && arr[j-1] > temp; j-- ){
                arr[j] = arr[j-1];
            }
            //4.直到左邊元素不再大于取出的元素，則將取出的元素插入到左邊元素
            //  的右邊
            // 避免自己給自己賦值
            if(j != i){
                arr[j] = temp;
            }
        }
    }

選擇排序

public static void choose(int[] arr){
        //1.使用外層循環(huán)負責將元素一個個取出來
        for(int i = 0; i < arr.length - 1; i++){
            //2.假定取出的元素是最小值，使用min記錄下標
            int min = i;
            //3.使用內(nèi)層循環(huán)讓min記錄的元素與后續(xù)元素依次比較，
            //  如果后續(xù)元素中有比min記錄的元素還小的元素，則重新記錄該元素下標
            for(int j = i+1; j < arr.length; j++){
                if(arr[j] < arr[min]){
                    min = j;
                }
            }
            //4.直到min記錄的元素與后續(xù)所有元素比較完畢，此時交換min記錄的元素
            //  和最開始假定的元素
            if(min != i){
                int temp = arr[min];
                arr[min] = arr[i];
                arr[i] = temp;
            }
        }
    }

快速排序

//自定義方法實現(xiàn)快速排序算法
    public static void quick(int[] arr, int left, int right) {
        //1.計算中間元素的下標作為基準值，并單獨保存起來
        //2.分別讓左右兩邊的元素依次和基準值進行比較
        //2.1 將所有比基準值小的元素放在基準值的左邊
        //2.2 將所有比基準值大的元素放在基準值的右邊，相等的任意一遍
        //3.直到三個坐標重合時將基準值放在重合的位置上
        //4.分別對左右兩邊的分組進行再次分組，使用遞歸

        if (left < right) {
            //Swap(s[l], s[(l + r) / 2]); //將中間的這個數(shù)和第一個數(shù)交換 參見注1
            int i = left, j = right, x = arr[left];
            while (i < j) {
                while (i < j && arr[j] >= x) // 從右向左找第一個小于x的數(shù)
                    j--;
                if (i < j)
                    arr[i++] = arr[j];

                while (i < j && arr[i] < x) // 從左向右找第一個大于等于x的數(shù)
                    i++;
                if (i < j)
                    arr[j--] = arr[i];
            }
            arr[i] = x;
            quick(arr, left, i - 1); // 遞歸調(diào)用
            quick(arr, i + 1, right);
        }
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] arr = {20, 8, 18, 5, 15, 30, 10, 25, 8};
        TestSort.quick(arr,0,arr.length-1);
        //打印最終的排序結(jié)果
        System.out.print("排序后的結(jié)果是：");
        for(int i = 0; i < arr.length; i++){
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

二分查找算法

//自定義一個方法實現(xiàn)二分查找算法
    public static int findBinary(int[] arr, int left, int right, int data){
        if(left <= right){
        
            //1.計算并找出中間元素
            int p = (left + right) / 2;
            //2.如果目標元素與中間元素相等，則返回對應下標
            if(data == arr[p]){
                return p;
            }
            //3.如果目標元素小于中間元素，則去左邊查找，重復以上過程，使用遞歸
            else if(data < arr[p]){
                return findBinary(arr, left, p-1, data);
            }
            //4.如果目標元素大于中間元素，則去右邊查找，重復以上過程，使用遞歸
            else{
                return findBinary(arr, p+1, right, data);
            }
        }
        
        return -1;
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] arr = {10,20,30,40,50,60,70,80,90};
        int res = TestFind.findBinary(arr, 0, arr.length-1, 100);
        System.out.println("該元素的下標是：" + res);
        
    }