熱線電話:0755-23712116
郵箱:contact@shuangyi-tech.com
地址:深圳市寶安區(qū)沙井街道后亭茅洲山工業(yè)園工業(yè)大廈全至科技創(chuàng)新園科創(chuàng)大廈2層2A
0.3 相關(guān)概念
內(nèi)執(zhí)行時所需存儲空間的度量,它也是數(shù)據(jù)規(guī)模n的函數(shù)。
冒泡排序是一種簡單的排序算法。它重復(fù)地走訪過要排序的數(shù)列,一次比較兩個元素,如果它們的順序錯誤就把它們交換過來。走訪數(shù)列的工作是重復(fù)地進行直到?jīng)]有再需要交換,也就是說該數(shù)列已經(jīng)排序完成。這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端。
1.2 動圖演示
選擇排序(Selection-sort)是一種簡單直觀的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰?,然后放到已排序序列的末尾。以此類推,直到所有元素均排序完畢。
n個記錄的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果。具體算法描述如下:
表現(xiàn)最穩(wěn)定的排序算法之一,因為無論什么數(shù)據(jù)進去都是O(n2)的時間復(fù)雜度,所以用到它的時候,數(shù)據(jù)規(guī)模越小越好。唯一的好處可能就是不占用額外的內(nèi)存空間了吧。理論上講,選擇排序可能也是平時排序一般人想到的最多的排序方法了吧。
插入排序(Insertion-Sort)的算法描述是一種簡單直觀的排序算法。它的工作原理是通過構(gòu)建有序序列,對于未排序數(shù)據(jù),在已排序序列中從后向前掃描,找到相應(yīng)位置并插入。
一般來說,插入排序都采用in-place在數(shù)組上實現(xiàn)。具體算法描述如下:
插入排序在實現(xiàn)上,通常采用in-place排序(即只需用到O(1)的額外空間的排序),因而在從后向前掃描過程中,需要反復(fù)把已排序元素逐步向后挪位,為最新元素提供插入空間。
1959年Shell發(fā)明,第一個突破O(n2)的排序算法,是簡單插入排序的改進版。它與插入排序的不同之處在于,它會優(yōu)先比較距離較遠的元素。希爾排序又叫縮小增量排序。
先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序,具體算法描述:
希爾排序的核心在于間隔序列的設(shè)定。既可以提前設(shè)定好間隔序列,也可以動態(tài)的定義間隔序列。動態(tài)定義間隔序列的算法是《算法(第4版)》的合著者Robert Sedgewick提出的?!?/p>