常見的排序算法有哪些

本篇內容介紹了“常見的排序算法有哪些”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

冒泡排序

最常見的排序算法之一，每次比較相鄰的兩個元素，如果需要的話則交換位置。

看下面的動圖一目了然。

代碼實現：

    public static int[] sort(int[] arr){
        if (arr.length < 2){
            return arr;
        }
        //定義一個標志位，主要考慮到已經排好序的數組，避免不必要的計算
        boolean flag;
        for(int i=1;i<arr.length;i++){
            flag = true;
            for(int j=0;j<arr.length-i;j++){
                if (arr[j] > arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    flag = false;
                }
            }
            if (flag){
                break;
            }
        }
        return arr;
    }

性能分析：

• 時間復雜度：O(n2)

• 空間復雜度：O(1)

• 算法穩定性：元素相等不會交換，是穩定的排序算法

選擇排序

選擇排序，每次循環需要找出數組中最小的元素，放在數組的最前面。

動畫：

代碼實現：

    public static int[] sort(int[] arr) {
        if (arr.length < 2) {
            return arr;
        }
        int minIndex;
        for (int i = 0; i < arr.length - 1; i++) {
            minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            if (i != minIndex) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }
        return arr;
    }

性能分析：

• 時間復雜度：O(n2)

• 空間復雜度：O(1)

插入排序

它的工作原理是通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。

動畫：

代碼實現：

    public static int[] sort(int[] arr) {
        if (arr.length < 2) {
            return arr;
        }
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j = i;
            for (; j > 0; j--) {
                if (temp < arr[j - 1]) {
                    //符合條件往后挪
                    arr[j] = arr[j - 1];
                } else {
                    //此處break不能省略，用來停止 j 的自減
                    break;
                }
            }
            arr[j] = temp;
        }
        return arr;
    }

上面這種寫法容易直觀也容易理解；如果你能理解上面的寫法，那么可以進一步把if判斷表達式進行提取：

    public static int[] sort1(int[] arr) {
        if (arr.length < 2) {
            return arr;
        }
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j = i;
            for (; j > 0 && temp < arr[j - 1]; j--) {
                //符合條件往后挪
                arr[j] = arr[j - 1];
            }
            arr[j] = temp;
        }
        return arr;
    }

“常見的排序算法有哪些”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！