數組演算法

• 2020 年 12 月 1 日
• 筆記

冒泡演算法

原理：

通過數組相鄰兩個數比較大小，得到左小右大的排序。循環以上操作，將獲得一個數組的最大數，並在數組最大索引處。

因為已經獲得了最大數，下次循環次數-1，以此類推直至排序完。

程式碼實現：

private static void bubleSort(int[] arr) {
        int js=arr.length-1;
        int tmp;
        for (int i = 0; i < js; i++) {
            for (int j = 0; j < js; j++) {
                if(arr[j]>arr[j+1]){
                    tmp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=tmp;
                }
            }
            js--;
        }
    }

二分法查找

目的：在數組中查找一個數字的索引。

使用要求：基於排序，按照大到小，或小到大都可以。

原理：

獲取數組中間索引的數組值，然後與要查找的數字進行比較，只有三種結果>、=、<,進行不同的判斷返回結果

程式碼實現：

private static int binarySearch(int[] arr, int num) {
        int max=arr.length;
        int min=0;
        int tmp = 0;
        if(max<min){
            return -1;
        }
        for (int i = 0; i < arr.length; i++) {
            tmp=(max+min)/2;
            if(arr[tmp]>num)
                max=tmp;
            else if(arr[tmp]<num)
                min=tmp;
            else
                return tmp;
        }
        return tmp;
    }

快排法

目的：在數組中，規則排序。

原理：

1. 將數組一號元素定位基準
2. 從最後一位元素開始於第一位元素盡心大小比較，查找比標準小的元素，找到一個後停止尋找。
3. 從第二位元素開始尋找比基準大的元素，找到一個後停止尋找，再將第二步找到的元素與這個元素位置交換。
4. 重複第二步和三步操作，直至兩者索引相同。

此時獲得的數組，相同的索引左邊都比中間索引的值小，索引右邊都比中間索引的值大。可通過遞歸實現後面數據排序操作。中間索引左邊的數據再次重複1234補，數組右邊同理。

程式碼實現：

private static void quickSort(int[] arr, int left, int right) {
        if(left>right){
            return;
        }
        int start=left;
        int end=right;
        int jl=arr[start];
        while(left!=right){
            while (arr[right]>=jl&&right>left){
                right--;
            }
            while(arr[left]<=jl&&right>left){
                left++;
            }
            int tmp=arr[left];
            arr[left]=arr[right];
            arr[right]=tmp;
        }
        arr[start]=arr[right];
        arr[right]=jl;


        quickSort(arr,start,left-1);
        quickSort(arr,left+1,end);
    }

謝謝觀看，如發現錯誤優化，請指正謝謝，祝您學有所成。