常用演算法排序的代碼

Ⅰ c++快速排序演算法代碼

1．將i 和j分別指向待排序區域的最左側記錄和最右側記錄的位置；
2．重復下述過程，直到i=j
2.1右側掃描，直到記錄j的關鍵碼小於基準記錄的關鍵碼；
2.2 如果i<j，則將r[j]與r[i]交換，並將i++；
2.3左側掃描，直到記錄i的關鍵碼大於基準記錄的關鍵碼；
2.4 如果i<j，則將r[i]與r[j]交換，並將j--；
3．退出循環，說明i和j指向了基準記錄所在位置，返回該位置；
void QuickSort(int r[ ], int first, int end)
{
if (first<end) { //遞歸結束
pivot=Partition(r, first, end); //一次劃分
QuickSort(r, first, pivot-1); //遞歸地對左側子序列進行快速排序
QuickSort(r, pivot+1, end); //遞歸地對右側子序列進行快速排序
}
}

int Partition(int r[ ], int first, int end)
{
i=first; j=end; //初始化
while (i<j)
{
while (i<j && r[i]<= r[j]) j--； //右側掃描
if (i<j) {
r[i]←→r[j]; //將較小記錄交換到前面
i++;
}
while (i<j && r[i]<= r[j]) i++； //左側掃描
if (i<j) {
r[j]←→r[i]; //將較大記錄交換到後面
j--;
}
}
retutn i; //i為軸值記錄的最終位置
}

Ⅱ C語言冒泡排序法代碼是什麼

所謂冒泡排序法，就是對一組數字進行從大到小或者從小到大排序的一種演算法。

1、具體方法是，相鄰數值兩兩交換。從第一個數值開始，如果相鄰兩個數的排列順序與我們的期望不同，則將兩個數的位置進行交換（對調）；如果其與我們的期望一致，則不用交換。重復這樣的過程，一直到最後沒有數值需要交換，則排序完成。具體情況如下圖所示：

Ⅲ 急求c語言寫的各種排序代碼

數據結構作業吧
1.簡單選擇排序
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
#define N 8
typedef int KeyType;
typedef int InfoType; /* 定義其它數據項的類型 */
typedef struct
{
KeyType key; /* 關鍵字項 */
InfoType otherinfo; /* 其它數據項，具體類型在主程中定義 */
}RedType; /* 記錄類型 */

typedef struct
{
RedType r[MAXSIZE+1]; /* r[0]閑置或用作哨兵單元 */
int length; /* 順序表長度 */
}SqList; /* 順序表類型 */

int SelectMinKey(SqList L,int i)
{ /* 返回在L.r[i..L.length]中key最小的記錄的序號 */
KeyType min;
int j,k;
k=i; /* 設第i個為最小 */
min=L.r[i].key;
for(j=i+1;j<=L.length;j++)
if(L.r[j].key<min) /* 找到更小的 */
{
k=j;
min=L.r[j].key;
}
return k;
}

void SelectSort(SqList *L)
{ /* 對順序表L作簡單選擇排序。演算法10.9 */
int i,j;
RedType t;
for(i=1;i<(*L).length;++i)
{ /* 選擇第i小的記錄，並交換到位 */
j=SelectMinKey(*L,i); /* 在L.r[i..L.length]中選擇key最小的記錄 */
if(i!=j)
{ /* 與第i個記錄交換 */
t=(*L).r[i];
(*L).r[i]=(*L).r[j];
(*L).r[j]=t;
}
}
}

void print(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}

int main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
SqList l;
int i;
for(i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前:\n");
print(l);
SelectSort(&l);
printf("排序後:\n");
print(l);
system("pause");
return 0;
}

2.冒泡排序
#include<stdio.h>
#include<stdlib.h>
#define N 8
void bubble_sort(int a[],int n)
{ /* 將a中整數序列重新排列成自小至大有序的整數序列(起泡排序) */
int i,j,t;
int change;
for(i=n-1,change=1;i>1&&change;--i)
{
change=0;
for(j=0;j<i;++j)
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
change=1;
}
}
}

void print(int r[],int n)
{
int i;
for(i=0;i<n;i++)
printf("%d ",r[i]);
printf("\n");
}

int main()
{
int d[N]={49,38,65,97,76,13,27,49};
printf("排序前:\n");
print(d,N);
bubble_sort(d,N);
printf("排序後:\n");
print(d,N);
system("pause");
return 0;

}

3.歸並排序
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
#define N 7
typedef int KeyType;
typedef int InfoType; /* 定義其它數據項的類型 */
typedef struct
{
KeyType key; /* 關鍵字項 */
InfoType otherinfo; /* 其它數據項，具體類型在主程中定義 */
}RedType; /* 記錄類型 */

typedef struct
{
RedType r[MAXSIZE+1]; /* r[0]閑置或用作哨兵單元 */
int length; /* 順序表長度 */
}SqList; /* 順序表類型 */

void Merge(RedType SR[],RedType TR[],int i,int m,int n)
{ /* 將有序的SR[i..m]和SR[m+1..n]歸並為有序的TR[i..n] 演算法10.12 */
int j,k,l;
for(j=m+1,k=i;i<=m&&j<=n;++k) /* 將SR中記錄由小到大地並入TR */
if LQ(SR[i].key,SR[j].key)
TR[k]=SR[i++];
else
TR[k]=SR[j++];
if(i<=m)
for(l=0;l<=m-i;l++)
TR[k+l]=SR[i+l]; /* 將剩餘的SR[i..m]復制到TR */
if(j<=n)
for(l=0;l<=n-j;l++)
TR[k+l]=SR[j+l]; /* 將剩餘的SR[j..n]復制到TR */
}

void MSort(RedType SR[],RedType TR1[],int s, int t)
{ /* 將SR[s..t]歸並排序為TR1[s..t]。演算法10.13 */
int m;
RedType TR2[MAXSIZE+1];
if(s==t)
TR1[s]=SR[s];
else
{
m=(s+t)/2; /* 將SR[s..t]平分為SR[s..m]和SR[m+1..t] */
MSort(SR,TR2,s,m); /* 遞歸地將SR[s..m]歸並為有序的TR2[s..m] */
MSort(SR,TR2,m+1,t); /* 遞歸地將SR[m+1..t]歸並為有序的TR2[m+1..t] */
Merge(TR2,TR1,s,m,t); /* 將TR2[s..m]和TR2[m+1..t]歸並到TR1[s..t] */
}
}

void MergeSort(SqList *L)
{ /* 對順序表L作歸並排序。演算法10.14 */
MSort((*L).r,(*L).r,1,(*L).length);
}

void print(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}

int main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7}};
SqList l;
int i;
for(i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前:\n");
print(l);
MergeSort(&l);
printf("排序後:\n");
print(l);
system("pause");
return 0;
}

4.快速排序:
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
#define N 8
typedef int KeyType;
typedef int InfoType; /* 定義其它數據項的類型 */
typedef struct
{
KeyType key; /* 關鍵字項 */
InfoType otherinfo; /* 其它數據項，具體類型在主程中定義 */
}RedType; /* 記錄類型 */

typedef struct
{
RedType r[MAXSIZE+1]; /* r[0]閑置或用作哨兵單元 */
int length; /* 順序表長度 */
}SqList; /* 順序表類型 */

int Partition(SqList *L,int low,int high)
{ /* 交換順序表L中子表L.r[low..high]的記錄，使樞軸記錄到位， */
/* 並返回其所在位置，此時在它之前(後)的記錄均不大(小)於它。演算法10.6(a) */
RedType t;
KeyType pivotkey;
pivotkey=(*L).r[low].key; /* 用子表的第一個記錄作樞軸記錄 */
while(low<high)
{ /* 從表的兩端交替地向中間掃描 */
while(low<high&&(*L).r[high].key>=pivotkey)
--high;
t=(*L).r[low]; /* 將比樞軸記錄小的記錄交換到低端 */
(*L).r[low]=(*L).r[high];
(*L).r[high]=t;
while(low<high&&(*L).r[low].key<=pivotkey)
++low;
t=(*L).r[low]; /* 將比樞軸記錄大的記錄交換到高端 */
(*L).r[low]=(*L).r[high];
(*L).r[high]=t;
}
return low; /* 返回樞軸所在位置 */
}

void QSort(SqList *L,int low,int high)
{ /* 對順序表L中的子序列L.r[low..high]作快速排序。演算法10.7 */
int pivotloc;
if(low<high)
{ /* 長度大於1 */
pivotloc=Partition(L,low,high); /* 將L.r[low..high]一分為二 */
QSort(L,low,pivotloc-1); /* 對低子表遞歸排序，pivotloc是樞軸位置 */
QSort(L,pivotloc+1,high); /* 對高子表遞歸排序 */
}
}

void QuickSort(SqList *L)
{ /* 對順序表L作快速排序。演算法10.8 */
QSort(L,1,(*L).length);
}

void print(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}

int main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
SqList l;
int i;
for(i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前:\n");
print(l);
QuickSort(&l);
printf("排序後:\n");
print(l);
system("pause");
return 0;
}

Ⅳ 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);
}

Ⅳ java冒泡排序法代碼

冒泡排序是比較經典的排序演算法。代碼如下：

for(int i=1;i<arr.length;i++){

for(int j=1;j<arr.length-i;j++){

//交換位置

}

拓展資料：

原理：比較兩個相鄰的元素，將值大的元素交換至右端。

思路：依次比較相鄰的兩個數，將小數放在前面，大數放在後面。即在第一趟：首先比較第1個和第2個數，將小數放前，大數放後。然後比較第2個數和第3個數，將小數放前，大數放後，如此繼續，直至比較最後兩個數，將小數放前，大數放後。重復第一趟步驟，直至全部排序完成。

第一趟比較完成後，最後一個數一定是數組中最大的一個數，所以第二趟比較的時候最後一個數不參與比較；

第二趟比較完成後，倒數第二個數也一定是數組中第二大的數，所以第三趟比較的時候最後兩個數不參與比較；

依次類推，每一趟比較次數-1；

……

舉例說明：要排序數組：int[]arr={6,3,8,2,9,1};

for(int i=1;i<arr.length;i++){

for(int j=1;j<arr.length-i;j++){

//交換位置

}

Ⅵ 快速排序演算法的示例代碼

usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;namespacetest{classQuickSort{staticvoidMain(string[]args){int[]array={49,38,65,97,76,13,27};sort(array,0,array.Length-1);Console.ReadLine();}/**一次排序單元，完成此方法，key左邊都比key小，key右邊都比key大。**@paramarray排序數組**@paramlow排序起始位置**@paramhigh排序結束位置**@return單元排序後的數組*/privatestaticintsortUnit(int[]array,intlow,inthigh){intkey=array[low];while(low<high){/*從後向前搜索比key小的值*/while(array[high]>=key&&high>low)--high;/*比key小的放左邊*/array[low]=array[high];/*從前向後搜索比key大的值，比key大的放右邊*/while(array[low]<=key&&high>low)++low;/*比key大的放右邊*/array[high]=array[low];}/*左邊都比key小，右邊都比key大。//將key放在游標當前位置。//此時low等於high*/array[low]=key;foreach(intiinarray){Console.Write({0} ,i);}Console.WriteLine();returnhigh;}/**快速排序*@paramarry*@return*/publicstaticvoidsort(int[]array,intlow,inthigh){if(low>=high)return;/*完成一次單元排序*/intindex=sortUnit(array,low,high);/*對左邊單元進行排序*/sort(array,low,index-1);/*對右邊單元進行排序*/sort(array,index+1,high);}}}運行結果：27 38 13 49 76 97 65
13 27 38 49 76 97 6513 27 38 49 65 76 97
快速排序就是遞歸調用此過程——在以49為中點分割這個數據序列，分別對前面一部分和後面一部分進行類似的快速排序，從而完成全部數據序列的快速排序，最後把此數據序列變成一個有序的序列，根據這種思想對於上述數組A的快速排序的全過程如圖6所示：
初始狀態 {49 38 65 97 76 13 27} 進行一次快速排序之後劃分為 {27 38 13} 49 {76 97 65} 分別對前後兩部分進行快速排序{27 38 13} 經第三步和第四步交換後變成 {13 27 38} 完成排序。{76 97 65} 經第三步和第四步交換後變成 {65 76 97} 完成排序。圖示 快速排序的最壞情況基於每次劃分對主元的選擇。基本的快速排序選取第一個元素作為主元。這樣在數組已經有序的情況下，每次劃分將得到最壞的結果。一種比較常見的優化方法是隨機化演算法，即隨機選取一個元素作為主元。這種情況下雖然最壞情況仍然是O(n^2)，但最壞情況不再依賴於輸入數據，而是由於隨機函數取值不佳。實際上，隨機化快速排序得到理論最壞情況的可能性僅為1/(2^n)。所以隨機化快速排序可以對於絕大多數輸入數據達到O(nlogn)的期望時間復雜度。一位前輩做出了一個精闢的總結：「隨機化快速排序可以滿足一個人一輩子的人品需求。」
隨機化快速排序的唯一缺點在於，一旦輸入數據中有很多的相同數據，隨機化的效果將直接減弱。對於極限情況，即對於n個相同的數排序，隨機化快速排序的時間復雜度將毫無疑問的降低到O(n^2)。解決方法是用一種方法進行掃描，使沒有交換的情況下主元保留在原位置。 QUICKSORT(A，p，r)
1if p<r
2then q ←PARTITION(A，p，r)
3QUICKSORT(A，p，q-1)
4QUICKSORT(A，q+1，r)
為排序一個完整的數組A，最初的調用是QUICKSORT(A，1，length[A]）。
快速排序演算法的關鍵是PARTITION過程，它對子數組A[p..r]進行就地重排：
PARTITION(A，p，r)
1x←A[r]
2i←p-1
3for j←p to r-1
4do if A[j]≤x
5then i←i+1
6exchange A[i]←→A[j]
7exchange A[i+1]←→A[r]
8return i+1 對PARTITION和QUICKSORT所作的改動比較小。在新的劃分過程中，我們在真正進行劃分之前實現交換：
（其中PARTITION過程同快速排序偽代碼（非隨機））
RANDOMIZED-PARTITION(A，p，r)
1i← RANDOM(p，r)
2exchange A[r]←→A[i]
3return PARTITION(A，p，r)
新的快速排序過程不再調用PARTITION，而是調用RANDOMIZED-PARTITION。
RANDOMIZED-QUICKSORT(A，p，r)
1if p<r
2then q← RANDOMIZED-PARTITION(A，p，r)
3RANDOMIZED-QUICKSORT(A，p，q-1)
4RANDOMIZED-QUICKSORT(A，q+1，r) 這里為方便起見，我們假設演算法Quick_Sort的范圍閾值為1（即一直將線性表分解到只剩一個元素），這對該演算法復雜性的分析沒有本質的影響。
我們先分析函數partition的性能，該函數對於確定的輸入復雜性是確定的。觀察該函數，我們發現，對於有n個元素的確定輸入L[p..r]，該函數運行時間顯然為θ（n）。
最壞情況
無論適用哪一種方法來選擇pivot，由於我們不知道各個元素間的相對大小關系（若知道就已經排好序了），所以我們無法確定pivot的選擇對劃分造成的影響。因此對各種pivot選擇法而言，最壞情況和最好情況都是相同的。
我們從直覺上可以判斷出最壞情況發生在每次劃分過程產生的兩個區間分別包含n-1個元素和1個元素的時候（設輸入的表有n個元素）。下面我們暫時認為該猜測正確，在後文我們再詳細證明該猜測。
對於有n個元素的表L[p..r]，由於函數Partition的計算時間為θ（n），所以快速排序在序壞情況下的復雜性有遞歸式如下：
T(1)=θ(1),T(n)=T(n-1)+T(1)+θ(n) (1)
用迭代法可以解出上式的解為T(n)=θ（n2）。
這個最壞情況運行時間與插入排序是一樣的。
下面我們來證明這種每次劃分過程產生的兩個區間分別包含n-1個元素和1個元素的情況就是最壞情況。
設T(n）是過程Quick_Sort作用於規模為n的輸入上的最壞情況的時間，則
T(n)=max(T(q)+T(n-q))+θ（n)，其中1≤q≤n-1 (2)
我們假設對於任何k<n，總有T(k）≤ck，其中c為常數；顯然當k=1時是成立的。
將歸納假設代入（2），得到：
T(n）≤max(cq2+c(n-q)2)+θ（n)=c*max(q2+(n-q)2)+θ（n)
因為在[1,n-1]上q2+(n-q)2關於q遞減，所以當q=1時q2+(n-q)2有最大值n2-2(n-1）。於是有：
T(n）≤cn2-2c(n-1)+θ（n）≤cn2
只要c足夠大，上面的第二個小於等於號就可以成立。於是對於所有的n都有T(n）≤cn。
這樣，排序演算法的最壞情況運行時間為θ（n2），且最壞情況發生在每次劃分過程產生的兩個區間分別包含n-1個元素和1個元素的時候。
時間復雜度為o（n2）。
最好情況
如果每次劃分過程產生的區間大小都為n/2，則快速排序法運行就快得多了。這時有：
T(n)=2T(n/2)+θ（n),T(1)=θ（1) (3)
解得：T(n)=θ（nlogn)
快速排序法最佳情況下執行過程的遞歸樹如下圖所示，圖中lgn表示以10為底的對數，而本文中用logn表示以2為底的對數.
由於快速排序法也是基於比較的排序法，其運行時間為Ω（nlogn)，所以如果每次劃分過程產生的區間大小都為n/2，則運行時間θ（nlogn）就是最好情況運行時間。
但是，是否一定要每次平均劃分才能達到最好情況呢？要理解這一點就必須理解對稱性是如何在描述運行時間的遞歸式中反映的。我們假設每次劃分過程都產生9:1的劃分，乍一看該劃分很不對稱。我們可以得到遞歸式：
T(n)=T(n/10)+T(9n/10)+θ（n),T(1)=θ（1) (4)
請注意樹的每一層都有代價n，直到在深度log10n=θ（logn）處達到邊界條件，以後各層代價至多為n。遞歸於深度log10/9n=θ（logn）處結束。這樣，快速排序的總時間代價為T(n)=θ（nlogn），從漸進意義上看就和劃分是在中間進行的一樣。事實上，即使是99:1的劃分時間代價也為θ（nlogn）。其原因在於，任何一種按常數比例進行劃分所產生的遞歸樹的深度都為θ（nlogn），其中每一層的代價為O(n），因而不管常數比例是什麼，總的運行時間都為θ（nlogn），只不過其中隱含的常數因子有所不同。（關於演算法復雜性的漸進階，請參閱演算法的復雜性)
平均情況
快速排序的平均運行時間為θ(nlogn)。
我們對平均情況下的性能作直覺上的分析。
要想對快速排序的平均情況有個較為清楚的概念，我們就要對遇到的各種輸入作個假設。通常都假設輸入數據的所有排列都是等可能的。後文中我們要討論這個假設。
當我們對一個隨機的輸入數組應用快速排序時，要想在每一層上都有同樣的劃分是不太可能的。我們所能期望的是某些劃分較對稱，另一些則很不對稱。事實上，我們可以證明，如果選擇L[p..r]的第一個元素作為支點元素，Partition所產生的劃分80%以上都比9:1更對稱，而另20%則比9:1差，這里證明從略。
平均情況下，Partition產生的劃分中既有「好的」，又有「差的」。這時，與Partition執行過程對應的遞歸樹中，好、差劃分是隨機地分布在樹的各層上的。為與我們的直覺相一致，假設好、差劃分交替出現在樹的各層上，且好的劃分是最佳情況劃分，而差的劃分是最壞情況下的劃分。在根節點處，劃分的代價為n，劃分出來的兩個子表的大小為n-1和1，即最壞情況。在根的下一層，大小為n-1的子表按最佳情況劃分成大小各為（n-1)/2的兩個子表。這兒我們假設含1個元素的子表的邊界條件代價為1。
在一個差的劃分後接一個好的劃分後，產生出三個子表，大小各為1，（n-1)/2和（n-1)/2，代價共為2n-1=θ（n）。一層劃分就產生出大小為（n-1)/2+1和（n-1)/2的兩個子表，代價為n=θ（n）。這種劃分差不多是完全對稱的，比9:1的劃分要好。從直覺上看，差的劃分的代價θ（n）可被吸收到好的劃分的代價θ（n）中去，結果是一個好的劃分。這樣，當好、差劃分交替分布劃分都是好的一樣：仍是θ（nlogn），但θ記號中隱含的常數因子要略大一些。關於平均情況的嚴格分析將在後文給出。
在前文從直覺上探討快速排序的平均性態過程中，我們已假定輸入數據的所有排列都是等可能的。如果輸入的分布滿足這個假設時，快速排序是對足夠大的輸入的理想選擇。但在實際應用中，這個假設就不會總是成立。
解決的方法是，利用隨機化策略，能夠克服分布的等可能性假設所帶來的問題。
一種隨機化策略是：與對輸入的分布作「假設」不同的是對輸入的分布作「規定」。具體地說，在排序輸入的線性表前，對其元素加以隨機排列，以強制的方法使每種排列滿足等可能性。事實上，我們可以找到一個能在O(n）時間內對含n個元素的數組加以隨機排列的演算法。這種修改不改變演算法的最壞情況運行時間，但它卻使得運行時間能夠獨立於輸入數據已排序的情況。
另一種隨機化策略是：利用前文介紹的選擇支點元素pivot的第四種方法，即隨機地在L[p..r]中選擇一個元素作為支點元素pivot。實際應用中通常採用這種方法。
快速排序的隨機化版本有一個和其他隨機化演算法一樣的有趣性質：沒有一個特別的輸入會導致最壞情況性態。這種演算法的最壞情況性態是由隨機數產生器決定的。你即使有意給出一個壞的輸入也沒用，因為隨機化排列會使得輸入數據的次序對演算法不產生影響。只有在隨機數產生器給出了一個很不巧的排列時，隨機化演算法的最壞情況性態才會出現。事實上可以證明幾乎所有的排列都可使快速排序接近平均情況性態，只有非常少的幾個排列才會導致演算法的近最壞情況性態。
一般來說，當一個演算法可按多條路子做下去，但又很難決定哪一條保證是好的選擇時，隨機化策略是很有用的。如果大部分選擇都是好的，則隨機地選一個就行了。通常，一個演算法在其執行過程中要做很多選擇。如果一個好的選擇的獲益大於壞的選擇的代價，那麼隨機地做一個選擇就能得到一個很有效的演算法。我們在前文已經了解到，對快速排序來說，一組好壞相雜的劃分仍能產生很好的運行時間 。因此我們可以認為該演算法的隨機化版本也能具有較好的性態。

Ⅶ java中排序演算法代碼

package temp;
import sun.misc.Sort;
/**
* @author zengjl
* @version 1.0
* @since 2007-08-22
* @Des java幾種基本排序方法
*/
/**
* SortUtil:排序方法
* 關於對排序方法的選擇：這告訴我們，什麼時候用什麼排序最好。當人們渴望先知道排在前面的是誰時，
* 我們用選擇排序；當我們不斷拿到新的數並想保持已有的數始終有序時，我們用插入排序；當給出的數
* 列已經比較有序，只需要小幅度的調整一下時，我們用冒泡排序。
*/
public class SortUtil extends Sort {
/**
* 插入排序法
* @param data
* @Des 插入排序(Insertion Sort)是，每次從數列中取一個還沒有取出過的數，並按照大小關系插入到已經取出的數中使得已經取出的數仍然有序。
*/
public int[] insertSort(int[] data) {
1/11頁
int temp;
for (int i = 1; i < data.length; i++) {
for (int j = i; (j > 0) && (data[j] < data[j - 1]); j--) {
swap(data, j, j - 1);
}
}
return data;
}
/**
* 冒泡排序法
* @param data
* @return
* @Des 冒泡排序(Bubble Sort)分為若干趟進行，每一趟排序從前往後比較每兩個相鄰的元素的大小（因此一趟排序要比較n-1對位置相鄰的數）並在
* 每次發現前面的那個數比緊接它後的數大時交換位置；進行足夠多趟直到某一趟跑完後發現這一趟沒有進行任何交換操作（最壞情況下要跑n-1趟，
* 這種情況在最小的數位於給定數列的最後面時發生）。事實上，在第一趟冒泡結束後，最後面那個數肯定是最大的了，於是第二次只需要對前面n-1
* 個數排序，這又將把這n-1個數中最小的數放到整個數列的倒數第二個位置。這樣下去，冒泡排序第i趟結束後後面i個數都已經到位了，第i+1趟實
* 際上只考慮前n-i個數（需要的比較次數比前面所說的n-1要小）。這相當於用數學歸納法證明了冒泡排序的正確性

Ⅷ C語言 冒泡排序法的代碼

#include<stdio.h>

void main()

{

int a[10];

int i,j,t;

printf("input 10 numbers: ");

for(i=0;i<10;i++)

scanf("%d",&a[i]);

for(j=0;j<9;j++) /*進行9次循環 實現9趟比較*/

for(i=0;i<9-j;i++) /*在每一趟中進行9-j次比較*/

if(a[i]>a[i+1]) /*相鄰兩個數比較,想降序只要改成a[i]<a[i+1]*/

{

t=a[i];

a[i]=a[i+1];

a[i+1]=t;

}

printf("the sorted numbers: ");

for(i=0;i<10;i++)

printf(" %d",a[i]);

}

(8)常用演算法排序的代碼擴展閱讀：

冒泡排序演算法的運作

1、比較相鄰的元素。如果第一個比第二個大（小），就交換他們兩個。

2、對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。這步做完後，最後的元素會是最大（小）的數。

3、針對所有的元素重復以上的步驟，除了最後已經選出的元素（有序）。

4、持續每次對越來越少的元素（無序元素）重復上面的步驟，直到沒有任何一對數字需要比較，則序列最終有序。

簡單的表示

#include <stdio.h>

void swap(int *i, int *j)

{

int temp = *i;

*i = *j;

*j = temp;

}

int main()

{

int a[10] = {2,1,4,5,6,9,7,8,7,7};

int i,j;

for (i = 0; i < 10; i++)

{

for (j = 9; j > i; j--)//從後往前冒泡

{

if (a[j] < a[j-1])

{

swap(&a[j], &a[j-1]);

}

}

}

for (i = 0; i < 10; i++)

{

printf("%d ", a[i]);

}

return 0;

}

參考資料來源：冒泡排序-網路

Ⅸ 演算法設計, 用代碼完成三種簡單的排序方法(冒泡,簡單插入,簡單選擇)中的任何一個即可

排序演算法是最基礎的演算法，冒泡演算法如下：
void buble_sort(int arr[], int length)
{
int i, j, max;
for(i=0, i<length-1, i++)
{
for(j=0, j<length-i-1, j++)

{
if(a[j]>a[j+1])

{

max = a[j];

a[j] = a[j+1];

a[j+1] = max;

}

}

}
}