欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java實現(xiàn)常見排序算法的優(yōu)化

 更新時間:2021年01月28日 15:07:41   作者:保護眼睛  
今天給大家?guī)淼氖顷P于Java的相關知識,文章圍繞著Java實現(xiàn)常見排序算法的優(yōu)化展開,文中有非常詳細的介紹及代碼示例,需要的朋友可以參考下

冒泡排序

冒泡排序的思想:
每次讓當前的元素和它的下一個元素比較大小、如果前一個的元素大于后一個元素的話,交換兩個元素。
這樣的話經歷一次掃描之后能確保數(shù)組的最后一個元素一定是數(shù)組中最大的元素。
那么下次掃描的長度比上次少一個、因為數(shù)組的最后一個元素已經是最大的了、即最后一個元素已經有序了。

優(yōu)化一: 優(yōu)化的思路就是每一次掃描遍歷一次數(shù)組、如果某次的掃描之后沒有發(fā)生數(shù)組元素的交換的話、那么說明數(shù)組的元素已經是有序的了,
就可以直接跳出循環(huán)、沒有繼續(xù)掃描的必要了。
優(yōu)化二:如果數(shù)組的尾部已經局部有序的話、那么在經歷一次掃描之后的話、就不需要在對尾部局部有序的部分進行掃描了。
具體的做法就是記錄上一次交換的位置,然后讓下一次的掃描到上一次的記錄的位置就好了、因為記錄的位置后的元素已經有序了。

原始的寫法

//常規(guī)的寫法
    public static void bubbleSort1(int[] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                }
            }
        }
    }

優(yōu)化一

//優(yōu)化一
    public static void bubbleSort2(int[] array) {
        boolean flag = true;
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                    flag = false;
                }
            }
            if (flag)
                break;
        }
    }

優(yōu)化二

//優(yōu)化二
    public static void bubbleSort3(int[] array) {
        int end = array.length-1;

        for (int i = end; i > 0 ; i--) {

            int lastIndex = 1;
            for (int j = 0; j < end; j++) {
                if (array[j] > array[j + 1]) {
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                    lastIndex = j + 1;
                }
            }
            end = lastIndex;
        }
    }

選擇排序

選擇排序的思想也是類似與冒泡排序的思想。再一次掃描之后找打數(shù)組當中最大的元素、將最大的元素放在數(shù)組的末尾。第二次的掃描數(shù)組的時候比上次掃描的長度減一

當然也可以換種思路來實現(xiàn)選擇排序—每次掃描數(shù)組、然后找出最小的元素、將最小的元素放在數(shù)組的首位、下次掃描的時候不在掃描數(shù)組的首位、將第二小的元素放在數(shù)組第二個位置即可。

方法一

public static void selectSort1(int[] array) {
        for (int end = array.length - 1; end > 0; end--) {
            int maxIndex = 0;
            for (int start = 0; start <= end; start++) {
                if (array[maxIndex] < array[start]) {
                    maxIndex = start;
                }
            }

            int tmp = array[end];
            array[end] = array[maxIndex];
            array[maxIndex] = tmp;
        }
    }

方法二

 public static void selectSort2(int[] array) {
        for (int start = 0; start < array.length; start++) {
            int minIndex = start;
            for (int end = start; end < array.length; end++) {
                if (array[end] < array[minIndex]) {
                    minIndex = end;
                }
            }
            int tmp = array[minIndex];
            array[minIndex] = array[start];
            array[start] = tmp;
        }
    }

堆排序

堆排可以看作是對選擇排序的一種優(yōu)化、將數(shù)組原地建成大堆、將最大的元素放在數(shù)組的最后一個位置、adjust使數(shù)組繼續(xù)保持大根堆、下一次的交換是和數(shù)組的倒數(shù)第二個元素進行交換。思路和前面兩種排序的算法的思路一致、也是找最值、和數(shù)組的首或尾交換、下次交換的時候忽略已經交換的元素。

當然也可以建立一個小堆。堆頂已經是最小的了,那么只需要比較堆頂?shù)淖蠛⒆雍陀液⒆拥拇笮〖纯?,左孩子大于右孩子的話、交換、讓右孩子adjust保持小堆(因為交換后的右孩子可能不滿足小堆)即可。

建大堆來實現(xiàn)堆排

public static void heapSort1(int[] array) {
        //建大堆
        for (int p = (array.length - 1 - 1) / 2; p >= 0; p--) {
            adjustDown(array, p, array.length);
        }
        //交換
        int end = array.length - 1;
        while (end > 0) {
            int tmp = array[0];
            array[0] = array[end];
            array[end] = tmp;
            adjustDown(array, 0, end);
            end--;
        }
    }

    public static void adjustDown(int[] array, int p, int len) {
        int child = p * 2 + 1;
        while (child < len) {
            if (child + 1 < len && array[child] < array[child + 1]) {
                child++;
            }
            if (array[child] > array[p]) {
                int tmp = array[child];
                array[child] = array[p];
                array[p] = tmp;
                p = child;
                child = p * 2 + 1;
            } else {
                break;
            }
        }
    }

建小堆來實現(xiàn)堆排

  public static void adjustDown1(int[] array, int p, int len) {
        int child = p * 2 + 1;
        while (child < len) {
            if (child + 1 < len && array[child] > array[child + 1]) {
                child++;
            }
            if (array[child] < array[p]) {
                int tmp = array[child];
                array[child] = array[p];
                array[p] = tmp;
                p = child;
                child = p * 2 + 1;
            } else {
                break;
            }
        }
    }

    public static void heapSort2(int[] array) {
        //建小堆
        for (int p = (array.length - 1 - 1) / 2; p >= 0; p--) {
            adjustDown1(array, p, array.length);
        }
        //交換
        int startIndex = 1;
        while (startIndex + 1 < array.length) {
            if (array[startIndex] > array[startIndex + 1]) {
                int tmp = array[startIndex];
                array[startIndex] = array[startIndex + 1];
                array[startIndex + 1] = tmp;
                adjustDown1(array,startIndex+1,array.length);
            }
            startIndex++;
        }
    }

插入排序

插入排序的思想就是類似于打牌的時候,左手拿的排就是有序的、右手拿牌然后將牌與前面的牌進行比較、然后插入到合適位置。
優(yōu)化一:
優(yōu)化一的思路就是將比較變?yōu)橐苿樱?br /> 每次拿到元素的時候就要和前面的元素進行比較、數(shù)組的逆序對比較多的話、那么每次都要比較和交換、所以我們可以先記錄下當前的元素的值、將該元素前面大于該元素的數(shù)字都后移一位、然后插入、這樣的話比較的和交換的次數(shù)就減少了。
優(yōu)化二:
要在前面的有序的元素中找到當前元素要插入的位置、那么是不是可以使用二分查找來實現(xiàn)呢?所以我們可以使用二分查找來繼續(xù)優(yōu)化一下。

實現(xiàn)

  public static void insertSort1(int[] array) {
        for (int start = 1; start < array.length; start++) {
            int cur = start;
            while (cur > 0 && array[cur] < array[cur - 1]) {
                int tmp = array[cur];
                array[cur] = array[cur - 1];
                array[cur - 1] = tmp;
                cur--;
            }
        }
    }

優(yōu)化一

public static void insertSort2(int[] array){
        for (int start = 1; start < array.length; start++) {
            int cur = start;
            int tmp = array[start];
            while (cur>0 && tmp < array[cur-1]){
                array[cur] = array[cur-1];
                cur--;
            }
            array[cur] = tmp;
        }
    }

優(yōu)化二

public static void insertSort3(int[] array) {
        for (int start = 1; start < array.length; start++) {
            int cur = array[start];
            int insertIndex = searchIndex(array, start);
            for (int i = start; i > insertIndex; i--) {
                array[i] = array[i - 1];
            }
            array[insertIndex] = cur;
        }
    }

    public static int searchIndex(int[] array, int index) {
        int start = 0;
        int end = index;
        while (start < end) {
            int mid = (start + end) >> 1;
            if (array[index] < array[mid]) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }

歸并排序

歸并排序的思想就是—不斷的將當前的序列平均分為2個子序列、直到子序列中的元素的個數(shù)為1的時候、然后不斷地將2個子序列合并成一個有序的序列。

優(yōu)化:
可以看到每次歸并的時候、申請的額外的數(shù)組的大小為左子序列的長度+右子序列的長度(end - start + 1)、歸并之后將額外的數(shù)組的值賦值到原數(shù)組的對應的位置上。
那么我們可以做出優(yōu)化、可以直接在原數(shù)組上進行操作、每次將左子序列的值拷貝出來、和右子序列的值比較、直接覆蓋原來的值即可。這樣每次申請的額外空間就比原來申請的空間減少一倍。

遞歸實現(xiàn)歸并排序

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

    public static void mergerRec(int[] array, int start, int end) {
        if (start >= end) return;
        int mid = (start + end) >> 1;
        mergerRec(array, start, mid);
        mergerRec(array, mid + 1, end);
        merger(array, start, mid, end);
    }

    private static void merger(int[] array, int start, int mid, int end) {
        int[] tmpArray = new int[end - start + 1];
        int tmpArrayIndex = 0;
        int leftStart = start;
        int leftEnd = mid;
        int rightStart = mid + 1;
        int rightEnd = end;
        while (leftStart <= leftEnd && rightStart <= rightEnd) {
            if (array[leftStart] < array[rightStart]) {
                tmpArray[tmpArrayIndex++] = array[leftStart++];
            } else {
                tmpArray[tmpArrayIndex++] = array[rightStart++];
            }
        }
        while (leftStart <= leftEnd) {
            tmpArray[tmpArrayIndex++] = array[leftStart++];
        }
        while (rightStart <= rightEnd) {
            tmpArray[tmpArrayIndex++] = array[rightStart++];
        }

        for (int i = 0; i < tmpArray.length; i++) {
            array[start + i] = tmpArray[i];
        }
    }

優(yōu)化

public static void mergerSort(int[] array, int start, int end) {
        if (end - start < 2) return;
        int mid = (start + end) >> 1;
        mergerSort(array, start, mid);
        mergerSort(array, mid, end);
        merger(array, start, mid, end);
    }

    private static void merger(int[] array, int start, int mid, int end) {
        int[] tmpLeftArray = new int[(end - start + 1) >> 1];
        int ls = 0;
        int le = mid - start;
        int rs = mid;
        int re = end;
        int arrIndex = start;
        for (int i = ls; i < le; i++) {
            tmpLeftArray[i] = array[start + i];
        }
        while (ls < le) {
            if (rs < re && array[rs] < tmpLeftArray[ls]) {
                array[arrIndex++] = array[rs++];
            } else {
                array[arrIndex++] = tmpLeftArray[ls++];

            }
        }
    }

來看O(n)的排序

public class ThreadSortDemo {
    public static void main(String[] args) {
        int[] array = {2, 23, 45, 5, 100, 0, 9};
        for (int i = 0; i < array.length; i++) {
            new ThreadSort(array[i]).start();
        }
    }
}

class ThreadSort extends Thread {
    private int val;

    ThreadSort(int val) {
        this.val = val;
    }

    @Override
    public void run() {
        try {
            Thread.sleep(val);
            System.out.print(val + " ");
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

快速排序和希爾排序好像沒有優(yōu)化的方法了。歡迎補充

當然除了基于比較的排序、還有基于非比較的排序。
計數(shù)排序:核心思想就是統(tǒng)計每個整數(shù)在序列中出現(xiàn)的次數(shù)、進而推導出每個整數(shù)在有序序列中的索引。具體的做法就是先找出序列中最大的元素、開辟出最大元素+1的數(shù)組空間、統(tǒng)計每個元素出現(xiàn)的次數(shù)counts[array[i]]++、然后遍歷coutns數(shù)組、找出不為0的元素、輸出對應的下標即可、也可以將下標重新放回到array數(shù)組中,也就是相當于array數(shù)組已經排好序了。
基數(shù)排序: 將所有元素統(tǒng)一為同樣的數(shù)位長度, 數(shù)位較短的數(shù)前面補零。然后, 從最低位開始, 依次進行一次排序,這樣從最低位排序一直到最高位排序完成以后, 原數(shù)組就變成一個有序序列。
桶排序:創(chuàng)建一定數(shù)量的桶、可以使用數(shù)組或者鏈表作為桶、按照一定的規(guī)則、將序列中的元素均勻的分配到對應的桶中、然后對每個桶中的元素進行單獨的排序、最后將所有非空的桶的元素合并成有序序列。

到此這篇關于Java實現(xiàn)常見排序算法的優(yōu)化的文章就介紹到這了,更多相關Java排序算法內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!

相關文章

  • java 生成二維碼實例

    java 生成二維碼實例

    這篇文章主要介紹了java 生成二維碼的實例,文中講解非常細致,代碼幫助大家更好的理解和學習,感興趣的朋友可以了解下
    2020-07-07
  • MyBatis延遲加載實現(xiàn)步驟詳解

    MyBatis延遲加載實現(xiàn)步驟詳解

    這篇文章主要介紹了MyBatis延遲加載實現(xiàn)步驟詳解,? MyBatis中的延遲加載,也成為懶加載,是指在進行關聯(lián)查詢時,按照設置的延遲規(guī)則推遲對關聯(lián)對象的查詢,延遲加載可以有效的減少數(shù)據庫的壓力,需要的朋友可以參考下
    2023-10-10
  • Java及Android中常用鏈式調用寫法簡單示例

    Java及Android中常用鏈式調用寫法簡單示例

    這篇文章主要介紹了Java及Android中常用鏈式調用寫法,結合實例形式分析了java編程中的鏈式調用概念、簡單使用方法及相關操作技巧,需要的朋友可以參考下
    2018-01-01
  • Java web實現(xiàn)賬號單一登錄,防止同一賬號重復登錄(踢人效果)

    Java web實現(xiàn)賬號單一登錄,防止同一賬號重復登錄(踢人效果)

    這篇文章主要介紹了Java web實現(xiàn)賬號單一登錄,防止同一賬號重復登錄,有點類似于qq登錄踢人效果,本文給大家介紹的非常詳細,具有一定的參考借鑒價值,需要的朋友可以參考下
    2019-10-10
  • 將Java對象序列化成JSON和XML格式的實例

    將Java對象序列化成JSON和XML格式的實例

    下面小編就為大家分享一篇將Java對象序列化成JSON和XML格式的實例,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2017-12-12
  • Java8中接口的新特性測試

    Java8中接口的新特性測試

    今天小編就為大家分享一篇關于Java8中接口的新特性測試,小編覺得內容挺不錯的,現(xiàn)在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧
    2018-12-12
  • Springboot 整合通用mapper和pagehelper展示分頁數(shù)據的問題(附github源碼)

    Springboot 整合通用mapper和pagehelper展示分頁數(shù)據的問題(附github源碼)

    這篇文章主要介紹了Springboot 整合通用mapper和pagehelper展示分頁數(shù)據(附github源碼),本文通過實例代碼給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2021-09-09
  • Java代碼里如何拼接SQL語句到mybatis的xml

    Java代碼里如何拼接SQL語句到mybatis的xml

    這篇文章主要介紹了Java代碼里拼接SQL語句到mybatis的xml操作,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2021-06-06
  • Java數(shù)據結構之棧與綜合計算器的實現(xiàn)

    Java數(shù)據結構之棧與綜合計算器的實現(xiàn)

    這篇文章主要為大家詳細介紹了Java數(shù)據結構中棧與綜合計算器的實現(xiàn),文中的示例代碼講解詳細,具有一定的學習價值,感興趣的小伙伴可以了解一下
    2022-10-10
  • SpringMVC日期類型參數(shù)傳遞實現(xiàn)步驟講解

    SpringMVC日期類型參數(shù)傳遞實現(xiàn)步驟講解

    這篇文章主要介紹了SpringMVC日期類型參數(shù)傳遞實現(xiàn)步驟,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習吧
    2023-02-02

最新評論