Java實現八種排序算法詳細代碼舉例

更新時間：2024年10月26日 10:11:37 作者：小川_wenxun

排序問題一直是程序員工作與面試的重點,今天特意整理研究下與大家共勉!這篇文章主要介紹了Java實現八種排序算法的相關資料,文中通過代碼介紹的非常詳細,需要的朋友可以參考下

直接插入排序

思路：

以兩個for循環(huán)，來實現兩個數及兩數中小數與前面數進行比較
假設第一個數為tmp，認為第一個數已經是排好序的，然后去和后面一個數進行比較
如果 j位置的數 > j+1位置的數，把 j位置的數賦值給 j+1位置；如果否，則向 j位置的前面去做，直到 j >= 0
重復進行步驟3，直到不符合循環(huán)條件

動圖如下：

代碼：

public static void insertSort(int[] array){
    for (int i = 1; i &lt; array.length; i++) {
        int tmp = array[i];
        int j = i-1;
        for (; j &gt;= 0; j--) {
            if(array[j] &gt; tmp){
                array[j+1] = array[j];
            }else{
                array[j+1] = tmp;
                break;
            }
        }
        array[j+1] = tmp;
    }
}

時間復雜度：O(N^2)

空間復雜度：O(1)

穩(wěn)定性：穩(wěn)定

注意：

本身是一個穩(wěn)定的排序，那么可以實現為不穩(wěn)定的。但是如果一個排序本身就是不穩(wěn)定，那就不能實現穩(wěn)定的排序。
數據越有序，直接插入排序越快

希爾排序

步驟：

希爾排序算是對直接排序進行優(yōu)化，把其中的數據通過分組來不斷簡化 其中的有序性，上面有提到數據越有序，直接插入排序越快，不過這個分組并不是常規(guī)理解的那種把幾個臨近的數字化為一個組，而是，如下圖所示：

通過間隔（gap）來實現分組，以上面紫色的原圖為例，這時的gap為5，這代表著隔著5個空格的數為一組，然后進行組內排序，不斷縮小間隔，增加每組內元素個數，再次進一步比較。

動圖如下：

代碼：

通過代碼部分，我們也能看出這里面有直接排序的存在，只不過其中的部分和希爾排序有些出入。

public static void shellInsert(int[] array){
    int gap = array.length;
    while(gap > 1){
        gap /= 2;
        shell(array, gap);
    }
}

private static void shell(int[] array, int gap) {
    for (int i = gap; i < array.length; i++) {
        int tmp = array[i];
        int j = i-gap;
        for (; j >= 0; j-= gap) {
            if(array[j] > tmp){
                array[j+gap] = array[j];
            }else{
                array[j+gap] = tmp;
                break;
            }
        }
        array[j+gap] = tmp;
    }
}

時間復雜度：O(N^1.2) - O(N^1.3)

空間復雜度：O(1)

穩(wěn)定性：不穩(wěn)定

選擇排序

第一種思路

步驟：

選擇排序，從名字上我們可以理解為從中不斷選擇出最小值，然后把它交換、排到前面
之所以說是不斷選出最小值，是因為每次選出最小值都是以 i位置為準，而i位置也會不斷變化，兩個for循環(huán)來實現

動圖如下：

代碼：

public static void selectSort(int[] array){
    for (int i = 0; i < array.length; i++) {
        int minIndex = i;
        for (int j = i+1; j < array.length; j++) {
            if(array[j] < array[minIndex]){
                minIndex = j;
            }
        }
        swap(array,i,minIndex);
    }
}

private static void swap(int[] array, int i, int minIndex) {
    int tmp = array[i];
    array[i] = array[minIndex];
    array[minIndex] = tmp;
}

因為其中有元素位置的交換，所以我們可以自己寫一個元素位置交換的方法。

時間復雜度：O(N^2) 和數據是否有序無關

空間復雜度：O(1)

穩(wěn)定性：不穩(wěn)定

第二種思路

步驟：

這里主要是通過雙指針的方法來找到最小值和最大值的位置，當然，這是相對于每次i位置的數的大小。整體過程和上面一種思路有些相似的部分，相對來說，掌握兩種方法還是要好一點。

public static void selectSort1(int[] array){
    int left = 0;
    int right = array.length-1;
    while(left < right){
        int minIndex = left;
        int maxIndex = left;
        for (int i = left+1; i <= right; i++) {
            if(array[i] < array[minIndex]){
                minIndex = i;
            }
            if(array[i] > array[maxIndex]){
                maxIndex = i;
            }
        }
        swap(array, left, minIndex);
        //確保最大值的位置，最大值正好是 left 下標
        //此時把最大值換到了minIndex下標
        if(maxIndex == 0){
            maxIndex = minIndex;
        }
        swap(array, right, maxIndex);
        left++;
        right--;
    }
}

private static void swap(int[] array, int i, int minIndex) {
    int tmp = array[i];
    array[i] = array[minIndex];
    array[minIndex] = tmp;
}

堆排序

步驟：

通過向下調整，創(chuàng)建一棵大根堆的樹
通過把根節(jié)點和最后一個分支節(jié)點進行交換
再進行向下調整，完成排序

這個思路主要是通過大根堆的由大到小的原理，再通過換位來實現排序。

代碼：

public static void heapSort(int[] array){
    createHeap(array);

    int end  = array.length-1;
    while(end > 0){
        swap(array, 0 ,end);
        siftDown(array, 0,end);
        end--;
    }
}

//創(chuàng)建大根堆
public static void createHeap(int[] array){
    //length-1為最后一棵子樹，-1 / 2 是為了找到最后一棵子樹的根節(jié)點
    for (int parent = (array.length-1-1)/2; parent >= 0; parent--) {
        siftDown(array,parent,array.length);//向下調整，創(chuàng)建大根堆
    }
}

/**
 *
 * @param array
 * @param parent 每棵子樹調整的根節(jié)點
 * @param length 每棵子樹調整的結束節(jié)點，跳到最后
 */
public static void siftDown(int[] array, int parent, int length) {
    int child = 2*parent+1;
    while(child < length){
        if(child + 1 < length && array[child] < array[child +1]){
            child++;
        }

        if(array[child] > array[parent]){
            swap(array, child, parent);
            parent = child;
            child = 2*parent+1;
        }else{
            break;
        }
    }
}

private static void swap(int[] array, int i, int minIndex) {
    int tmp = array[i];
    array[i] = array[minIndex];
    array[minIndex] = tmp;
}

時間復雜度：O(N*logN)
空間復雜度：O(1)

穩(wěn)定性：不穩(wěn)定

冒泡排序

步驟：

通過相鄰的兩個元素相互比較，若前位置比后位置的數要大，進行交換

動圖如下：

下面代碼部分是優(yōu)化后的部分，未優(yōu)化則不包含(flg元素和 -i操作 )

代碼：

public static void bubbleSort(int[] array){
    for (int i = 0; i < array.length-1; i++) {
        boolean flg = false;
        for (int j = 0; j < array.length-1-i; j++) {
            if(array[j] > array[j+1]){
                swap(array, j, j+1);
                flg = true;
            }
        }
        //優(yōu)化后的情況
        //n個數據，比較n-1次，有可能其中i次就有序了
        if(!flg){
            break;
        }
    }
}

private static void swap(int[] array, int i, int minIndex) {
    int tmp = array[i];
    array[i] = array[minIndex];
    array[minIndex] = tmp;
}

時間復雜度：不優(yōu)化的情況（沒有下方的boolean元素和-i操作） O(n^2)

優(yōu)化以后，最快情況能達到O(N)

空間復雜度：O(1)

穩(wěn)定性：穩(wěn)定

快速排序

快速排序有三種方式能來實現

挖坑法
hoare法
雙指針法

如果問題問到快速排序，優(yōu)先使用挖坑法，其次hoare法、雙指針法

挖坑法

步驟：

先是實現保證一個數的左邊都比它小，右邊都比它大，具體步驟如下步驟2，3，4
把第一個數存起來，為tmp，第一個位置當作是坑
從后面找比tmp小的值，放到坑里面，后面被放入坑的數的位置再當作坑
從前面找比tmp大的值，放到坑里面，前面被放入坑的數的位置當作坑
再向兩邊進行遞歸來處理

動圖如下：

代碼：

public static void quickSort(int[] array){
    quick(array,0,array.length-1);
}

private static void quick(int[] array, int start, int end){
    // = 是為了應對沒有右邊的情況，遞歸結束條件
    if(start >= end){
        return;
    }
    //整個方法走完之后，為第一次交換位置
    int pivot = partition1(array, start, end);
    quick(array, start, pivot-1);
    quick(array, pivot+1, end);
}

private static int partition1(int[] array, int left, int right) {
    int tmp = array[left];
   
    while(left < right){
        //循環(huán)找，不循環(huán)時則代表找到，找到比tmp小的數
        while(left < right && array[right] >= tmp){
            right--;
        }
        //挖坑法，然后填坑
        //先是把第一個位置當作空，從后面數，如果有數比它小，就放到第一位
        //然后是從前數，找最大值，找到后放到，剛剛的位置
        //最后再把第一個數放到right和left相交的位置
        //方法就是把兩邊的數分大小放到第一個數兩邊
        array[left] = array[right];


        //找到比tmp大的數
        while(left < right && array[left] <= tmp){
            left++;
        }
        array[right] = array[left];
    }
    array[left] = tmp;
    return left;
}

hoare法

步驟：

先是實現保證一個數的左邊都比它小，右邊都比它大，具體步驟如下步驟2，3，4
把第一個數存起來，為tmp
tmp和后面的數進行比較，然后把小數放到tmp前面，大數放到tmp后面
遞歸實現對tmp兩邊進行排序

代碼如下：

public static void quickSort(int[] array){
    quick(array,0,array.length-1);
}

private static void quick(int[] array, int start, int end){
    // = 是為了應對沒有右邊的情況，遞歸結束條件
    if(start >= end){
        return;
    }
    //整個方法走完之后，為第一次交換位置
    int pivot = partition(array, start, end);
    quick(array, start, pivot-1);
    quick(array, pivot+1, end);
}

private static int partition(int[] array, int left, int right) {
    int tmp = array[left];
    int tmpleft = left;

    while(left < right){
        //循環(huán)找，不循環(huán)時則代表找到
        //right是為了把右邊的小數移到左邊
        while(left < right && array[right] >= tmp){
            right--;
        }

        while(left < right && array[left] <= tmp){
            left++;
        }
        swap(array, left, right);
    }
    //因為left所找的是把左邊的大數放到右邊，所以找到最后的數會比left小，進行交換
    swap(array,left,tmpleft);
    return left;
}

private static void swap(int[] array, int i, int minIndex) {
    int tmp = array[i];
    array[i] = array[minIndex];
    array[minIndex] = tmp;
}

雙指針法

步驟：

這個主要是靠 cur + left 雙指針來實現排序的，通過前后條件判斷來進行排序

代碼如下：

public static void quickSort(int[] array){
    quick(array,0,array.length-1);
}

private static void quick(int[] array, int start, int end){
    // = 是為了應對沒有右邊的情況，遞歸結束條件
    if(start >= end){
        return;
    }
    //整個方法走完之后，為第一次交換位置
    int pivot = partition3(array, start, end);
    quick(array, start, pivot-1);
    quick(array, pivot+1, end);
}

public static int partition3(int[] array, int left, int right){
    int prev = left;
    int cur = left+1;
    while(cur <= right){
        if(array[left] > array[cur] && array[cur] != array[prev]){
            swap(array, cur, prev);
        }
        cur++;
    }
    swap(array,prev,left);
    return prev;
}

private static void swap(int[] array, int i, int minIndex) {
    int tmp = array[i];
    array[i] = array[minIndex];
    array[minIndex] = tmp;
}

關于快速排序

時間復雜度：當數據給定的是1 2 3 4 5 6……有序的情況是 O(n^2)

最好的情況是O(N*logN)均勻分為叉，滿二叉樹

空間復雜度：最壞情況，遞歸是要開辟內存的O(N),最好的情況，滿二叉樹O(logN)

穩(wěn)定性：不穩(wěn)定

優(yōu)化

通過上面三種方法，我們能看到三種方法中都有遞歸方式，每次遞歸都需要開辟內存，那么我們可以采取怎樣的方式來減少遞歸的次數？

通過下面兩種方法可以實現我們的想法：

三數取中

直接插入法【針對一定范圍】

關于三數取中的意思是：找到左、右、中三個數的中位數。

部分直接插入，也可以減少遞歸次數，因為數據有越有序，直接插入法越快。

代碼部分如下：

public class Sort {
    public static void quickSort(int[] array){
        quick(array,0,array.length-1);
    }

    private static void quick(int[] array, int start, int end){
        // = 是為了應對沒有右邊的情況，遞歸結束條件
        if(start >= end){
            return;
        }

        if(end - start + 1 <= 7){
            insertSortRange(array, start, end);
            return;
        }
        int minIndex = getMiddleNum(array, start, end);
        swap(array, start, minIndex);

        //整個方法走完之后，為第一次交換位置
        int pivot = partition1(array, start, end);
        quick(array, start, pivot-1);
        quick(array, pivot+1, end);
    }

    public static void insertSortRange(int[] array, int start, int end){
        for (int i = start+1; i <= end; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= start; j--) {
                if(array[j] > tmp){
                    array[j+1] = array[j];
                }else{
                    array[j+1] = tmp;
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

    private static int getMiddleNum(int[] array, int left, int right){
        int mid = (left+right)/2;
        if(array[left] < array[right]){
            if(array[mid] < array[left]){
                return left;
            }else if(array[mid] > array[right]){
                return right;
            }else{
                return mid;
            }
        }else{
            if(array[mid] > array[left]){
                return left;
            }else if(array[mid] < array[right]){
                return right;
            }else{
                return mid;
            }
        }
    }

    private static int partition1(int[] array, int left, int right) {
        int tmp = array[left];

        while(left < right){
            //循環(huán)找，不循環(huán)時則代表找到，找到比tmp小的數
            while(left < right && array[right] >= tmp){
                right--;
            }
            //挖坑法，然后填坑
            //先是把第一個位置當作空，從后面數，如果有數比它小，就放到第一位
            //然后是從前數，找最大值，找到后放到，剛剛的位置
            //最后再把第一個數放到right和left相交的位置
            //方法就是把兩邊的數分大小放到第一個數兩邊
            array[left] = array[right];


            //找到比tmp大的數
            while(left < right && array[left] <= tmp){
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }

    private static void swap(int[] array, int left, int right){
        int tmp = array[left];
        array[left] = array[right];
        array[right] = tmp;
    }
}

非遞歸實現

非遞歸實現，主要是棧的使用，通過控制出棧和入棧的元素及其順序來實現

代碼如下：

public static void quickSort(int[] array){
    quickNor(array,0,array.length-1);
}

private static void quickNor(int[] array, int start, int end){

    Deque<Integer> stack = new ArrayDeque<>();
    int pivot = partition1(array, start, end);
    //pivot左邊有兩個元素
    if(pivot > start+1){
        stack.push(start);
        stack.push(pivot-1);
    }

    if(pivot < end-1){
        stack.push(pivot+1);
        stack.push(end);
    }

    while(!stack.isEmpty()){
        end = stack.pop();
        start = stack.pop();
        pivot = partition1(array, start, end);
        if(pivot > start+1){
            stack.push(start);
            stack.push(pivot-1);
        }

        if(pivot < end-1){
            stack.push(pivot+1);
            stack.push(end);
        }
    }
}

private static int partition1(int[] array, int left, int right) {
    int tmp = array[left];

    while(left < right){
        //循環(huán)找，不循環(huán)時則代表找到，找到比tmp小的數
        while(left < right && array[right] >= tmp){
            right--;
        }
        //挖坑法，然后填坑
        //先是把第一個位置當作空，從后面數，如果有數比它小，就放到第一位
        //然后是從前數，找最大值，找到后放到，剛剛的位置
        //最后再把第一個數放到right和left相交的位置
        //方法就是把兩邊的數分大小放到第一個數兩邊
        array[left] = array[right];


        //找到比tmp大的數
        while(left < right && array[left] <= tmp){
            left++;
        }
        array[right] = array[left];
    }
    array[left] = tmp;
    return left;
}

private static void swap(int[] array, int left, int right){
    int tmp = array[left];
    array[left] = array[right];
    array[right] = tmp;
}

歸并排序

步驟：

先把要排序的元素分為兩個組，接著繼續(xù)向下分組(有種遞歸的味道了)
把每組元素比較完后，再把兩個有序數組組合起來

代碼如下：

public static void mergeSort(int[] array){
    mergeSortTmp(array, 0, array.length-1);
}

//遞歸實現歸并排序
private static void mergeSortTmp(int[] array, int left, int right) {
    if(left >= right){
        return;
    }
    //找中間值
    int mid = (left + right)/2;
    mergeSortTmp(array, left, mid-1);
    mergeSortTmp(array, mid+1, right);
    //走到這里，相當于全部分解完
    //合并，合并有序數組
    merge(array, left, mid, right);


}

private static void merge(int[] array, int left, int mid, int right) {
    int[] tmp = new int[right-left+1];
    int k = 0;
    int s1 = left;
    int e1 = mid;
    int s2 = mid+1;
    int e2 = right;

    while(s1 <= e1 &&  s2 <= e2){
        if(array[s1] <= array[s2]){
            tmp[k++] = array[s1++];
        }else {
            tmp[k++] = array[s2++];
        }
    }

    while(s1 <= e1){
        tmp[k++] = array[s1++];
    }

    while(s2 <= e2){
        tmp[k++] = array[s2++];
    }
    //可以保證tmp數組是有序的
    for (int i = 0; i < k; i++) {
        array[i+left] = tmp[i];
    }
}

時間復雜度：O(N*logN)

空間復雜度：O(N)

穩(wěn)定性：穩(wěn)定

非遞歸實現

非遞歸的實現，主要依靠的間隔gap的不斷變大，然后通過每一小部分的排序進而來實現整個數據組的排序

代碼如下：

public static void mergeSortNor(int[] array){
    int gap =1;
    while(gap < array.length){
        for (int i = 0; i < array.length; i = i + gap*2) {
            int left = i;
            int mid = (left + gap -1);
            if(mid >= array.length){
                mid = array.length-1;
            }
            int right = mid + gap;
            if(right >= array.length){
                right = array.length-1;
            }
            merge(array, left, mid, right);
        }
        gap *= 2;
    }
}

private static void merge(int[] array, int left, int mid, int right) {
    int[] tmp = new int[right-left+1];
    int k = 0;
    int s1 = left;
    int e1 = mid;
    int s2 = mid+1;
    int e2 = right;

    while(s1 <= e1 &&  s2 <= e2){
        if(array[s1] <= array[s2]){
            tmp[k++] = array[s1++];
        }else {
            tmp[k++] = array[s2++];
        }
    }

    while(s1 <= e1){
        tmp[k++] = array[s1++];
    }

    while(s2 <= e2){
        tmp[k++] = array[s2++];
    }
    //可以保證tmp數組是有序的
    for (int i = 0; i < k; i++) {
        array[i+left] = tmp[i];
    }
}

計數排序

非基于比較的排序

還有桶排序，基數排序，感興趣可以了解一下

使用場景：集中在某個范圍內的一組數據

步驟：

根據數據的個數來創(chuàng)建數組
把對應元素出現的個數給到對應的位置，記錄出現的次數
根據記錄的次數，依次輸出元素

代碼如下：

public static void countSort(int[] array){

    //1.找最大值 和 最小值 來確定 計數數組的大小
    int maxVal = array[0];
    int minVal = array[0];
    for (int i = 1; i < array.length; i++) {
        if(array[i] > maxVal){
            maxVal = array[i];
        }
        if(array[i] < minVal){
            minVal = array[i];
        }
    }
    int len = maxVal - minVal + 1;
    int[] count = new int[len];

    //2.遍歷原來的數組array， 把每個元素 放到對應的計數數組中 進行比較
    for (int i = 0; i < array.length; i++) {
        int index = array[i];
        count[index-minVal]++;
    }

    //3.依次 遍歷計數數組
    int index = 0;
    for (int i = 0; i < count.length; i++) {
        while(count[i] != 0){
            array[index] = i+minVal;
            index++;
            count[i]--;
        }
    }
}

總結

到此這篇關于Java實現八種排序算法的文章就介紹到這了,更多相關Java八種排序算法內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

SpringSecurity認證授權全流程解讀
這篇文章主要介紹了SpringSecurity認證授權全流程,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
2025-06-06
mapper.xml無法解析字段的問題
這篇文章主要介紹了mapper.xml無法解析字段的問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
2023-06-06
java多線程volatile內存語義解析
這篇文章主要介紹了java多線程volatile內存語義解析,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
2020-01-01
Mybatis Plus框架項目落地實踐分析總結
這篇文章主要為大家介紹了Mybatis Plus框架項目落地實踐分析總結，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪
2023-03-03
Feign之Multipartfile文件傳輸填坑
這篇文章主要介紹了Feign之Multipartfile文件傳輸埋坑及解決方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
2021-06-06
Java中精確的浮點運算操作示例
這篇文章主要介紹了Java中精確的浮點運算操作方法,結合具體實例形式分析了java浮點數運算的相關函數、使用技巧與注意事項,需要的朋友可以參考下
2017-06-06
Java進階必備之多線程編程
今天帶大家來學習java多線程編程,文中有非常詳細的代碼示例及介紹,對正在學習java多線程的小伙伴們很有幫助,需要的朋友可以參考下
2021-05-05
修改maven本地倉庫路徑的方法
本篇文章主要介紹了修改maven本地倉庫路徑的方法，小編覺得挺不錯的，現在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧
2017-12-12
springboot整合easy-es實現數據的增刪改查的示例代碼
Easy-Es是一款基于ElasticSearch官方提供的RestHighLevelClient打造的低碼開發(fā)框架,本文主要介紹了springboot整合easy-es實現數據的增刪改查的示例代碼,具有一定的參考價值,感興趣的可以了解一下
2024-03-03
SpringBoot中的Logging詳解
這篇文章主要介紹了SpringBoot中的Logging詳解,log配置可能是被忽視的一個環(huán)節(jié),一般的項目中日志配置好了基本上很少去改動,我們常規(guī)操作是log.info來記錄日志內容,很少會有人注意到springBoot中日志的配置,需要的朋友可以參考下
2023-09-09