㈠ 數據結構C語言——實現各種排序演算法
剛做完的
#include <iostream>
using namespace std;
void BiInsertsort(int r[], int n) //插入排序（折半）
{
for(int i=2;i<=n;i++)
{
if (r[i]<r[i-1])
{
r[0] = r[i]; //設置哨兵
int low=1,high=i-1; //折半查找
while (low<=high)
{
int mid=(low+high)/2;
if (r[0]<r[mid]) high=mid-1;
else low = mid+1;
}
int j;
for (j=i-1;j>high;j--) r[j+1] = r[j]; //後移
r[j+1] = r[0];
}
}
for(int k=1;k<=n;k++) cout<<r[k]<<" ";
cout<<"\n";
}
void ShellSort ( int r[], int n) //希爾排序
{
for(int d=n/2;d>=1;d=d/2) //以d為增量進行直接插入排序
{
for (int i=d+1;i<=n;i++)
{
r[0] = r[i]; //暫存被插入記錄
int j;
for( j=i-d; j>0 && r[0]<r[j]; j=j-d) r[j+d] = r[j]; //記錄後移d個位置
r[j+d] = r[0];
}
}
for(int i=1;i<=n;i++) cout<<r[i]<<" ";
cout<<"\n";
}
void BubbleSort(int r[], int n) //起泡排序
{
int temp,exchange,bound;
exchange=n; //第一趟起泡排序的范圍是r[0]到r[n-1]
while (exchange) //僅當上一趟排序有記錄交換才進行本趟排序
{
bound=exchange;
exchange=0;
for (int j=1; j<bound; j++) //一趟起泡排序
if (r[j]>r[j+1])
{
temp=r[j];
r[j]=r[j+1];
r[j+1]=temp;
exchange=j; //記錄每一次發生記錄交換的位置
}
}
for(int i=1;i<=n;i++) cout<<r[i]<<" ";
cout<<"\n";
}
int Partition(int r[], int first, int end) //快速排序一次劃分
{
int i=first; //初始化
int j=end;
r[0]=r[first];
while (i<j)
{
while (i<j && r[0]<= r[j]) j--; //右側掃描
r[i]=r[j];
while (i<j && r[i]<= r[0]) i++; //左側掃描
r[j]=r[i];
}
r[i]=r[0];
return i; //i為軸值記錄的最終位置
}
void QuickSort(int r[], int first, int end) //快速排序
{
if (first<end)
{ //遞歸結束
int pivot=Partition(r, first, end); //一次劃分
QuickSort(r, first, pivot-1);//遞歸地對左側子序列進行快速排序
QuickSort(r, pivot+1, end); //遞歸地對右側子序列進行快速排序
}
}
void SelectSort(int r[ ], int n) //簡單選擇排序
{
int i,j,index,temp;
for (i=1; i<n; i++) //對n個記錄進行n-1趟簡單選擇排序
{
index=i;
for (j=i+1; j<=n; j++) //在無序區中選取最小記錄
if (r[j]<r[index]) index=j;
if (index!=i)
{
temp=r[i];
r[i]=r[index];
r[index]=temp;
}
}
for(i=1;i<=n;i++) cout<<r[i]<<" ";
cout<<"\n";
}
void main()
{
const int numv=12;
int a[3][numv]={{0,6,13,19,23,37,39,41,45,48,58,86},{0,86,58,48,45,41,39,37,23,19,13,6},{0,23,13,48,86,19,6,41,58,37,45,39}};
int z1[numv],z2[numv];
int m,n;
cout<<"請選擇測試數據類型：⑴正序 ⑵逆序 ⑶隨機 [ 若跳出,請按⑷ ]" <<endl;
cin>>m;
while(m>0&&m<4)
{
cout<<"請選擇排序演算法：⑴直接插入排序 ⑵希爾排序 ⑶冒泡排序 ⑷快速排序 \n ⑸簡單選擇排序"<<endl;
cin>>n;
switch(n)
{
case 1:
cout << "直接插入排序前：" << "\n";
for(int j=1;j<numv;j++) cout<<a[m-1][j]<<" ";
cout << "\n直接插入排序結果為：" << "\n";
BiInsertsort(a[m-1],numv-1);
break;
case 2:
cout << "\n希爾排序前：" << "\n";
for(int j=1;j<numv;j++) cout<<a[m-1][j]<<" ";
cout << "\n希爾排序結果為：" << "\n";
ShellSort(a[m-1], numv-1);
break;
case 3:
cout << "\n冒泡排序前：" << "\n";
for(int k=1;k<numv;k++) cout<<a[m-1][k]<<" ";
cout << "\n冒泡排序結果為：" << "\n";
BubbleSort(a[m-1], numv-1);
break;
case 4:
cout << "\n快速排序前：" << "\n";
for(int j=1;j<numv;j++) cout<<a[m-1][j]<<" ";
cout << "\n快速排序結果為：" << "\n";
QuickSort(a[m-1],0,numv-1);
for(int i=1;i<numv;i++)
cout<<a[m-1][i]<<" ";
cout<<"\n";
break;
case 5:
cout << "\n簡單選擇排序前：" << "\n";
for(int j=1;j<numv;j++) cout<<a[m-1][j]<<" ";
cout << "\n簡單選擇排序結果為：" << "\n";
SelectSort(a[m-1],numv-1);
break;
default:
cout<<"輸入錯誤！"<<endl;
}
m=0;
cout<<"請選擇測試數據類型：⑴正序 ⑵逆序 ⑶隨機 [ 若跳出,請按⑷ ]" <<endl;
cin>>m;
}
if(m==4) cout<<"(*^__^*) 再見！"<<endl;
else cout<<"輸入錯誤！"<<endl;
}
㈡ 求各種排序演算法的比較
給你一個國家集訓隊的快排吧，這個應該夠用了。
這個是對a數組從小到大排序，把這個添加到任何程序中都很快。這個肯定要比堆排序快。對於插入排序快的快排肯定要較慢。但這個比較穩定，要不國家集訓隊怎麼用它呢！！！！！！
procere qsort(l,r:longint);
var
i,j,x,yy:longint;
begin
i:=l;j:=r;x:=a[(i+j) shr 1];
repeat
while a[i]<x do inc(i);
while a[j]>x do dec(j);
if i<=j then
begin
yy:=a[i];a[i]:=a[j];a[j]:=yy;
inc(i);dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;
㈢ 程序的排序演算法都有那幾種
1
插入排序
2快速排序
3選擇排序
4歸並排序
5基數排序
具體的你可以參照以下網址
http://shi..com/shi/233776.html
㈣ 幾個簡單的排序演算法
現在諸如：冒泡排序（最簡單的）、選擇排序、堆排序、SHELL排序、快速排序、歸並排序等各種排序演算法，在各類數據結構教材上都已經有了 C 語言版的子函數實現代碼，當然了，這個數據類型是一個抽象的數據類型，其實在使用時只需要在調用函數入口處，將調用形參修改為適合自己的數據類型即可。
㈤ 各種排序演算法
有插入排序，堆排序，快速排序，基排序，計數排序，桶排序，我說不完的，，詳情參看《演算法導論》
㈥ 各種排序演算法比較
插入排序 n*n、希爾排序 <=n*n、起泡排序 <=n* n、快速排序 n *log 2 n、選擇排序=n * n、堆排序n * log2 n、歸並排序 n * n
㈦ 各種排序演算法的比較
小朋友啊，你這不是問題是作業啊。
㈧ 、題目：各種排序演算法實現和比較
給個聯系方式。我發給你！！！
㈨ 各種排序演算法實現和比較
1、 堆排序定義
n個關鍵字序列Kl，K2，…，Kn稱為堆，當且僅當該序列滿足如下性質(簡稱為堆性質)：
(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ )
若將此序列所存儲的向量R[1..n]看做是一棵完全二叉樹的存儲結構，則堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉結點的關鍵字均不大於(或不小於)其左右孩子(若存在)結點的關鍵字。
關鍵字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分別滿足堆性質(1)和(2)，故它們均是堆，其對應的完全二叉樹分別如小根堆示例和大根堆示例所示。
2、大根堆和小根堆
根結點(亦稱為堆頂)的關鍵字是堆里所有結點關鍵字中最小者的堆稱為小根堆。
根結點(亦稱為堆頂)的關鍵字是堆里所有結點關鍵字中最大者，稱為大根堆。
注意：
①堆中任一子樹亦是堆。
②以上討論的堆實際上是二叉堆(Binary Heap)，類似地可定義k叉堆。
3、堆排序特點
堆排序(HeapSort)是一樹形選擇排序。
堆排序的特點是：在排序過程中，將R[l..n]看成是一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系，在當前無序區中選擇關鍵字最大(或最小)的記錄。
4、堆排序與直接插入排序的區別
直接選擇排序中，為了從R[1..n]中選出關鍵字最小的記錄，必須進行n-1次比較，然後在R[2..n]中選出關鍵字最小的記錄，又需要做n-2次比較。事實上，後面的n-2次比較中，有許多比較可能在前面的n-1次比較中已經做過，但由於前一趟排序時未保留這些比較結果，所以後一趟排序時又重復執行了這些比較操作。
堆排序可通過樹形結構保存部分比較結果，可減少比較次數。
5、堆排序
堆排序利用了大根堆(或小根堆)堆頂記錄的關鍵字最大(或最小)這一特徵，使得在當前無序區中選取最大(或最小)關鍵字的記錄變得簡單。
（1）用大根堆排序的基本思想
① 先將初始文件R[1..n]建成一個大根堆，此堆為初始的無序區
② 再將關鍵字最大的記錄R[1](即堆頂)和無序區的最後一個記錄R[n]交換，由此得到新的無序區R[1..n-1]和有序區R[n]，且滿足R[1..n-1].keys≤R[n].key
③ 由於交換後新的根R[1]可能違反堆性質，故應將當前無序區R[1..n-1]調整為堆。然後再次將R[1..n-1]中關鍵字最大的記錄R[1]和該區間的最後一個記錄R[n-1]交換，由此得到新的無序區R[1..n-2]和有序區R[n-1..n]，且仍滿足關系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調整為堆。
……
直到無序區只有一個元素為止。
（2）大根堆排序演算法的基本操作：
① 初始化操作：將R[1..n]構造為初始堆；
② 每一趟排序的基本操作：將當前無序區的堆頂記錄R[1]和該區間的最後一個記錄交換，然後將新的無序區調整為堆(亦稱重建堆)。
注意：
①只需做n-1趟排序，選出較大的n-1個關鍵字即可以使得文件遞增有序。
②用小根堆排序與利用大根堆類似，只不過其排序結果是遞減有序的。堆排序和直接選擇排序相反：在任何時刻，堆排序中無序區總是在有序區之前，且有序區是在原向量的尾部由後往前逐步擴大至整個向量為止。
（3）堆排序的演算法：
void HeapSort(SeqIAst R)
{ //對R[1..n]進行堆排序，不妨用R[0]做暫存單元
int i；
BuildHeap(R)； //將R[1-n]建成初始堆
for(i=n;i1；i--){ //對當前無序區R[1..i]進行堆排序，共做n-1趟。
R[0]=R[1]；R[1]=R[i];R[i]=R[0]； //將堆頂和堆中最後一個記錄交換
Heapify(R，1，i-1)； //將R[1..i-1]重新調整為堆，僅有R[1]可能違反堆性質
} //endfor
} //HeapSort
（4） BuildHeap和Heapify函數的實現
因為構造初始堆必須使用到調整堆的操作，先討論Heapify的實現。
① Heapify函數思想方法
每趟排序開始前R[l..i]是以R[1]為根的堆，在R[1]與R[i]交換後，新的無序區R[1..i-1]中只有R[1]的值發生了變化，故除R[1]可能違反堆性質外，其餘任何結點為根的子樹均是堆。因此，當被調整區間是R[low..high]時，只須調整以R[low]為根的樹即可。
"篩選法"調整堆
R[low]的左、右子樹(若存在)均已是堆，這兩棵子樹的根R[2low]和R[2low+1]分別是各自子樹中關鍵字最大的結點。若R[low].key不小於這兩個孩子結點的關鍵字，則R[low]未違反堆性質，以R[low]為根的樹已是堆，無須調整；否則必須將R[low]和它的兩個孩子結點中關鍵字較大者進行交換，即R[low]與R[large](R[large].key=max(R[2low].key，R[2low+1].key))交換。交換後又可能使結點R[large]違反堆性質，同樣由於該結點的兩棵子樹(若存在)仍然是堆，故可重復上述的調整過程，對以R[large]為根的樹進行調整。此過程直至當前被調整的結點已滿足堆性質，或者該結點已是葉子為止。上述過程就象過篩子一樣，把較小的關鍵字逐層篩下去，而將較大的關鍵字逐層選上來。因此，有人將此方法稱為"篩選法"。
具體的演算法
②BuildHeap的實現
要將初始文件R[l..n]調整為一個大根堆，就必須將它所對應的完全二叉樹中以每一結點為根的子樹都調整為堆。
顯然只有一個結點的樹是堆，而在完全二叉樹中，所有序號 的結點都是葉子，因此以這些結點為根的子樹均已是堆。這樣，我們只需依次將以序號為 ， -1，…，1的結點作為根的子樹都調整為堆即可。
具體演算法。
5、大根堆排序實例
對於關鍵字序列(42，13，24，91，23，16，05，88)，在建堆過程中完全二叉樹及其存儲結構的變化情況參見。
6、 演算法分析
堆排序的時間，主要由建立初始堆和反復重建堆這兩部分的時間開銷構成，它們均是通過調用Heapify實現的。
堆排序的最壞時間復雜度為O(nlgn)。堆排序的平均性能較接近於最壞性能。
由於建初始堆所需的比較次數較多，所以堆排序不適宜於記錄數較少的文件。
堆排序是就地排序，輔助空間為O(1)，
它是不穩定的排序方法。