排序演算法效率
① 幾種排序演算法效率的比較
插入排序，選擇排序，交換排序（冒泡），數據結構書上有詳細的介紹
以下是直接插入排序，選擇排序，希爾排序，冒泡排序的演算法
/*直接插入排序的基本思想是：順序地把待排序序
列中的各個記錄按其關鍵字的大小，插入到已排
序的序列的適當位置。
*/
void InsertSort(elemtype x[], int n)
{
int i,j;
elemtype s;
for(i=0;i<n-1;i )
{
s = x[i 1];
j = i;
while(j>-1 && s.key<x[j].key)
{
x[j 1] = x[j];
j--;
}
x[j 1]=s;
}
}
/*選擇排序的基本思想是：不斷從待排序的序列中
選取關鍵字最小的記錄放到已排序的記錄序列的
後面，知道序列中所有記錄都已排序為止。
*/
void SelectSort(elemtype x[], int n)
{
int i,j,Small;
elemtype Temp;
for(i=0;i<n-1;i )
{
Small = i;
for(j=i 1;j<n;j )
{
if(x[j].key<x[Small].key)
Small = j;
}
if(Small!=i)
{
Temp = x[i];
x[i] = x[Small];
x[Small] = Temp;
}
}
}
/*希爾排序的基本思想是：不斷把待排序的記錄分
成若干個小組，對同一組內的記錄進行排序，在
分組時，始終保證當前組內的記錄個數超過前面
分組排序時組內的記錄個數。
*/
void ShellSort(elemtype x[], int n, int d[], int Number)
{
int i, j, k, m, Span;
elemtype s;
for(m=0;m<Number;m )
{
Span = d[m];
for(k=0;k<Span;k )
{
for(i=k;i<n-Span;i =Span)
{
s = x[i Span];
j = i;
while(j>-1 && s.key<x[j].key)
{
x[j Span] = x[j];
j-=Span;
}
x[j Span] = s;
}
}
}
}
/*冒泡排序的基本思想是：將待排序序列中第一個
記錄的關鍵字R1與第二個記錄的關鍵字R2做比較，
如果R1>R2，則交換R1和R2的位置，否則不交換；
然後繼續對當前序列中的第二個記錄和第三個記
錄同樣的處理，依此類推。
*/
void BubbleSort(elemtype x[], int n)
{
int i,j,flag=1;
elemtype temp;
for(i=1;i<n && flag==1;i )
{
flag=0;
for(j=0;j<n-i;j )
{
if(x[j].key>x[j 1].key)
{
flag=1;
temp=x[j];
x[j]=x[j 1];
x[j 1]=temp;
}
}
}
}
② 數據結構中哪種排序方式效率最好
簡單排序的演算法（直接插入，冒泡，簡單選擇排序）簡單且穩定，適合與待排記錄較小的情況，當當待排序的關鍵碼序列已經基本有序時，用直接插入排序最快。
就平均時間的性能而言，快速排序最佳，即排序速度最快，所以在隨機情況下，快速排序是最佳選擇。一般情況下，快速排序效率最好。
既要節省空間，又要有較快的排序速度，堆排序是最佳選擇，其不足之處是建堆時需要消耗較多時間。
若希望排序是穩定的，且有較快的排序速度，則可選用2路歸並排序，其缺點需要較大的輔助空間分配。
③ 在各類演算法中那種演算法排序是最快的
說句實話，沒有最快這一說。
如果不在乎浪費空間，應該是桶排序最快
如果整體基本有序，插入排序最快
如果考慮綜合情況，快速排序更加實用常見（希爾排序、堆排序等各種排序也各有優劣）
一般情況下，冒泡這種排序僅僅是名字起的有趣罷了，不太好用
④ 幾種排序演算法的比較
一、八大排序演算法的總體比較
4.3、堆的插入：
每次插入都是將新數據放在數組最後。可以發現從這個新數據的父結點到根結點必然為一個有序的數列，然後將這個新數據插入到這個有序數據中
（1）用大根堆排序的基本思想
先將初始數組建成一個大根堆，此對為初始的無序區；
再將最大的元素和無序區的最後一個記錄交換，由此得到新的無序區和有序區，且滿足<=的值；
由於交換後新的根可能違反堆性質，故將當前無序區調整為堆。然後再次將其中最大的元素和該區間的最後一個記錄交換，由此得到新的無序區和有序區，且仍滿足關系的值<=的值，同樣要將其調整為堆；
..........
直到無序區只有一個元素為止；
4.4：應用
尋找M個數中的前K個最小的數並保持有序；
時間復雜度：O(K)[創建K個元素最大堆的時間復雜度] +（M-K）*log(K)[對剩餘M-K個數據進行比較並每次對最大堆進行從新最大堆化]
5.希爾排序
（1）基本思想
先將整個待排序元素序列分割成若乾子序列（由相隔某個「增量」的元素組成的）分別進行直接插入排序，然後依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序（因為直接插入排序在元素基本有序的情況下，效率很高）；
（2）適用場景
比較在希爾排序中是最主要的操作，而不是交換。用已知最好的步長序列的希爾排序比直接插入排序要快，甚至在小數組中比快速排序和堆排序還快，但在涉及大量數據時希爾排序還是不如快排；
6.歸並排序
（1）基本思想
首先將初始序列的n個記錄看成是n個有序的子序列，每個子序列的長度為1，然後兩兩歸並，得到n/2個長度為2的有序子序列，在此基礎上，再對長度為2的有序子序列進行兩兩歸並，得到若干個長度為4的有序子序列，以此類推，直到得到一個長度為n的有序序列為止；
（2）適用場景
若n較大，並且要求排序穩定，則可以選擇歸並排序；
7.簡單選擇排序
（1）基本思想
第一趟：從第一個記錄開始，將後面n-1個記錄進行比較，找到其中最小的記錄和第一個記錄進行交換；
第二趟：從第二個記錄開始，將後面n-2個記錄進行比較，找到其中最小的記錄和第2個記錄進行交換；
...........
第i趟：從第i個記錄開始，將後面n-i個記錄進行比較，找到其中最小的記錄和第i個記錄進行交換；
以此類推，經過n-1趟比較，將n-1個記錄排到位，剩下一個最大記錄直接排在最後；
⑤ 常見的排序演算法哪個效率最高
快速排序法。
⑥ 幾種排序演算法的效率比較
[內部排序的主要演算法及相關可實現程序.rar
] - 內部排序的所有演算法，而且有相關可執行例子，包括插入排序，選擇排序，希爾排序，快速排序，堆排序，歸並排序等，很全，很孀。[排序演算法、字典和B-樹的C++語言實現.zip
] - 排序演算法、字典和B-樹的C++語言實現
代碼內容 包括以下演算法：
qui.c sort: quicksort
qsort.c sort: qsort
ins.c sort: insert sort
shl.c sort: shell sort
has.c dictionary:[幾種排序方法的實現.rar
] - 用 插入排序, 希爾排序 ,冒泡, 快速排序 , 選擇排序 ,堆排序, 歸並排序 實現對任意隨機數序列,並比較各種方法的運行快慢和復雜度[paixu.rar] - 內部排序演算法比較
] - 一個用VC++6.0做的一個資料庫方面的程序，是用來英語學習的，有助於VC資料庫編程的學習。[各種排序方法比較.rar
] - 這個程序包括了各種常用內部排序演算法在平均排序所需時間上的比較.[實現各種排序演算法並分析與比較.rar
] - 本程序實現各種排序演算法並分析與比較 直接插入排序， SHELL排序，冒泡排序，快速排序，簡單選擇排序，堆排序，歸並排序[圖論演算法庫 C++ 語言實現.zip
] - 圖論演算法庫 C++ 語言實現
代碼內容 圖論演算法庫，包括以下演算法：
⑦ 哪種排序演算法的效率最高
沒有最高，只有更高。不同數據結構有不同演算法，沒有可比性。同一種數據結構才能比
⑧ 誰幫我寫一份c語言版的各種排序演算法的效率比較
（1）「冒泡法」 冒泡法大家都較熟悉。其原理為從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); }