經典排序演算法
❶ Java的幾種經典排序演算法
冒泡
二分法
Math.sort直接排序
拿著名稱去網路就行了
❷ 如何在現代C中實現經典排序演算法
冒泡法大家都較熟悉。其原理為從a[0]開始，依次將其和後面的元素比較,若a[0]>a[i]，則交換它們，一直比較到a[n]。同理對a[1],a[2],...a[n-1]處理，即完成排序。下面列出其代碼：
void bubble(int *a,int n) /*定義兩個參數：數組首地址與數組大小*/
{
int i,j,temp;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++) /*注意循環的上下限*/
if(a[i]>a[j]) {
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
冒泡法原理簡單，但其缺點是交換次數多，效率低。
下面介紹一種源自冒泡法但更有效率的方法「選擇法」。
（2）「選擇法」
選擇法循環過程與冒泡法一致，它還定義了記號k=i,然後依次把a[k]同後面元素比較，若a[k]>a[j],則使k=j.最後看看k=i是否還成立，不成立則交換a[k],a[i],這樣就比冒泡法省下許多無用的交換，提高了效率。
void choise(int *a,int n)
{
int i,j,k,temp;
for(i=0;i<n-1;i++) {
k=i; /*給記號賦值*/
for(j=i+1;j<n;j++)
if(a[k]>a[j]) k=j; /*是k總是指向最小元素*/
if(i!=k) { /*當k!=i是才交換，否則a[i]即為最小*/
temp=a[i];
a[i]=a[k];
a[k]=temp;
}
}
}
選擇法比冒泡法效率更高，但說到高效率，非「快速法」莫屬，現在就讓我們來了解它。
（3）「快速法」
快速法定義了三個參數，（數組首地址*a,要排序數組起始元素下標i,要排序數組結束元素下標j). 它首先選一個數組元素（一般為a[(i+j)/2],即中間元素）作為參照，把比它小的元素放到它的左邊，比它大的放在右邊。然後運用遞歸，在將它左，右兩個子數組排序，最後完成整個數組的排序。下面分析其代碼：
void quick(int *a,int i,int j)
{
int m,n,temp;
int k;
m=i;
n=j;
k=a[(i+j)/2]; /*選取的參照*/
do {
while(a[m]<k&&m<j) m++; /* 從左到右找比k大的元素*/
while(a[n]>k&&n>i) n--; /* 從右到左找比k小的元素*/
if(m<=n) { /*若找到且滿足條件，則交換*/
temp=a[m];
a[m]=a[n];
a[n]=temp;
m++;
n--;
}
}while(m<=n);
if(m<j) quick(a,m,j); /*運用遞歸*/
if(n>i) quick(a,i,n);
}
（4）「插入法」
插入法是一種比較直觀的排序方法。它首先把數組頭兩個元素排好序，再依次把後面的元素插入適當的位置。把數組元素插完也就完成了排序。
void insert(int *a,int n)
{
int i,j,temp;
for(i=1;i<n;i++) {
temp=a[i]; /*temp為要插入的元素*/
j=i-1;
while(j>=0&&temp<a[j]) { /*從a[i-1]開始找比a[i]小的數，同時把數組元素向後移*/
a[j+1]=a[j];
j--;
}
a[j+1]=temp; /*插入*/
}
}
（5）「shell法」
shell法是一個叫 shell 的美國人與1969年發明的。它首先把相距k(k>=1)的那幾個元素排好序，再縮小k值（一般取其一半），再排序，直到k=1時完成排序。下面讓我們來分析其代碼：
void shell(int *a,int n)
{
int i,j,k,x;
k=n/2; /*間距值*/
while(k>=1) {
for(i=k;i<n;i++) {
x=a[i];
j=i-k;
while(j>=0&&x<a[j]) {
a[j+k]=a[j];
j-=k;
}
a[j+k]=x;
}
k/=2; /*縮小間距值*/
}
}
上面我們已經對幾種排序法作了介紹，現在讓我們寫個主函數檢驗一下。
#include<stdio.h>
/*別偷懶，下面的"..."代表函數體，自己加上去哦！*/
void bubble(int *a,int n)
{
...
}
void choise(int *a,int n)
{
...
}
void quick(int *a,int i,int j)
{
...
}
void insert(int *a,int n)
{
...
}
void shell(int *a,int n)
{
...
}
/*為了列印方便，我們寫一個print吧。*/[code]
void print(int *a,int n)
{
int i;
for(i=0;i<n;i++)
printf("%5d",a[i]);
printf("\n");
}
main()
{ /*為了公平，我們給每個函數定義一個相同數組*/
int a1[]={13,0,5,8,1,7,21,50,9,2};
int a2[]={13,0,5,8,1,7,21,50,9,2};
int a3[]={13,0,5,8,1,7,21,50,9,2};
int a4[]={13,0,5,8,1,7,21,50,9,2};
int a5[]={13,0,5,8,1,7,21,50,9,2};
printf("the original list:");
print(a1,10);
printf("according to bubble:");
bubble(a1,10);
print(a1,10);
printf("according to choise:");
choise(a2,10);
print(a2,10);
printf("according to quick:");
quick(a3,0,9);
print(a3,10);
printf("according to insert:");
insert(a4,10);
print(a4,10);
printf("according to shell:");
shell(a5,10);
print(a5,10);
}
❸ 除了經典和常用的排序演算法外，還有哪些奇葩而有趣的排序演算法
排序演算法有：
冒泡排序（bubble sort） — O(n^2）
雞尾酒排序(Cocktail sort，雙向的冒泡排序) — O(n^2）
插入排序（insertion sort）— O(n^2)
桶排序（bucket sort）— O(n); 需要 O(k) 額外空間
計數排序(counting sort) — O(n+k); 需要 O(n+k) 額外空間
合並排序（merge sort）— O(nlog n); 需要 O(n) 額外空間
原地合並排序— O(n^2)
二叉排序樹排序 （Binary tree sort） — O(nlog n)期望時間； O(n^2)最壞時間； 需要 O(n) 額外空間
鴿巢排序(Pigeonhole sort) — O(n+k); 需要 O(k) 額外空間
基數排序（radix sort）— O(n·k); 需要 O(n) 額外空間
Gnome 排序— O(n^2)
圖書館排序— O(nlog n) with high probability，需要 （1+ε)n額外空間
不穩定的
選擇排序（selection sort）— O(n^2)
希爾排序（shell sort）— O(nlog n) 如果使用最佳的現在版本
組合排序— O(nlog n)
堆排序（heapsort）— O(nlog n)
平滑排序— O(nlog n)
快速排序（quicksort）— O(nlog n) 期望時間，O(n^2) 最壞情況； 對於大的、亂數列表一般相信是最快的已知排序
Introsort— O(nlog n)
Patience sorting— O(nlog n+ k) 最壞情況時間，需要 額外的 O(n+ k) 空間，也需要找到最長的遞增子串列（longest increasing subsequence）
不實用的
Bogo排序— O(n× n!) 期望時間，無窮的最壞情況。
Stupid sort— O(n^3); 遞歸版本需要 O(n^2) 額外存儲器
珠排序（Bead sort） — O(n) or O（√n)，但需要特別的硬體
Pancake sorting— O(n)，但需要特別的硬體
stooge sort——O（n^2.7）很漂亮但是很耗時
❹ 除了經典和常用的排序演算法外，還有哪些奇葩而有
猴子排序，隨機打亂，當剛好排好序的時候停止運行，復雜度為O(n！)
❺ 兩兩比較大小排序法是8種排序演算法的哪一種啊
是 冒泡排序法，復習一下：若記錄序列的初始狀態為"正序"，則冒泡排序過程只需進行一趟排序，在排序過程中只需進行n-1次比較，且不移動記錄；反之，若記錄序列的初始狀態為"逆序"，則需進行n(n-1）/2次比較和記錄移動。因此冒泡排序總的時間復雜度為O(n*n)。
❻ C語言中有哪些經典的排序方法
選擇排序的原理是，每次從待排序數字中挑選出最大（最小）數字，放在有序序列的末尾。實際操作中，只需要在這個數組中將挑出來的數字與前面的數字交換即可。
例如：
4
1 5
2 3
找到最小的1，1和4交換
1
4 5
2
3
找到最小的2，2和4交換
1
2
5
4
3
找到最小的3，3和5交換
1
2
3
4
5
找到最小的4，4和4交換（不交換也可）
可見，選擇排序需要一個雙重循環來完成，因此它的復雜度是o(n^2)
在數據量比較大時，不建議使用這種排序方法。
其他排序方法有很多，你甚至可以自己根據不同數據規模設計不同的排序方法。比較常見的有冒泡排序，插入排序（這兩種和選擇排序一樣，都是o(n^2)），二分法插入排序（降低了一些復雜度，但是涉及到大規模數據移動，效率依然不高），快速排序（平均復雜度o(nlogn)，但是不穩定，最壞情況o(n^2)），隨機化快速排序（很大程度上避免了最壞情況的出現），堆排序（o(nlogn)，編程復雜度高），基數排序（理論復雜度o(n)，實際要比這個慢。甚至能應付字元串排序，但是編程復雜度高，牽扯到其他數據結構），桶排序（o(n)，編程簡單，效率高，但是應付的數據范圍不能太大，受到內存大小的限制）。
平時比較常用的就是快速排序，程序簡單，效率也可以接受。
這是我了解的一些東西，希望對你有幫助。
❼ 搜索引擎的排序演算法都有哪些是怎麼實現的
2.1基於詞頻統計——詞位置加權的搜索引擎
利用關鍵詞在文檔中出現的頻率和位置排序是搜索引擎最早期排序的主要思想，其技術發展也最為成熟，是第一階段搜索引擎的主要排序技術，應用非常廣泛，至今仍是許多搜索引擎的核心排序技術。其基本原理是：關鍵詞在文檔中詞頻越高，出現的位置越重要，則被認為和檢索詞的相關性越好。
1）詞頻統計
文檔的詞頻是指查詢關鍵詞在文檔中出現的頻率。查詢關鍵詞詞頻在文檔中出現的頻率越高，其相關度越大。但當關鍵詞為常用詞時，使其對相關性判斷的意義非常小。TF/IDF很好的解決了這個問題。TF/IDF演算法被認為是信息檢索中最重要的發明。TF（Term Frequency）：單文本詞彙頻率，用關鍵詞的次數除以網頁的總字數，其商稱為「關鍵詞的頻率」。IDF（Inverse Document Frequency）：逆文本頻率指數，其原理是，一個關鍵詞在N個網頁中出現過，那麼N越大，此關鍵詞的權重越小，反之亦然。當關鍵詞為常用詞時，其權重極小，從而解決詞頻統計的缺陷。
2）詞位置加權
在搜索引擎中，主要針對網頁進行詞位置加權。所以，頁面版式信息的分析至關重要。通過對檢索關鍵詞在Web頁面中不同位置和版式，給予不同的權值，從而根據權值來確定所搜索結果與檢索關鍵詞相關程度。可以考慮的版式信息有：是否是標題，是否為關鍵詞，是否是正文，字體大小，是否加粗等等。同時，錨文本的信息也是非常重要的，它一般能精確的描述所指向的頁面的內容。
2.2基於鏈接分析排序的第二代搜索引擎
鏈接分析排序的思想起源於文獻引文索引機制，即論文被引用的次數越多或被越權威的論文引用，其論文就越有價值。鏈接分析排序的思路與其相似，網頁被別的網頁引用的次數越多或被越權威的網頁引用，其價值就越大。被別的網頁引用的次數越多，說明該網頁越受歡迎，被越權威的網頁引用，說明該網頁質量越高。鏈接分析排序演算法大體可以分為以下幾類：基於隨機漫遊模型的，比如PageRank和Repution演算法；基於概率模型的，如SALSA、PHITS；基於Hub和Authority相互加強模型的，如HITS及其變種；基於貝葉斯模型的，如貝葉斯演算法及其簡化版本。所有的演算法在實際應用中都結合傳統的內容分析技術進行了優化。本文主要介紹以下幾種經典排序演算法：
1）PageRank演算法
PageRank演算法由斯坦福大學博士研究生Sergey Brin和Lwraence Page等提出的。PageRank演算法是Google搜索引擎的核心排序演算法，是Google成為全球最成功的搜索引擎的重要因素之一，同時開啟了鏈接分析研究的熱潮。
PageRank演算法的基本思想是：頁面的重要程度用PageRank值來衡量，PageRank值主要體現在兩個方面：引用該頁面的頁面個數和引用該頁面的頁面重要程度。一個頁面P（A）被另一個頁面P（B）引用，可看成P（B）推薦P（A），P（B）將其重要程度（PageRank值）平均的分配P（B）所引用的所有頁面，所以越多頁面引用P（A），則越多的頁面分配PageRank值給P（A），PageRank值也就越高，P（A）越重要。另外，P(B)越重要，它所引用的頁面能分配到的PageRank值就越多，P（A）的PageRank值也就越高，也就越重要。
其計算公式為：
PR（A）：頁面A的PageRank值；
d：阻尼系數，由於某些頁面沒有入鏈接或者出鏈接，無法計算PageRank值，為避免這個問題（即LinkSink問題），而提出的。阻尼系數常指定為0.85。
R（Pi）：頁面Pi的PageRank值；
C（Pi）：頁面鏈出的鏈接數量；
PageRank值的計算初始值相同，為了不忽視被重要網頁鏈接的網頁也是重要的這一重要因素，需要反復迭代運算，據張映海撰文的計算結果，需要進行10次以上的迭代後鏈接評價值趨於穩定，如此經過多次迭代，系統的PR值達到收斂。
PageRank是一個與查詢無關的靜態演算法，因此所有網頁的PageRank值均可以通過離線計算獲得。這樣，減少了用戶檢索時需要的排序時間，極大地降低了查詢響應時間。但是PageRank存在兩個缺陷：首先PageRank演算法嚴重歧視新加入的網頁，因為新的網頁的出鏈接和入鏈接通常都很少，PageRank值非常低。另外PageRank演算法僅僅依靠外部鏈接數量和重要度來進行排名，而忽略了頁面的主題相關性，以至於一些主題不相關的網頁（如廣告頁面）獲得較大的PageRank值，從而影響了搜索結果的准確性。為此，各種主題相關演算法紛紛涌現，其中以以下幾種演算法最為典型。
2）Topic-Sensitive PageRank演算法
由於最初PageRank演算法中是沒有考慮主題相關因素的，斯坦福大學計算機科學系Taher Haveli-wala提出了一種主題敏感（Topic-Sensitive）的PageRank演算法解決了「主題漂流」問題。該演算法考慮到有些頁面在某些領域被認為是重要的，但並不表示它在其它領域也是重要的。
網頁A鏈接網頁B，可以看作網頁A對網頁B的評分，如果網頁A與網頁B屬於相同主題，則可認為A對B的評分更可靠。因為A與B可形象的看作是同行，同行對同行的了解往往比不是同行的要多，所以同行的評分往往比不是同行的評分可靠。遺憾的是TSPR並沒有利用主題的相關性來提高鏈接得分的准確性。
3）HillTop演算法
HillTop是Google的一個工程師Bharat在2001年獲得的專利。HillTop是一種查詢相關性鏈接分析演算法，克服了的PageRank的查詢無關性的缺點。HillTop演算法認為具有相同主題的相關文檔鏈接對於搜索者會有更大的價值。在Hilltop中僅考慮那些用於引導人們瀏覽資源的專家頁面（Export Sources）。Hilltop在收到一個查詢請求時，首先根據查詢的主題計算出一列相關性最強的專家頁面，然後根據指向目標頁面的非從屬專家頁面的數量和相關性來對目標頁面進行排序。
HillTop演算法確定網頁與搜索關鍵詞的匹配程度的基本排序過程取代了過分依靠PageRank的值去尋找那些權威頁面的方法，避免了許多想通過增加許多無效鏈接來提高網頁PageRank值的作弊方法。HillTop演算法通過不同等級的評分確保了評價結果對關鍵詞的相關性，通過不同位置的評分確保了主題（行業）的相關性，通過可區分短語數防止了關鍵詞的堆砌。
但是，專家頁面的搜索和確定對演算法起關鍵作用，專家頁面的質量對演算法的准確性起著決定性作用，也就忽略了大多數非專家頁面的影響。專家頁面在互聯網中占的比例非常低（1.79%），無法代表互聯網全部網頁，所以HillTop存在一定的局限性。同時，不同於PageRank演算法，HillTop演算法的運算是在線運行的，對系統的響應時間產生極大的壓力。
4）HITS
HITS（Hyperlink Inced Topic Search）演算法是Kleinberg在1998年提出的，是基於超鏈接分析排序演算法中另一個最著名的演算法之一。該演算法按照超鏈接的方向，將網頁分成兩種類型的頁面：Authority頁面和Hub頁面。Authority頁面又稱權威頁面，是指與某個查詢關鍵詞和組合最相近的頁面，Hub頁面又稱目錄頁，該頁面的內容主要是大量指向Authority頁面的鏈接，它的主要功能就是把這些Authority頁面聯合在一起。對於Authority頁面P，當指向P的Hub頁面越多，質量越高，P的Authority值就越大；而對於Hub頁面H，當H指向的Authority的頁面越多，Authority頁面質量越高，H的Hub值就越大。對整個Web集合而言，Authority和Hub是相互依賴、相互促進，相互加強的關系。Authority和Hub之間相互優化的關系，即為HITS演算法的基礎。
HITS基本思想是：演算法根據一個網頁的入度（指向此網頁的超鏈接）和出度（從此網頁指向別的網頁）來衡量網頁的重要性。在限定范圍之後根據網頁的出度和入度建立一個矩陣，通過矩陣的迭代運算和定義收斂的閾值不斷對兩個向量Authority和Hub值進行更新直至收斂。
實驗數據表明，HITS的排名准確性要比PageRank高，HITS演算法的設計符合網路用戶評價網路資源質量的普遍標准，因此能夠為用戶更好的利用網路信息檢索工具訪問互聯網資源帶來便利。
但卻存在以下缺陷：首先，HITS演算法只計算主特徵向量，處理不好主題漂移問題；其次，進行窄主題查詢時，可能產生主題泛化問題；第三，HITS演算法可以說一種實驗性質的嘗試。它必須在網路信息檢索系統進行面向內容的檢索操作之後，基於內容檢索的結果頁面及其直接相連的頁面之間的鏈接關系進行計算。盡管有人嘗試通過演算法改進和專門設立鏈接結構計算伺服器（Connectivity Server）等操作，可以實現一定程度的在線實時計算，但其計算代價仍然是不可接受的。
2.3基於智能化排序的第三代搜索引擎
排序演算法在搜索引擎中具有特別重要的地位，目前許多搜索引擎都在進一步研究新的排序方法，來提升用戶的滿意度。但目前第二代搜索引擎有著兩個不足之處，在此背景下，基於智能化排序的第三代搜索引擎也就應運而生。
1）相關性問題
相關性是指檢索詞和頁面的相關程度。由於語言復雜，僅僅通過鏈接分析及網頁的表面特徵來判斷檢索詞與頁面的相關性是片面的。例如：檢索「稻瘟病」，有網頁是介紹水稻病蟲害信息的，但文中沒有「稻瘟病」這個詞，搜索引擎根本無法檢索到。正是以上原因，造成大量的搜索引擎作弊現象無法解決。解決相關性的的方法應該是增加語意理解，分析檢索關鍵詞與網頁的相關程度，相關性分析越精準，用戶的搜索效果就會越好。同時，相關性低的網頁可以剔除，有效地防止搜索引擎作弊現象。檢索關鍵詞和網頁的相關性是在線運行的，會給系統相應時間很大的壓力，可以採用分布式體系結構可以提高系統規模和性能。
2）搜索結果的單一化問題
在搜索引擎上，任何人搜索同一個詞的結果都是一樣。這並不能滿足用戶的需求。不同的用戶對檢索的結果要求是不一樣的。例如：普通的農民檢索「稻瘟病」，只是想得到稻瘟病的相關信息以及防治方法，但農業專家或科技工作者可能會想得到稻瘟病相關的論文。
解決搜索結果單一的方法是提供個性化服務，實現智能搜索。通過Web數據挖掘，建立用戶模型（如用戶背景、興趣、行為、風格），提供個性化服務。