排序演算法解析

⑴ JS常見排序演算法

排序演算法說明:

（1）對於評述演算法優劣術語的說明

穩定 ：如果a原本在b前面，而a=b，排序之後a仍然在b的前面；

不穩定 ：如果a原本在b的前面，而a=b，排序之後a可能會出現在b的後面；

內排序 ：所有排序操作都在內存中完成；

外排序 ：由於數據太大，因此把數據放在磁碟中，而排序通過磁碟和內存的數據傳輸才能進行；

時間復雜度 : 一個演算法執行所耗費的時間。

空間復雜度 : 運行完一個程序所需內存的大小。

(2)排序演算法圖片總結:

1.冒泡排序:

解析：1.比較相鄰的兩個元素，如果前一個比後一個大，則交換位置。

2.第一輪的時候最後一個元素應該是最大的一個。

3.按照步驟一的方法進行相鄰兩個元素的比較，這個時候由於最後一個元素已經是最大的了，所以最後一個元素不用比較。

2.快速排序:

解析：快速排序是對冒泡排序的一種改進，第一趟排序時將數據分成兩部分，一部分比另一部分的所有數據都要小。然後遞歸調用，在兩邊都實行快速排序。

3.插入排序:

解析：

 （1） 從第一個元素開始，該元素可以認為已經被排序

 （2） 取出下一個元素，在已經排序的元素序列中從後向前掃描

 （3） 如果該元素（已排序）大於新元素，將該元素移到下一位置

 （4） 重復步驟3，直到找到已排序的元素小於或者等於新元素的位置

 （5）將新元素插入到下一位置中

 （6） 重復步驟2

2.二分查找:

解析：二分查找，也為折半查找。首先要找到一個中間值，通過與中間值比較，大的放又，小的放在左邊。再在兩邊中尋找中間值，持續以上操作，直到找到所在位置為止。

（1）遞歸方法

（2）非遞歸方法

4.選擇排序:

解析:首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。

以此類推，直到所有元素均排序完畢。

5.希爾排序:

解析:先將整個待排序的記錄序列分割成為若乾子序列分別進行直接插入排序

6.歸並排序:

解析:歸並排序是一種穩定的排序方法。將已有序的子序列合並，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。

7.堆排序:

解析:堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序演算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是

小於（或者大於）它的父節點。

8.計數排序:

 解析:計數排序使用一個額外的數組C，其中第i個元素是待排序數組A中值等於i的元素的個數。然後根據數組C來將A中的元素排到正確的位置。它只能對整數進行排序。

9.桶排序:

解析:假設輸入數據服從均勻分布，將數據分到有限數量的桶里，每個桶再分別排序（有可能再使用別的排序演算法或是以遞歸方式繼續使用桶排序進行排

10.基數排序:

解析:基數排序是按照低位先排序，然後收集；再按照高位排序，然後再收集；依次類推，直到最高位。有時候有些屬性是有優先順序順序的，先按低優先順序排序，再按高優

先級排序。最後的次序就是高優先順序高的在前，高優先順序相同的低優先順序高的在前。基數排序基於分別排序，分別收集，所以是穩定的。

基數排序 vs 計數排序 vs 桶排序

這三種排序演算法都利用了桶的概念，但對桶的使用方法上有明顯差異：

基數排序：根據鍵值的每位數字來分配桶 計數排序：每個桶只存儲單一鍵值 桶排序：每個桶存儲一定范圍的數值

⑵ Python實現的快速排序演算法詳解

Python實現的快速排序演算法詳解
本文實例講述了Python實現的快速排序演算法。分享給大家供大家參考，具體如下：
快速排序基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
如序列[6，8，1，4，3，9]，選擇6作為基準數。從右向左掃描，尋找比基準數小的數字為3，交換6和3的位置，[3，8，1，4，6，9]，接著從左向右掃描，尋找比基準數大的數字為8，交換6和8的位置，[3，6，1，4，8，9]。重復上述過程，直到基準數左邊的數字都比其小，右邊的數字都比其大。然後分別對基準數左邊和右邊的序列遞歸進行上述方法。
實現代碼如下：
def parttion(v, left, right):
key = v[left]
low = left
high = right
while low < high:
while (low < high) and (v[high] >= key):
high -= 1
v[low] = v[high]
while (low < high) and (v[low] <= key):
low += 1
v[high] = v[low]
v[low] = key
return low
def quicksort(v, left, right):
if left < right:
p = parttion(v, left, right)
quicksort(v, left, p-1)
quicksort(v, p+1, right)
return v
s = [6, 8, 1, 4, 3, 9, 5, 4, 11, 2, 2, 15, 6]
print("before sort:",s)
s1 = quicksort(s, left = 0, right = len(s) - 1)
print("after sort:",s1)
運行結果：
before sort: [6, 8, 1, 4, 3, 9, 5, 4, 11, 2, 2, 15, 6]
after sort: [1, 2, 2, 3, 4, 4, 5, 6, 6, 8, 9, 11, 15]

⑶ java中冒泡排序演算法的詳細解答以及程序

實例說明

用冒泡排序方法對數組進行排序。

實例解析

交換排序的基本思想是兩兩比較待排序記錄的關鍵字，發現兩個記錄的次序相反時即進行交換，直到沒有反序的記錄為止。

應用交換排序基本思想的主要排序方法有冒泡排序和快速排序。

冒泡排序

將被排序的記錄數組 R[1..n] 垂直排列，每個記錄 R[i] 看做是重量為 R[i].key 的氣泡。根據輕氣泡不能在重氣泡之下的原則，從下往上掃描數組 R 。凡掃描到違反本原則的輕氣泡，就使其向上「漂浮」。如此反復進行，直到最後任何兩個氣泡都是輕者在上，重者在下為止。

(1) 初始， R[1..n] 為無序區。

(2) 第一趟掃描，從無序區底部向上依次比較相鄰的兩個氣泡的重量，若發現輕者在下、重者在上，則交換二者的位置。即依次比較 (R[n],R[n-1]) 、 (R[n-1],R[n-2]) 、 … 、 (R[2],R[1]); 對於每對氣泡 (R[j+1],R[j]), 若 R[j+1].key<R[j].key, 則交換 R[j+1] 和 R[j] 的內容。

第一趟掃描完畢時，「最輕」的氣泡就飄浮到該區間的頂部，即關鍵字最小的記錄被放在最高位置 R[1] 上。

(3) 第二趟掃描，掃描 R[2..n]。掃描完畢時，「次輕」的氣泡飄浮到 R[2] 的位置上 …… 最後，經過 n-1 趟掃描可得到有序區 R[1..n]。

注意：第 i 趟掃描時， R[1..i-1] 和 R[i..n] 分別為當前的有序區和無序區。掃描仍是從無序區底部向上直至該區頂部。掃描完畢時，該區中最輕氣泡漂浮到頂部位置 R[i] 上，結果是 R[1..i] 變為新的有序區。

冒泡排序演算法

因為每一趟排序都使有序區增加了一個氣泡，在經過 n-1 趟排序之後，有序區中就有 n-1 個氣泡，而無序區中氣泡的重量總是大於等於有序區中氣泡的重量，所以整個冒泡排序過程至多需要進行 n-1 趟排序。

若在某一趟排序中未發現氣泡位置的交換，則說明待排序的無序區中所有氣泡均滿足輕者在上，重者在下的原則，因此，冒泡排序過程可在此趟排序後終止。為此，在下面給出的演算法中，引入一個布爾量 exchange, 在每趟排序開始前，先將其置為 FALSE 。若排序過程中發生了交換，則將其置為 TRUE 。各趟排序結束時檢查 exchange, 若未曾發生過交換則終止演算法，不再進行下趟排序。

具體演算法如下：

void BubbleSort(SeqList R){
//R(1..n) 是待排序的文件，採用自下向上掃描，對 R 做冒泡排序
int i,j;
Boolean exchange; // 交換標志
for(i=1;i<n;i++){ // 最多做 n-1 趟排序
exchange=FALSE; // 本趟排序開始前，交換標志應為假
for(j=n-1;j>=i;j--) // 對當前無序區 R[i..n] 自下向上掃描
if(R[j+1].key<R[j].key){ // 交換記錄
R[0]=R[j+1]; //R[0] 不是哨兵，僅做暫存單元
R[j+1]=R[j];
R[j]=R[0];
exchange=TRUE; // 發生了交換，故將交換標志置為真
}
if(!exchange) // 本趟排序未發生交換，提前終止演算法
return;
} //endfor( 外循環 )
}//BubbleSort

publicclassBubbleSort{

publicstaticvoidmain(String[]args){
//TODOAuto-generatedmethodstub
List<Integer>lstInteger=newArrayList<Integer>();
lstInteger.add(1);
lstInteger.add(1);
lstInteger.add(3);
lstInteger.add(2);
lstInteger.add(1);
for(inti=0;i<lstInteger.size();i++){
System.out.println(lstInteger.get(i));
}
System.out.println("排序之後-----------------");
lstInteger=sortList(lstInteger);
for(inti=0;i<lstInteger.size();i++){
System.out.println(lstInteger.get(i));
}

}

publicstaticList<Integer>sortList(List<Integer>lstInteger){
inti,j,m;
booleanblChange;
intn=lstInteger.size();

for(i=0;i<n;i++){
blChange=false;
for(j=n-1;j>i;j--){
if(lstInteger.get(j)<lstInteger.get(j-1)){
m=lstInteger.get(j-1);
lstInteger.set(j-1,lstInteger.get(j));
lstInteger.set(j,m);
blChange=true;
}
}
if(!blChange){
returnlstInteger;
}
}
returnlstInteger;
}
}
歸納注釋

演算法的最好時間復雜度:若文件的初始狀態是正序的,一趟掃描即可完成排序。所需的關鍵字比較次數C和記錄移動次數M均達到最小值，即C(min)=n-1,M(min)=0。冒泡排序最好的時間復雜度為O(n)。

演算法的最壞時間復雜度:若初始文件是反序的，需要進行n-1趟排序。每趟排序要進行n-1次關鍵字的比較(1<=i<=n-1),且每次比較都必須移動記錄3次。在這種情況下，比較和移動次數均達到最大值，即C(max)=n(n-1)/2=O(n^2)，M(max)=3n(n-1)/2=O(n^2)。冒泡排序的最壞時間復雜度為O(n^2)。

演算法的平均時間復雜度為O(n^2)。雖然冒泡排序不一定要進行n-1趟，但由於它的記錄移動次數較多，故平均時間性能比直接插入排序要差得多。

演算法穩定性：冒泡排序是就地排序，且它是穩定的。

演算法改進：上述的冒泡排序還可做如下的改進，①記住最後一次交換發生位置lastExchange的冒泡排序(該位置之前的相鄰記錄均已有序)。下一趟排序開始時，R[1..lastExchange-1]是有序區，R[lastExchange..n]是無序區。這樣，一趟排序可能使當前有序區擴充多個記錄，從而減少排序的趟數。②改變掃描方向的冒泡排序。冒泡排序具有不對稱性。能一趟掃描完成排序的情況，只有最輕的氣泡位於R[n]的位置，其餘的氣泡均已排好序，那麼也只需一趟掃描就可以完成排序。如對初始關鍵字序列12、18、42、44、45、67、94、10就僅需一趟掃描。需要n-1趟掃描完成排序情況，當只有最重的氣泡位於R[1]的位置，其餘的氣泡均已排好序時，則仍需做n-1趟掃描才能完成排序。比如對初始關鍵字序列：94、10、12、18、42、44、45、67就需7趟掃描。造成不對稱性的原因是每趟掃描僅能使最重氣泡「下沉」一個位置，因此使位於頂端的最重氣泡下沉到底部時，需做n-1趟掃描。在排序過程中交替改變掃描方向，可改進不對稱性

⑷ php幾種排序演算法實例詳解

四種排序演算法的PHP實現：
1)插入排序(InsertionSort)的基本思想是：
每次將一個待排序的記錄，按其關鍵字大小插入到前面已經排好序的子文件中的適當位置，直到全部記錄插入完成為止。

2)選擇排序(SelectionSort)的基本思想是：
每一趟從待排序的記錄中選出關鍵字最小的記錄，順序放在已排好序的子文件的最後，直到全部記錄排序完畢。

3)冒泡排序的基本思想是：
兩兩比較待排序記錄的關鍵字，發現兩個記錄的次序相反時即進行交換，直到沒有反序的記錄為止。

4)快速排序實質上和冒泡排序一樣，都是屬於交換排序的一種應用。所以基本思想和上面的冒泡排序是一樣的。

1.sort.php文件如下：

<?php
classSort{
private$arr=array();
private$sort='insert';
private$marker='_sort';
private$debug=TRUE;
/**
*構造函數
*
*@paramarray例如：
$config=array(
'arr'=>array(22,3,41,18),//需要排序的數組值
'sort'=>'insert',//可能值:insert,select,bubble,quick
'debug'=>TRUE//可能值:TRUE,FALSE
)
*/
publicfunctionconstruct($config=array()){
if(count($config)>0){
$this->_init($config);
}
}
/**
*獲取排序結果
*/
publicfunctiondisplay(){
return$this->arr;
}
/**
*初始化
*
*@paramarray
*@returnbool
*/
privatefunction_init($config=array()){
//參數判斷
if(!is_array($config)ORcount($config)==0){
if($this->debug===TRUE){
$this->_log("sort_init_param_invaild");
}
returnFALSE;
}
//初始化成員變數
foreach($configas$key=>$val){
if(isset($this->$key)){
$this->$key=$val;
}
}
//調用相應的成員方法完成排序
$method=$this->sort.$this->marker;
if(!method_exists($this,$method)){
if($this->debug===TRUE){
$this->_log("sort_method_invaild");
}
returnFALSE;
}
if(FALSE===($this->arr=$this->$method($this->arr)))
returnFALSE;
returnTRUE;
}
/**
*插入排序
*
*@paramarray
*@returnbool
*/
privatefunctioninsert_sort($arr){
//參數判斷
if(!is_array($arr)ORcount($arr)==0){
if($this->debug===TRUE){
$this->_log("sort_array(insert)_invaild");
}
returnFALSE;
}
//具體實現
$count=count($arr);
for($i=1;$i<$count;$i++){
$tmp=$arr[$i];
for($j=$i-1;$j>=0;$j--){
if($arr[$j]>$tmp){
$arr[$j+1]=$arr[$j];
$arr[$j]=$tmp;
}
}
}
return$arr;
}
/**
*選擇排序
*
*@paramarray
*@returnbool
*/
privatefunctionselect_sort($arr){
//參數判斷
if(!is_array($arr)ORcount($arr)==0){
if($this->debug===TRUE){
$this->_log("sort_array(select)_invaild");
}
returnFALSE;
}
//具體實現
$count=count($arr);
for($i=0;$i<$count-1;$i++){
$min=$i;
for($j=$i+1;$j<$count;$j++){
if($arr[$min]>$arr[$j])$min=$j;
}
if($min!=$i){
$tmp=$arr[$min];
$arr[$min]=$arr[$i];
$arr[$i]=$tmp;
}
}
return$arr;
}
/**
*冒泡排序
*
*@paramarray
*@returnbool
*/
privatefunctionbubble_sort($arr){
//參數判斷
if(!is_array($arr)ORcount($arr)==0){
if($this->debug===TRUE){
$this->_log("sort_array(bubble)_invaild");
}
returnFALSE;
}
//具體實現
$count=count($arr);
for($i=0;$i<$count;$i++){
for($j=$count-1;$j>$i;$j--){
if($arr[$j]<$arr[$j-1]){
$tmp=$arr[$j];
$arr[$j]=$arr[$j-1];
$arr[$j-1]=$tmp;
}
}
}
return$arr;
}
/**
*快速排序
*@bywww.5wx.org
*@paramarray
*@returnbool
*/
privatefunctionquick_sort($arr){
//具體實現
if(count($arr)<=1)return$arr;
$key=$arr[0];
$left_arr=array();
$right_arr=array();
for($i=1;$i<count($arr);$i++){
if($arr[$i]<=$key)
$left_arr[]=$arr[$i];
else
$right_arr[]=$arr[$i];
}
$left_arr=$this->quick_sort($left_arr);
$right_arr=$this->quick_sort($right_arr);

returnarray_merge($left_arr,array($key),$right_arr);
}
/**
*日誌記錄
*/
privatefunction_log($msg){
$msg='date['.date('Y-m-dH:i:s').']'.$msg.'
';
return@file_put_contents('sort_err.log',$msg,FILE_APPEND);
}
}
/*Endoffilesort.php*/
/*Locationhtdocs/sort.php*/
2.sort_demo.php文件如下：

<?php
require_once('sort.php');
$config=array(
'arr'=>array(23,22,41,18,20,12,200303,2200,1192),
//需要排序的數組值
'sort'=>'select',
//可能值:insert,select,bubble,quick
'debug'=>TRUE
//可能值:TRUE,FALSE
);
$sort=newSort($config);
//var_mp($config['arr']);
var_mp($sort->display());
/*Endofphp*/

⑸ 快速排序演算法在平均情況下的時間復雜度為 求詳解

時間復雜度為O(nlogn) n為元素個數
1. 快速排序的三個步驟：
1.1. 找到序列中用於劃分序列的元素
1.2. 用元素劃分序列
1.3. 對劃分後的兩個序列重復1,2兩個步驟指導序列無法再劃分
所以對於n個元素其排序時間為
T(n) = 2*T(n/2) + n （表示將長度為n的序列劃分為兩個子序列，每個子序列需要T(n/2)
的時間，而劃分序列需要n的時間）
而 T(1) = 1 （表示長度為1的序列無法劃分子序列，只需要1的時間即可）
T(n) = 2^logn + logn * n （n被不斷二分最終只能二分logn次（最優的情況,每次選取
的元素都均分序列））
= n + nlogn
因此T(n) = O(nlogn)
以上是最優情況的推導，因此快速排序在最優情況下其排序時間為O(nlogn),通常平均情況
我們也認為是此值。
在最壞情況下其會退化為冒泡排序，T(n) = T(n - 1) + n (每次選取的元素只能將序列劃分為
一段，即自身是 最小元素或最大元素)
因此T(n) = n * (n-1) / 2 相當於O(n^2)