Java如何實現冒泡、選擇、插入、希爾、歸并排序算法

這篇文章給大家分享的是有關Java如何實現冒泡、選擇、插入、希爾、歸并排序算法的內容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。

簡單的排序

常見的時間復雜度

???? 常數階Ο(1)

???? 對數階Ο(log2n)

???? 線性階Ο(n)

???? 線性對數階Ο(nlog2n)

???? 平方階Ο(n²)

???? 立方階Ο(n³)

???? K次方階Ο(n^k)

???? 指數階Ο(2^n)

常見的時間復雜度對應圖

&Omicron;(1)＜&Omicron;(log2n)＜&Omicron;(n)＜&Omicron;(nlog2n)＜&Omicron;(n&sup2;)＜&Omicron;(n&sup3;)＜&hellip;＜&Omicron;(2^n) ＜&Omicron;(n!)<O(n^n)

冒泡排序（Quicksort）

算法描述：

①. 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。

②. 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。這步做完后，最后的元素會是最大的數。

③. 針對所有的元素重復以上的步驟，除了最后一個。

④. 持續(xù)每次對越來越少的元素重復上面的步驟①~③，直到沒有任何一對數字需要比較。

為了直觀感受，在網上找個動態(tài)的演示

代碼實現：

當數組中有n個元素時，只需要進行n-1輪比較，則整個數組就是有序的
public static void bubbleSort(int[] arr) {
 // 進行i輪比較
    for (int i = 0; i < arr.length - 1; i++)
     {
        for (int j = 0; j < arr.length - 1 - i; j++) {
        //后一位的值大于前一位的值進行值交換
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
            }
        }
    }
}

public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

選擇排序（Quicksort）

算法描述：

選擇排序是一種簡單直觀的排序算法。它的工作原理是：第一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最?。ù螅┰兀^續(xù)放在起始位置知道未排序元素個數為0。

代碼實現：

public static void selectionSort(int[] a) {
//每當完成一輪，將會找到最小值，一個i代表一輪
    for (int i = 0; i < a.length; i++) {
        int index = i;
        //每一輪從i+1開始找，查找是否有比當前值更小的值
        for (int j = i + 1; j < a.length; j++) {
            if (a[index] > a[j]) {
                index = j;
            }
        }//如果index和i不相等說明，下標交換過，也就是說找到更小的數值了
        if (index != i) {
            swap(a, index, i);
        }
    }
}

public static void swap(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

插入排序（insertSort）

算法描述：

插入排序也是一種常見的排序算法，插入排序的思想是：將初始數據分為有序部分和無序部分，每一步將一個無序部分的數據插入到前面已經排好序的有序部分中，直到插完所有元素為止。 插入排序的步驟如下：每次從無序部分中取出一個元素，與有序部分中的元素從后向前依次進行比較，并找到合適的位置，將該元素插到有序組當中。 將數組分為2端，有序數組和無序數組，依次將無序數組中的值插入到無序數組中。

如圖，插入4的過程如下 將數組分為2端，有序數組和無序數組，依次將無序數組中的值插入到無序數組中。

如下圖3 6 7為有序數組，4 2為無序數組。依次將4，2插入到無序數組中即可

如圖，插入4的過程如下

代碼實現：

public static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int temp = a[i];
        int j;
        // 查到合適的插入位置，插入即可
        for (j = i - 1; j >= 0 && a[j] > temp; j--) {
            a[j + 1] = a[j];
        }
        a[j + 1] = temp;
    }
}

希爾排序 （ShellSort）

算法描述：

希爾排序是基于插入排序改進后的算法。因為當數據移動次數太多時會導致效率低下。所以我們可以先讓數組整體有序（剛開始移動的幅度大一點，后面再小一點），這樣移動的次數就會降低，進而提高效率

代碼實現：

public static void shellSort(int[] a) {
    for (int step = a.length / 2; step > 0; step /= 2) {
    //接下來的過程類似于插入排序
        for (int i = step; i < a.length; i++) {
            int temp = a[i];
            int j;
            for (j = i - step; j >= 0 && a[j] > temp ; j -= step) {
                a[j + step] = a[j];
            }
            a[j + step] = temp;
        }
    }
}

歸并排序（MergetSort）

算法描述：

1.申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列；

2.設定兩個指針，最初位置分別為兩個已經排序序列的起始位置；

3.比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置；

4.重復步驟 3 直到某一指針達到序列尾；

將另一序列剩下的所有元素直接復制到合并序列尾。

方便理解，直接網上找圖

代碼實現：

public static void mergeSort(int[] a, int left, int right) {
    // 將數組分段成只有一個元素
    if (left == right) {
        return;
    }
    int mid = (left + right) / 2;
    mergeSort(a, left, mid);//遞歸
    mergeSort(a, mid + 1, right);
    merge(a, left, mid, right);
}

public static void merge(int[] a, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= right) {
        if (a[i] < a[j]) {
            temp[k++] = a[i++];
        } else {
            temp[k++] = a[j++];
        }
    }
    // 復制左邊數組剩余的值
    while (i <= mid) {
        temp[k++] = a[i++];
    }
    // 復制右邊數組剩余的值
    while (j <= right) {
        temp[k++] = a[j++];
    }
    int index = 0;
    //把temp全部復制給數組
    while (left <= right) {
        a[left++] = temp[index++];
    }
}

快速排序（QuickSort）

算法描述：

• 快速排序的執(zhí)行流程主要分為如下三步

• 從數列中取出一個數作為基準數

• 分區(qū)，將比它大的數全放到它的右邊，小于或等于它的數全放到它的左邊

• 再對左右區(qū)間重復第二步，直到各區(qū)間只有一個數

代碼實現：

public static void quickSort(int[] a, int left, int right) {
    if (left >= right) {
        return;
    }
    int index = sort(a, left, right);
    //得到中間值index，然后一分為二，繼續(xù)分
    quickSort(a, left, index - 1);
    quickSort(a, index + 1, right);
}

public static int sort(int[] a, int left, int right) {
//以左邊的a[left]為基準數
    int key = a[left];
    while (left < right) {
        // 從right所指位置向前搜索找到第一個關鍵字小于key的記錄和key互相交換
        while (left < right && a[right] >= key) {
            right--;
        }
        a[left] = a[right];
        // 從left所指位置向后搜索，找到第一個關鍵字大于key的記錄和key互相交換
        while (left < right && a[left] <= key) {
            left++;
        }
        a[right] = a[left];
    }
    // 放key值，此時left和right相同
    a[left] = key;
    return left;
}

感謝各位的閱讀！關于“Java如何實現冒泡、選擇、插入、希爾、歸并排序算法”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！