一些排序算法(java描述)

Atom 發布于2019-08-16 18:26 / 3430人閱讀

摘要：桶排序的基本思路是遍歷一個待排的數組把每個數出現的次數記錄到一個新的數組里面那這個新的數組里的下標就是待排序的數組的值設待排數組是記錄待排數組的桶是讓我們來理一下思路新建一個數組數組的大小是循環遍歷這個數組在循環體里面將數出現的次數記

bucket sort

桶排序的基本思路是遍歷一個待排的數組,把每個數出現的次數記錄到一個新的數組里面,那這個新的數組里的下標就是待排序的數組的值.

設待排數組是arr,記錄待排數組的桶是bucket讓我們來理一下思路:

新建一個數組,數組的大小是arr.length-1;

循環遍歷arr這個數組,在循環體里面將arr數出現的次數記錄到bucket這個數組里面;

遍歷bucket這個數組,判斷值是多少就輸出多少次bucket的下標;

以下是Java代碼:

public static void bucketSort(int [] arr){
        int[] bucket=new int[max(arr)+1];
        for (int i = 0; i < arr.length; i++) {
            bucket[arr[i]]++;
        }
        int count=0;
        for (int i=0;i
以上只是一個簡單的桶排序,不能排序負數和小數,但它的時間復雜度也僅僅是T(N)=O(N+M);
buble sort
冒泡排序的的思路就是遍歷數組,交換(swap)相鄰兩個元素,使余下未排序數組部分最大(或最小)的元素浮到最前或最后;
這樣排序一個長度為N的數組所需要的時間復雜度T(N)=O(N²)
以下是java代碼:
    public static void bubbleSort(int [] arr){
        for (int i = arr.length; i > 0; i--) {
            for (int j = 0; j < i-1; j++) {
                if (arr[j]>arr[j+1]){
                    swap(arr,j,j+1);
                }
            }
        }
    }
冒泡排序的缺點很明顯,在全部無序的情況下,時間復雜度太高了(因為它只能交換相鄰兩個元素);
而且上述的示例有一個需要改進的地方就是:設想一個數組前半部分是有序的,但是如果有序的話檢查一次就夠了(前面在排序后半部分的元素中已經檢查過了),所以我們可以設一個布爾型的flag值,有序就直接跳過,這樣能大大縮短代碼運行時間;
selection sort
選擇排序和冒泡排序有點類似,它的基本思路就是把數組看成兩部分:一部分有序,一部分無序;
把后面無序的部分的最小值放到前半部分的最后面(冒泡排序是交換相鄰的元素)
以下是java代碼:
    public static void selectionSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            for (int j = i+1; j < arr.length; j++) {
                if (arr[j]
選擇排序的時間復雜度也是O(N²)
insertion sort
插入排序的基本思路是選擇后面沒排序的部分的第一個元素,插入到前半部分有序的合適位置(和選擇排序正好相反);
讓我們來理一下思路吧:

arr[0]是有序的;
遍歷余下的將arr[1]放到前面有序部分的合適位置(arr[0]前面或后面);
每次把余下部分的第一個放到前面有序的合適位置(重復1,2步驟);
直到余下的部分沒有元素.

以下是java代碼:
 /**
     * thought the arr as two part, the front part is ordered and the end part is unordered;
     * in the loop each time put the fist element of the end part to the appropriate position in the front part;
     * until the outer loop is over;
     * @param arr the array wait to sort;
     */
    public static void insertionSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] j; k--) {
                        arr[k]=arr[k-1];
                    }
                    arr[j]=tmp;
                    break;
                }
            }
        }
    }
由于有兩層循環,所以它的時間復雜度也是O(N²),不過和選擇排序不同的是它是穩定的排序;
quick sort
快速排序采用分治法(divide-and-conquer method),利用遞歸(recursion)對數組作拆分處理;
分治法的基本思路就是:大事化小,小事化無;
讓我們來理一下思路吧:

隨便找一個元素看作基準點(為了方便起見我們不妨把arr[0]看作基準點);
基準點左邊的數比基準點小,右邊的數比它大;
循環調用,直到每部分只有兩數,左邊小,右邊大;

java代碼如下:
    /**
     * Quicksort is a divide-and-conquer method for sorting.
     * divide the arr to two parts, set the leftest element as the standard position;
     * find the smaller element than standard position from the right;
     * find the larger element than standard position from the left;
     * @param arr the arr wait to sort
     * @param left left guard
     * @param right right guard
     */
    public static void quickSort(int[] arr,int left,int right){
        if (left>right) return;
        int i=left,j=right,pos=arr[left];
        while(i!=j){
            while(i=pos){
                j--;
            }
            while(i
由于快排是跳躍交換元素位置的(和冒泡排序不同),所以它的平均時間復雜度是O(NlogN);
沒接觸到遞歸的同學可能覺得快排有點抽象,可以參照<啊哈,算法>或<算法第四版>(實際上我也在用這兩本教材),你也可以看看發明者關于快排的論文;
summary
以下是每種算法的平均時間復雜度:


name
T(N)



bucket sort
O(N+M)


buble sort
O(N²)


selection sort
O(N²)


insertion sort
O(N²)


quick sort
O(NlogN)



還有其他的希爾排序,堆排序,計數排序,基數排序啊有待讀者們去一一探索,這里就不再一一贅述了.
原文鏈接:<算法第四版>最佳實踐

name	T(N)
bucket sort	O(N+M)
buble sort	O(N²)
selection sort	O(N²)
insertion sort	O(N²)
quick sort	O(NlogN)

GPU云服務器云服務器 java插入排序算法 java實驗排序算法 java自然排序算法 java三種排序算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/75103.html

十大經典排序算法總結(Javascript描述)

摘要：算法描述冒泡排序是一種簡單的排序算法。算法描述和實現一般來說，插入排序都采用在數組上實現。平均情況希爾排序年發明第一個突破的排序算法是簡單插入排序的改進版它與插入排序的不同之處在于，它會優先比較距離較遠的元素。前言讀者自行嘗試可以想看源碼戳這，博主在github建了個庫，讀者可以Clone下來本地嘗試。此博文配合源碼體驗更棒哦~~~ 個人博客：Damonare的個人博客原文地址：...

Binguner 2019-08-20 11:05 評論0 收藏0
基本排序 - Algorithms, Part I, week 2 ELEMENTARY SORTS

摘要：我們討論比較排序算法的理論基礎，并結合本章應用排序和優先級隊列算法。基本排序引入了選擇排序，插入排序和。描述了，一種保證在線性時間內運行的排序算法。當我們后續實現排序算法時，我們實際上將這個機制隱藏在我們的實現下面。前言上一篇：棧和隊列下一篇：歸并排序排序是重新排列一系列對象以便按照某種邏輯順序排列的過程。排序在商業數據處理和現代科學計算中起著重要作用。在交易處理，組合優化，天體...

BLUE 2019-08-16 15:58 評論0 收藏0
八大排序算法Java實現

摘要：向后移動位簡單選擇排序基本思想常用于取序列中最大最小的幾個數時。代碼實現循環次數選出最小的值和位置交換位置堆排序基本思想對簡單選擇排序的優化。概述常見的八大排序算法，它們之間的關系如下： showImg(https://segmentfault.com/img/remote/1460000011395738?w=880&h=671); 直接插入排序希爾排序簡單選擇排序堆排序...

Coly 2019-08-15 11:57 評論0 收藏0
算法-java排序實現總結

摘要：一常見的排序算法及時間復雜度二各排序算法的理解及實現冒泡排序算法描述比較相鄰元素，如果第一個比第二個大，交換位置，這樣每經過一趟就冒出一個最大的動圖演示代碼實現快速排序算法描述從數列中挑出一個元素，稱為基準從左向右找比這個第一個比這個基一.常見的排序算法及時間復雜度 showImg(https://segmentfault.com/img/bV8J6j?w=1722&h=1132);...

explorer_ddf 2019-08-15 15:31 評論0 收藏0
Java數據結構與算法——排序(基礎概念)

摘要：排序算法索引待更數據結構與算法桶排序數據結構與算法快速排序時間復雜度算法的時間復雜度是一個函數，其定量的描述了一個算法運行時間和輸入規模之間的關系。總結在介紹排序算法之前，本篇先對后面排序算法的基本概念說叨說叨，打下一個基礎鋪墊。聲明：碼字不易，轉載請注明出處，歡迎文章下方討論交流。前言：Java數據結構與算法專題會不定時更新，歡迎各位讀者監督。在介紹各類排序算法之前，本篇先聊聊算...

jzzlee 2019-08-16 11:10 評論0 收藏0