一些簡單的數組排序算法

AndroidTraveler 發布于2019-08-23 10:41 / 3193人閱讀

摘要：快速排序遞歸分而治之通過一趟排序將要排序的數據分割成獨立的兩部分，然后再按此方法對這兩部分數據分別進行快速排序，每次返回一個有序數組。

arraySort 數組排序

這里為大家整理了一些簡單的數組排序的算法

冒泡排序 --- 比較兩個相鄰的元素，替換成正確的位置（你選擇的正序還是倒序） 快速排序 --- 基線條件 --- 只剩一個元素的時候就是有序的數組 選擇排序 --- 無序中選擇極值，進行排序 插入排序 --- 無序中循環，插入到有序中 冒泡排序

重復地走訪過要排序的元素列，一次比較兩個相鄰的元素，重復地進行直到沒有相鄰元素需要交換，也就是說該元素已經排序完成。這個算法的名字由來是因為越大的元素會經由交換慢慢“浮”到數列的頂端（升序或降序排列），就如同碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣，故名“冒泡排序”。

1. 從數組的第一項 **arr[0]** 項開始，與 **arr[1]** 進行對比，大的往后移動
2. 對每一個相鄰的元素，都進行以上操作，直到沒有相鄰元素進行對比,最后一對相鄰  **arr[length-2]-arr[length-1]** 
3. 兩兩對比一輪之后，發現數組最后一個元素是最大的
4. 每走一輪，大的元素都到冒泡到了最后面，所以 ***n個元素，n-1個循環（n-1輪）（n-1個外循環）***（最后第二輪結束的時候，最小的元素已經在最前面了） 
5. 每走一輪，最后的元素已經排好序，所以每走一輪，**比較相鄰元素的次數少了一次  arr.length-1-當前外循環 **

function bubbleSort(arr){
    var length = arr.length;
    for(var i = 0;iright){
                arr[j]=right;
                arr[j+1]=left;
            }
        }
    }
    return arr;
}

冒泡排序的優點：每進行一趟排序，就會少比較一次，因為每進行一趟排序都會找出一個較大值。

每進行一趟比較，每一趟少比較一次，一定程度上減少了算法的量。

快速排序 -遞歸-分而治之

通過一趟排序將要排序的數據分割成獨立的兩部分，然后再按此方法對這兩部分數據分別進行快速排序，每次返回一個有序數組。

1. 基數條件（不再進行遞歸的操作）：數組長度等于1
2. 遞歸條件：數組長度大于1
3. 選擇一個基準值 **base**
4. 大于基準值的放一邊，小于基準值的放一邊 **left right**
5. 分開的每邊 再次挑選基準值，重復3之后的步驟
6. 最后將返回的數組合并在一起

function quickSort(arr){
    if(arr.length<2){
        return arr;
    }
    var base = arr.splice(Math.floor(arr.length/2),1); //基準值
    var left = [];
    var right = [];
    for(var i=0;i

選擇排序    無序中選擇極值進行排序
1. 在數組中選擇出 ** 最小的一項 極值 **（也就是沒有排序的當中）
2. 將其插入到數組的開頭（有序的開頭）
3. 再把選出來的最小一項刪除掉
3. 上面兩部就行成了 （有序的開頭+無序的數組）
4. 每走一輪，前面的有序+1，后面的無序-1，所以，n個元素，***n-1輪*** 第n輪已經找不到無序的了

function selectSort(arr){
    var length = arr.length;
    for(var i = 0;i

插入排序 無序中循環，插入到有序中

1.假設**arr[0]**為有序的第一項，arr[0]之后的都為無序 （有序+無序）
2.從arr[0]之后無序進行循環,插入到**有序**相應的位置中
3.每走一輪，有序+1，無序-1

n.arr[n]和arr[n-1]對比，滿足 arr[n-1] > arr[n]， =>=> 在有序中找到相應的位置插入  


function insertSort(arr){
    var length = arr.length;
    for(var i = 1;iarr[i]){ //判斷能不能動，只要前面那一項比他大就能動
            for(var j = i-1;j>=0;j--){
                if(arr[j]>insert){ //前面那一項比他大，那么將前面那一項的位置記錄下來，
                    insertIndex = j;
                }
            }
            arr.splice(insertIndex,0,insert); //插入到前面去
            arr.splice(i+1,1); //原來位置上的刪除，因為插入了一項，要在原來的位置上加1
        }

    }
    return arr;
}

再來對比一下這四個排序


ms  數組長度
6
10
3000



冒泡排序
0.19
0.56
19.6


快速排序
0.28
0.29
0.27


選擇排序
0.22
0.82
12.6


插入排序
0.34
0.44
11



數組越長，快速排序>插入排序>選擇排序>冒泡排序

ms 數組長度	6	10	3000
冒泡排序	0.19	0.56	19.6
快速排序	0.28	0.29	0.27
選擇排序	0.22	0.82	12.6
插入排序	0.34	0.44	11

GPU云服務器云服務器最簡單的排序算法字符串排序數組排序算法數組排序算法c語言簡單的c語言排序

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

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

【算法日積月累】1-選擇排序

摘要：選擇排序算法實現實現選擇排序，記錄最小元素的索引，最后才交換位置說明交換兩個數組中的元素，在中有更簡單的寫法，這是的語法糖，其它語言中是沒有的。和語言中比較器的實現前面我們說到了，我們為了突出排序算法的思想，將所有的例子僅限在數組排序中。 showImg(https://segmentfault.com/img/remote/1460000017909538?w=1949&h=1080...

neuSnail 2019-07-31 11:21 評論0 收藏0
歸并排序 - Algorithms, Part I, week 3 MERGESORTS

摘要：兩個單元素數組的合并實際就是對這兩個數進行了排序，即變為，同樣再對后一組的兩個數歸并排序，即變為，再將兩單元數組歸并成四單元數組即和歸并為。前言本周講解兩個50多年前發明，但今天仍然很重要的經典算法 (歸并排序和快速排序) 之一 -- 歸并排序，幾乎每個軟件系統中都可以找到其中一個或兩個的實現，并研究這些經典方法的新變革。我們的涉及范圍從數學模型中解釋為什么這些方法有效到使這些算法...

Jokcy 2019-08-19 11:35 評論0 收藏0
JavaScript數據結構和算法

摘要：棧被稱為一種后入先出的數據結構。散列使用的數據結構叫做散列表。這些操作需要求助于其他數據結構，比如下面介紹的二叉查找樹。前言在過去的幾年中，得益于Node.js的興起，JavaScript越來越廣泛地用于服務器端編程。鑒于JavaScript語言已經走出了瀏覽器，程序員發現他們需要更多傳統語言（比如C++和Java）提供的工具。這些工具包括傳統的數據結構（如鏈表，棧，隊列，圖等），...

EastWoodYang 2019-08-21 16:23 評論0 收藏0
一些前端算法詳解 --- (不定時更新)

摘要：也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法。該方法因於年提出而得名。前言因為比較隨心所欲,所以我不按難度分享算法,所以你們會看到有時候順序有變化,因為我發表的時候會按照難度修改下位置,盡量讓你們看的時候能從簡單開始,以后每次更新都加個更新時間好了,讓你們知道我進度.新增計時函數直觀對比效率并且因為資料比較雜,很多都是我個人理解說法,如果有發...

Baaaan 2019-08-26 10:35 評論0 收藏0