.example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}.example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:0 0 5px 0;padding:5px;border:1px solid #d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc 100px);background-image:linear-gradient(#fff,#e5eecc 100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1px solid #d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1px solid #d4d4d4;width:98%}div.code{width:98%;border:1px solid #d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.code div{font-size:110%}div.code div,div.code p,div.example_code p{font-family:"courier new"}pre{margin:15px auto;font:12px/20px Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1px solid #ddd;border-left-width:4px;padding:10px 15px} 排序算法是《數(shù)據(jù)結(jié)構(gòu)與算法》中最基本的算法之一。排序算法可以分為內(nèi)部排序和外部排序,內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進行排序,而外部排序是因排序的數(shù)據(jù)很大,一次不能容納全部的排序記錄,在排序過程中需要訪問外存。常見的內(nèi)部排序算法有:插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。以下是快速排序算法:
公司專注于為企業(yè)提供成都網(wǎng)站建設(shè)、做網(wǎng)站、微信公眾號開發(fā)、商城網(wǎng)站建設(shè),微信小程序,軟件按需設(shè)計網(wǎng)站等一站式互聯(lián)網(wǎng)企業(yè)服務(wù)。憑借多年豐富的經(jīng)驗,我們會仔細了解各客戶的需求而做出多方面的分析、設(shè)計、整合,為客戶設(shè)計出具風(fēng)格及創(chuàng)意性的商業(yè)解決方案,成都創(chuàng)新互聯(lián)更提供一系列網(wǎng)站制作和網(wǎng)站推廣的服務(wù)。
快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下,排序 n 個項目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較,但這種狀況并不常見。事實上,快速排序通常明顯比其他 Ο(nlogn) 算法更快,因為它的內(nèi)部循環(huán)(inner loop)可以在大部分的架構(gòu)上很有效率地被實現(xiàn)出來。
快速排序使用分治法(Divide and conquer)策略來把一個串行(list)分為兩個子串行(sub-lists)。
快速排序又是一種分而治之思想在排序算法上的典型應(yīng)用。本質(zhì)上來看,快速排序應(yīng)該算是在冒泡排序基礎(chǔ)上的遞歸分治法。
快速排序的名字起的是簡單粗暴,因為一聽到這個名字你就知道它存在的意義,就是快,而且效率高!它是處理大數(shù)據(jù)最快的排序算法之一了。雖然 Worst Case 的時間復(fù)雜度達到了 O(n?),但是人家就是優(yōu)秀,在大多數(shù)情況下都比平均時間復(fù)雜度為 O(n logn) 的排序算法表現(xiàn)要更好,可是這是為什么呢,我也不知道。好在我的強迫癥又犯了,查了 N 多資料終于在《算法藝術(shù)與信息學(xué)競賽》上找到了滿意的答案:
快速排序的最壞運行情況是 O(n?),比如說順序數(shù)列的快排。但它的平攤期望時間是 O(nlogn),且 O(nlogn) 記號中隱含的常數(shù)因子很小,比復(fù)雜度穩(wěn)定等于 O(nlogn) 的歸并排序要小很多。所以,對絕大多數(shù)順序性較弱的隨機數(shù)列而言,快速排序總是優(yōu)于歸并排序。
1. 算法步驟
從數(shù)列中挑出一個元素,稱為 "基準"(pivot);
重新排序數(shù)列,所有元素比基準值小的擺放在基準前面,所有元素比基準值大的擺在基準的后面(相同的數(shù)可以到任一邊)。在這個分區(qū)退出之后,該基準就處于數(shù)列的中間位置。這個稱為分區(qū)(partition)操作;
遞歸地(recursive)把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序;
2. 動圖演示
代碼實現(xiàn) JavaScript 實例 function quickSort ( arr , left , right ) {
var len = arr. length ,
? ? partitionIndex ,
? ? left = typeof left != 'number' ? 0 : left ,
? ? right = typeof right != 'number' ? len - 1 : right ;
if ( left
給你介紹4種排序方法及源碼,供參考
1.冒泡排序
主要思路: 從前往后依次交換兩個相鄰的元素,大的交換到后面,這樣每次大的數(shù)據(jù)就到后面,每一次遍歷,最大的數(shù)據(jù)到達最后面,時間復(fù)雜度是O(n^2)。
public?static?void?bubbleSort(int[]?arr){
for(int?i?=0;?i??arr.length?-?1;?i++){
for(int?j=0;?j??arr.length-1;?j++){
if(arr[j]??arr[j+1]){
arr[j]?=?arr[j]^arr[j+1];
arr[j+1]?=?arr[j]^arr[j+1];
arr[j]?=?arr[j]^arr[j+1];
}
}
}
}
2.選擇排序
主要思路:每次遍歷序列,從中選取最小的元素放到最前面,n次選擇后,前面就都是最小元素的排列了,時間復(fù)雜度是O(n^2)。
public?static?void?selectSort(int[]?arr){
for(int?i?=?0;?i?arr.length?-1;?i++){
for(int?j?=?i+1;?j??arr.length;?j++){
if(arr[j]??arr[i]){
arr[j]?=?arr[j]^arr[i];
arr[i]?=?arr[j]^arr[i];
arr[j]?=?arr[j]^arr[i];
}
}
}
}
3.插入排序
主要思路:使用了兩層嵌套循環(huán),逐個處理待排序的記錄。每個記錄與前面已經(jīng)排好序的記錄序列進行比較,并將其插入到合適的位置,時間復(fù)雜度是O(n^2)。
public?static?void?insertionSort(int[]?arr){
int?j;
for(int?p?=?1;?p??arr.length;?p++){
int?temp?=?arr[p];???//保存要插入的數(shù)據(jù)
//將無序中的數(shù)和前面有序的數(shù)據(jù)相比,將比它大的數(shù),向后移動
for(j=p;?j0??temp?arr[j-1];?j--){
arr[j]?=?arr[j-1];
}
//正確的位置設(shè)置成保存的數(shù)據(jù)
arr[j]?=?temp;
}
}
4.希爾排序
主要思路:用步長分組,每個分組進行插入排序,再慢慢減小步長,當步長為1的時候完成一次插入排序,? 希爾排序的時間復(fù)雜度是:O(nlogn)~O(n2),平均時間復(fù)雜度大致是O(n^1.5)
public?static?void?shellSort(int[]?arr){
int?j?;
for(int?gap?=?arr.length/2;?gap??0?;?gap/=2){
for(int?i?=?gap;?i??arr.length;?i++){
int?temp?=?arr[i];
for(j?=?i;?j=gap??temparr[j-gap];?j-=gap){
arr[j]?=?arr[j-gap];
}
arr[j]?=?temp;
}
}
}
冒泡排序是比較經(jīng)典的排序算法。代碼如下:
for(int i=1;iarr.length;i++){
for(int j=1;jarr.length-i;j++){
//交換位置
} ? ?
拓展資料:
原理:比較兩個相鄰的元素,將值大的元素交換至右端。
思路:依次比較相鄰的兩個數(shù),將小數(shù)放在前面,大數(shù)放在后面。即在第一趟:首先比較第1個和第2個數(shù),將小數(shù)放前,大數(shù)放后。然后比較第2個數(shù)和第3個數(shù),將小數(shù)放前,大數(shù)放后,如此繼續(xù),直至比較最后兩個數(shù),將小數(shù)放前,大數(shù)放后。重復(fù)第一趟步驟,直至全部排序完成。
第一趟比較完成后,最后一個數(shù)一定是數(shù)組中最大的一個數(shù),所以第二趟比較的時候最后一個數(shù)不參與比較;
第二趟比較完成后,倒數(shù)第二個數(shù)也一定是數(shù)組中第二大的數(shù),所以第三趟比較的時候最后兩個數(shù)不參與比較;
依次類推,每一趟比較次數(shù)-1;
??
舉例說明:要排序數(shù)組:int[]?arr={6,3,8,2,9,1};?
for(int i=1;iarr.length;i++){
for(int j=1;jarr.length-i;j++){
//交換位置
} ? ?
參考資料:冒泡排序原理