一些排序算法(java描述)

Atom 發(fā)布于2019-08-16 18:26 / 3438人閱讀

摘要：桶排序的基本思路是遍歷一個待排的數(shù)組把每個數(shù)出現(xiàn)的次數(shù)記錄到一個新的數(shù)組里面那這個新的數(shù)組里的下標(biāo)就是待排序的數(shù)組的值設(shè)待排數(shù)組是記錄待排數(shù)組的桶是讓我們來理一下思路新建一個數(shù)組數(shù)組的大小是循環(huán)遍歷這個數(shù)組在循環(huán)體里面將數(shù)出現(xiàn)的次數(shù)記

bucket sort

桶排序的基本思路是遍歷一個待排的數(shù)組,把每個數(shù)出現(xiàn)的次數(shù)記錄到一個新的數(shù)組里面,那這個新的數(shù)組里的下標(biāo)就是待排序的數(shù)組的值.

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

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

循環(huán)遍歷arr這個數(shù)組,在循環(huán)體里面將arr數(shù)出現(xiàn)的次數(shù)記錄到bucket這個數(shù)組里面;

遍歷bucket這個數(shù)組,判斷值是多少就輸出多少次bucket的下標(biāo);

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

arr[0]是有序的;
遍歷余下的將arr[1]放到前面有序部分的合適位置(arr[0]前面或后面);
每次把余下部分的第一個放到前面有序的合適位置(重復(fù)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;
                }
            }
        }
    }
由于有兩層循環(huán),所以它的時間復(fù)雜度也是O(N²),不過和選擇排序不同的是它是穩(wěn)定的排序;
quick sort
快速排序采用分治法(divide-and-conquer method),利用遞歸(recursion)對數(shù)組作拆分處理;
分治法的基本思路就是:大事化小,小事化無;
讓我們來理一下思路吧:

隨便找一個元素看作基準(zhǔn)點(diǎn)(為了方便起見我們不妨把a(bǔ)rr[0]看作基準(zhǔn)點(diǎn));
基準(zhǔn)點(diǎn)左邊的數(shù)比基準(zhǔn)點(diǎn)小,右邊的數(shù)比它大;
循環(huán)調(diào)用,直到每部分只有兩數(shù),左邊小,右邊大;

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
由于快排是跳躍交換元素位置的(和冒泡排序不同),所以它的平均時間復(fù)雜度是O(NlogN);
沒接觸到遞歸的同學(xué)可能覺得快排有點(diǎn)抽象,可以參照<啊哈,算法>或<算法第四版>(實(shí)際上我也在用這兩本教材),你也可以看看發(fā)明者關(guān)于快排的論文;
summary
以下是每種算法的平均時間復(fù)雜度:


name
T(N)



bucket sort
O(N+M)


buble sort
O(N²)


selection sort
O(N²)


insertion sort
O(N²)


quick sort
O(NlogN)



還有其他的希爾排序,堆排序,計數(shù)排序,基數(shù)排序啊有待讀者們?nèi)ヒ灰惶剿?這里就不再一一贅述了.
原文鏈接:<算法第四版>最佳實(shí)踐

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云服務(wù)器云服務(wù)器 java插入排序算法 java實(shí)驗排序算法 java自然排序算法 java三種排序算法

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/75103.html

發(fā)表評論

登陸后可評論

0條評論

Atom

男|高級講師

我要關(guān)注我要私信

TA的文章

tensorflow1安裝

閱讀 3181·2023-04-25 19:09
整理一些中國香港大帶寬vps – 有cn2 gia大帶寬vps

閱讀 3893·2021-10-22 09:54
?openGauss數(shù)據(jù)庫源碼解析系列文章—— DeepSQL?

閱讀 1770·2021-09-29 09:35
FIN7黑客使用Windows 11主題文件植入Javascript后門

閱讀 2925·2021-09-08 09:45
NTP時間戳轉(zhuǎn)換成UTC時間的過程

閱讀 2270·2021-09-06 15:00
CSS基礎(chǔ)

閱讀 2781·2019-08-29 15:32
巧用patternLock開發(fā)圖案滑屏解鎖

閱讀 1046·2019-08-28 18:30
VueCli+Node+mongodb打造個人博客（含前臺展示及后臺管理系統(tǒng)）（下）

閱讀 382·2019-08-26 13:43

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

一些排序算法(java描述)

相關(guān)文章

**十大經(jīng)典排序算法總結(jié)(Javascript描述)**

基本排序 - Algorithms, Part I, week 2 ELEMENTARY SORTS

**八大排序算法Java實(shí)現(xiàn)**

**算法-java排序實(shí)現(xiàn)總結(jié)**

Java數(shù)據(jù)結(jié)構(gòu)與算法——排序(基礎(chǔ)概念)

發(fā)表評論

0條評論

Atom

男|高級講師

TA的文章

tensorflow1安裝

整理一些中國香港大帶寬vps – 有cn2 gia大帶寬vps

?openGauss數(shù)據(jù)庫源碼解析系列文章—— DeepSQL?

FIN7黑客使用Windows 11主題文件植入Javascript后門

NTP時間戳轉(zhuǎn)換成UTC時間的過程

CSS基礎(chǔ)

巧用patternLock開發(fā)圖案滑屏解鎖

VueCli+Node+mongodb打造個人博客（含前臺展示及后臺管理系統(tǒng)）（下）

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

一些排序算法(java描述)

相關(guān)文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！