c語言常用的排序演算法

Ⅰ c語言的兩種排序

下面是C語言裡面常用的三種排序方法，但願對樓主有幫助，
一、冒泡法（起泡法）
演算法要求：用起泡法對10個整數按升序排序。
演算法分析：如果有n個數，則要進行n-1趟比較。在第1趟比較中要進行n-1次相鄰元素的兩兩比較，在第j趟比較中要進行n-j次兩兩比較。比較的順序從前往後，經過一趟比較後，將最值沉底（換到最後一個元素位置），最大值沉底為升序，最小值沉底為降序。
演算法源代碼：
# include <stdio.h>
main()
{
int a[10],i,j,t;
printf("Please input 10 numbers: ");
/*輸入源數據*/
for(i=0;i<10;i++)
scanf("%d",&a[i]);
/*排序*/
for(j=0;j<9;j++) /*外循環控制排序趟數，n個數排n-1趟*/
for(i=0;i<9-j;i++) /*內循環每趟比較的次數，第j趟比較n-j次*/
if(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]);
printf("\n");
}
演算法特點：相鄰元素兩兩比較，每趟將最值沉底即可確定一個數在結果的位置，確定元素位置的順序是從後往前，其餘元素可能作相對位置的調整。可以進行升序或降序排序。
演算法分析：定義n-1次循環，每個數字比較n-j次，比較前一個數和後一個數的大小。然後交換順序。
二、選擇法
演算法要求：用選擇法對10個整數按降序排序。
演算法分析：每趟選出一個最值和無序序列的第一個數交換，n個數共選n-1趟。第i趟假設i為最值下標，然後將最值和i+1至最後一個數比較，找出最值的下標，若最值下標不為初設值，則將最值元素和下標為i的元素交換。
演算法源代碼：
# include <stdio.h>
main()
{
int a[10],i,j,k,t,n=10;
printf("Please input 10 numbers:");
for(i=0;i<10;i++)
scanf("%d",&a[i]);
for(i=0;i<n-1;i++) /*外循環控制趟數，n個數選n-1趟*/
{
k=i; /*假設當前趟的第一個數為最值,記在k中 */
for(j=i+1;j<n;j++) /*從下一個數到最後一個數之間找最值*/
if(a[k]<a[j]) /*若其後有比最值更大的*/
k=j; /*則將其下標記在k中*/
if(k!=i) /*若k不為最初的i值，說明在其後找到比其更大的數*/
{ t=a[k]; a[k]=a[i]; a[i]=t; } /*則交換最值和當前序列的第一個數*/
}
printf("The sorted numbers: ");
for(i=0;i<10;i++)
printf("%d ",a[i]);
printf("\n");
}
演算法特點：每趟是選出一個最值確定其在結果序列中的位置，確定元素的位置是從前往後，而每趟最多進行一次交換，其餘元素的相對位置不變。可進行降序排序或升序排序。
演算法分析：定義外部n-1次循環，假設第一個為最值，放在參數中，在從下一個數以後找最值若後面有比前面假設的最值更大的就放在k中，然後在對k進行分析。若k部位最初的i值。也就是假設的i不是最值，那麼就交換最值和當前序列的第一個數
三、插入法
演算法要求：用插入排序法對10個整數進行降序排序。
演算法分析：將序列分為有序序列和無序列，依次從無序序列中取出元素值插入到有序序列的合適位置。初始是有序序列中只有第一個數，其餘n-1個數組成無序序列，則n個數需進n-1次插入。尋找在有序序列中插入位置可以從有序序列的最後一個數往前找，在未找到插入點之前可以同時向後移動元素，為插入元素准備空間。
演算法源代碼：
# include <stdio.h>
main()
{
int a[10],i,j,t;
printf("Please input 10 numbers: ");
for(i=0;i<10;i++)
scanf("%d",&a[i]);
for(i=1;i<10;i++) /*外循環控制趟數，n個數從第2個數開始到最後共進行n-1次插入*/
{
t=a[i]; /*將待插入數暫存於變數t中*/
for( j=i-1 ; j>=0 && t>a[j] ; j-- ) /*在有序序列（下標0 ~ i-1）中尋找插入位置*/
a[j+1]=a[j]; /*若未找到插入位置，則當前元素後移一個位置*/
a[j+1]=t; /*找到插入位置，完成插入*/
}
printf("The sorted numbers: ");
for(i=0;i<10;i++)
printf("%d ",a[i]);
printf("\n");
}
演算法特點：每趟從無序序列中取出第一個數插入到有序序列的合適位置，元素的最終位置在最後一趟插入後才能確定位置。也可是先用循環查找插入位置（可從前往後或從後往前），再將插入位置之後的元素（有序列中）逐個後移一個位置，最後完成插入。該演算法的特點是在尋找插入位置的同時完成元素的移動。因為元素的移動必須從後往前，則可將兩個操作結合在一起完成，提高演算法效率。仍可進行升序或降序排序。
二、下面是三種排序的概念及其優缺點

冒泡排序
已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。首先比較a[1]與a[2]的值，若a[1]大於a[2]則交換兩者的值，否則不變。再比較a[2]與a[3]的值，若a[2]大於a[3]則交換兩者的值，否則不變。再比較a[3]與a[4]，依此類推，最後比較a[n-1]與a[n]的值。這樣處理一輪後，a[n]的值一定是這組數據中最大的。再對a[1]~a[n-1]以相同方法處理一輪，則a[n-1]的值一定是a[1]~a[n-1]中最大的。再對a[1]~a[n-2]以相同方法處理一輪，依此類推。共處理n-1輪後a[1]、a[2]、……a[n]就以升序排列了。
優點：穩定，比較次數已知；
缺點：慢，每次只能移動相鄰兩個數據，移動數據的次數多。

選擇排序
已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。首先比較a[1]與a[2]的值，若a[1]大於a[2]則交換兩者的值，否則不變。再比較a[1]與a[3]的值，若a[1]大於a[3]則交換兩者的值，否則不變。再比較a[1]與a[4]，依此類推，最後比較a[1]與a[n]的值。這樣處理一輪後，a[1]的值一定是這組數據中最小的。再將a[2]與a[3]~a[n]以相同方法比較一輪，則a[2]的值一定是a[2]~a[n]中最小的。再將a[3]與a[4]~a[n]以相同方法比較一輪，依此類推。共處理n-1輪後a[1]、a[2]、……a[n]就以升序排列了。
優點：穩定，比較次數與冒泡排序一樣，數據移動次數比冒泡排序少；
缺點：相對之下還是慢。

插入排序
已知一組升序排列數據a[1]、a[2]、……a[n]，一組無序數據b[1]、b[2]、……b[m]，需將二者合並成一個升序數列。首先比較b[1]與a[1]的值，若b[1]大於a[1]，則跳過，比較b[1]與a[2]的值，若b[1]仍然大於a[2]，則繼續跳過，直到b[1]小於a數組中某一數據a[x]，則將a[x]~a[n]分別向後移動一位，將b[1]插入到原來a[x]的位置這就完成了b[1]的插入。b[2]~b[m]用相同方法插入。（若無數組a，可將b[1]當作n=1的數組a）
優點：穩定，快；
缺點：比較次數不一定，比較次數越少，插入點後的數據移動越多，特別是當數據總量龐大的時候，但用鏈表可以解決這個問題。

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

冒泡排序法，是C語言常用的排序演算法之一，意思是對一組數字進行從大到小或者從小到大排序的一種演算法。

具體方法是：

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

C語言常見的排序演算法：

1、冒泡排序

基本思想：比較相鄰的兩個數，如果前者比後者大，則進行交換。每一輪排序結束，選出一個未排序中最大的數放到數組後面。

2、快速排序

基本思想:選取一個基準元素，通常為數組最後一個元素（或者第一個元素）。從前向後遍歷數組，當遇到小於基準元素的元素時，把它和左邊第一個大於基準元素的元素進行交換。在利用分治策略從已經分好的兩組中分別進行以上步驟，直到排序完成。

3、直接插入排序

基本思想：和交換排序不同的是它不用進行交換操作，而是用一個臨時變數存儲當前值。當前面的元素比後面大時，先把後面的元素存入臨時變數，前面元素的值放到後面元素位置，再到最後把其值插入到合適的數組位置。

4、直接選擇排序

基本思想：依次選出數組最小的數放到數組的前面。首先從數組的第二個元素開始往後遍歷，找出最小的數放到第一個位置。再從剩下數組中找出最小的數放到第二個位置。以此類推，直到數組有序。

以上內容參考 網路-排序演算法、網路-c語言冒泡排序

Ⅲ 用C語言編程:用選擇法對10個整數排序,10個整數用scanf函數輸入

1、打開visual C++ 6.0，准備一個空白的c語言文件，引入頭文件，在main函數中定義變數和數組：

Ⅳ C語言實現文件排序

常見排序演算法（冒泡，選擇，快速）的C語言實現
要實現這幾種演算法的關鍵是要熟悉演算法的思想。簡單的說，冒泡排序，就如名字說的，每經過一輪排序，將最大的數沉到最底部。選擇排序的思想是將整個數列，分為有序區和無序區。每輪排序，將無序區里的最小數移入到有序區。快速排序的思想是以一個數為中心，通常這個數是該數列第一個數，將整個數列分為兩個部分，一個部分是大於這個數的區域，一個部分是小於這個數的區域。然後再對這兩個部分的數列分別排序。如果將數列分為兩個部分是通過，一方面從後向前的搜索，另一方面從前向後的搜索來實現的。具體的參考後面的來自網路的文檔。
從這幾個簡單的排序演算法上看，有幾個特點：
冒泡排序是最簡單的，也是最穩定的演算法。
選擇排序不太穩定，但是效率上較冒泡還是有較大的提升。其實在分析的過程中就能發現，選擇排序和冒泡排序相比，中間少了很多的交換過程，和比較的次數，這個應該是時間較少的原因。選擇排序能夠滿足一般的使用。當比較的數超過以萬為單位時，選擇排序也還是要一點時間的。
快速排序據說是最快的。這個可以從思想上看的出來。，當記錄較多的時候，快速排序的比較循環次數比上面2個都要少。但是在具體的實現過程中，並不見得如此。這是因為遞歸效率的低下導致的。當然，估計在實際使用過的過程，快速排序估計都會使用非遞歸操作棧的方式來實現。那樣應該會效率高傷不少。估計我會在後期出一個快速排序的非遞歸實現來真正比較它們3個性能。在下面的程序中，可以通過調高N的數字就能看的出來冒泡排序和選擇排序性能的差異。在N較小，大概幾百的時候，是看不出來的。N較大的的時候，比如N=1000或者N=10000的時候，快速排序的遞歸實現就會卡死在那裡了，出不了結果。
以下是具體的代碼：
/*
** 常見排序演算法比較
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>
#define N 10
#define Demo 1

void BubbleSort(int arr[], int n);
void SelectSort(int arr[], int n);
void QuickSort(int arr[], int n);
void PrintArray(int arr[], int n);
void GenerateArray(int arr[], int n);

int main(int argc, char *argv[])
{
int arr[N];

GenerateArray(arr, N);
#if Demo
printf("Before the bubble sort------------------------\n");
PrintArray(arr, N);
#endif
printf("Start Bubble sort----------------------\n");
clock_t start_time1=clock(); //開始計時
BubbleSort(arr, N);
clock_t end_time1=clock(); // 結束計時
printf("Running time is: %lf ms\n", (double)(end_time1-start_time1)/CLOCKS_PER_SEC*1000); //輸出運行時間
#if Demo
printf("After the bubble sort------------------------\n");
PrintArray(arr, N);
#endif
printf("-----------------------------------------------------------\n");

sleep(1000); // 單位是毫秒即千分之一秒
GenerateArray(arr, N);
#if Demo
printf("Before the selection sort------------------------\n");
PrintArray(arr, N);
#endif
printf("Start selection sort----------------------\n");
clock_t start_time2=clock(); //開始計時
SelectSort(arr, N);
clock_t end_time2=clock(); // 結束計時
printf("Running time is: %lf ms\n", (double)(end_time2-start_time2)/CLOCKS_PER_SEC*1000); //輸出運行時間
#if Demo
printf("After the selection sort------------------------\n");
PrintArray(arr, N);
#endif

printf("-----------------------------------------------------------\n");
sleep(1000); // 單位是毫秒即千分之一秒
GenerateArray(arr, N);
#if Demo
printf("Before the quick sort------------------------\n");
PrintArray(arr, N);
#endif
printf("Start quick sort----------------------\n");
clock_t start_time3=clock(); //開始計時
QuickSort(arr, N);
clock_t end_time3=clock(); // 結束計時
printf("Running time is: %lf ms\n", (double)(end_time3-start_time3)/CLOCKS_PER_SEC*1000); //輸出運行時間
#if Demo
printf("After the quick sort------------------------\n");
PrintArray(arr, N);
#endif

system("PAUSE");
return 0;
}

// 產生隨機列表
void GenerateArray(int arr[], int n)
{
int i;
srand((unsigned)time(0));

for(i = 0; i <N; i++)
{
arr[i] = rand(); // 生成隨機數 范圍在0-32767之間
}
}

// 列印列表
void PrintArray(int arr[], int n)
{
int i = 0;
for(i = 0; i < n; i++)
printf("%6d", arr[i]);
printf("\n");
}

// 經典冒泡排序
void BubbleSort(int arr[], int n)
{
int i = 0, j =0;
for(i = 0; i < n; i++)
for(j = 0; j < n - 1 - i; 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];
}
}
}

// 快速排序的遞歸實現
void QuickSort(int arr[], int n)
{
if(n <= 1)
return;

int i =0 , j = n - 1;
int key = arr[0];
int index = 0;

while(i < j)
{
// 從後向前搜索
while(j > i && arr[j] > key)
j--;
if(j == i)
break;
else
{
//交換 a[j] a[i]
arr[j] = arr[j] ^arr[i];
arr[i] = arr[j] ^arr[i];
arr[j] = arr[j] ^arr[i];
index = j;
}

// 從前向後搜索
while(i < j && arr[i] <key)
i++;
if(i == j)
break;
else
{
// 交換 a[i] a[j]
arr[j] = arr[j] ^arr[i];
arr[i] = arr[j] ^arr[i];
arr[j] = arr[j] ^arr[i];
index = i;
}
}
QuickSort(arr, index);
QuickSort(arr + index + 1, n - 1 - index);
}

// 選擇排序
void SelectSort(int arr[], int n)
{
int i, j;
int min;

for(i = 0; i < n - 1; i++)
{
int index = 0;
min = arr[i];
for(j = i + 1; j < n; j++) //找出 i+1 - n 無序區的最小者與arr[i]交換
{
if(arr[j] < min)
{
min = arr[j];
index = j;
}
}
if(index != 0) //表明無序區有比arr[i]小的元素
{
arr[i] = arr[i]^arr[index];
arr[index] = arr[i]^arr[index];
arr[i] = arr[i]^arr[index];
}
}
}

程序里有幾點注意的地方：
一，在程序里，交換2個數，我使用了異或來處理。這個可以根據個人喜好。為了避免產生臨時變數，可以使用如下幾種方式來交換2個數：
a=a^b;
b=a^b;
a=a^b;

或者
a=a+b;
b=a-b;
a=a-b;
使用第二種也挺好的。第一種異或的方式，只適用於，2個數都為int型的，a,b可以正可以負，這個沒有關系，但是必須是int類型。
二， sleep()函數是包含在windows.h裡面的，要加入 #include <window.h>
三， 關於隨機數生成的2個函數 srand()種子發生器函數，還有rand()隨機數生成器函數，自己可以參考相關文檔。
四， Demo宏來控制是演示還是比較性能用的。當把N調整的很小，比如10的時候，可以設置Demo為1，那樣就能列印數組了，可以看到比較前後的情況。當把N調整到很大比如10000的時候，就把Demo設置為0，那樣就不列印數組，直接比較性能。

具體的演算法文檔參考下面的：
冒泡排序
基本概念
冒泡排序（BubbleSort）的基本概念是：依次比較相鄰的兩個數，將小數放在前面，大數放在後面。即在第一趟：首先比較第1個和第2個數，將小數放前，大數放後。然後比較第2個數和第3個數，將小數放前，大數放後，如此繼續，直至比較最後兩個數，將小數放前，大數放後。至此第一趟結束，將最大的數放到了最後。在第二趟：仍從第一對數開始比較（因為可能由於第2個數和第3個數的交換，使得第1個數不再小於第2個數），將小數放前，大數放後，一直比較到倒數第二個數（倒數第一的位置上已經是最大的），第二趟結束，在倒數第二的位置上得到一個新的最大數（其實在整個數列中是第二大的數）。如此下去，重復以上過程，直至最終完成排序。
由於在排序過程中總是小數往前放，大數往後放，相當於氣泡往上升，所以稱作冒泡排序。
用二重循環實現，外循環變數設為i，內循環變數設為j。外循環重復9次，內循環依次重復9，8，...，1次。每次進行比較的兩個元素都是與內循環j有關的，它們可以分別用a[j]和a[j+1]標識，i的值依次為1,2,...,9，對於每一個i, j的值依次為1,2,...10-i。
產生
在許多程序設計中，我們需要將一個數列進行排序，以方便統計，而冒泡排序一直由於其簡潔的思想方法而倍受青睞。
排序過程
設想被排序的數組R［1..N］垂直豎立，將每個數據元素看作有重量的氣泡，根據輕氣泡不能在重氣泡之下的原則，從下往上掃描數組R，凡掃描到違反本原則的輕氣泡，就使其向上"漂浮"，如此反復進行，直至最後任何兩個氣泡都是輕者在上，重者在下為止。
演算法示例
A[0] 、 A[1]、 A[2]、 A[3]、 A[4]、 A[5]、 A[6]：
49 38 65 97 76 13 27
第一趟冒泡排序過程
38 49 65 97 76 13 27
38 49 65 97 76 13 27
38 49 65 97 76 13 27
38 49 65 76 97 13 27
38 49 65 76 13 97 27
38 49 65 76 13 27 97 – 這是第一趟冒泡排序完的結果
第二趟也是重復上面的過程，只不過不需要比較最後那個數97，因為它已經是最大的
38 49 65 13 27 76 97 – 這是結果
第三趟繼續重復，但是不需要比較倒數2個數了
38 49 13 27 65 76 97
….
選擇排序
基本思想
n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果：
①初始狀態：無序區為R[1..n]，有序區為空。
②第1趟排序
在無序區R[1..n]中選出關鍵字最小的記錄R[k]，將它與無序區的第1個記錄R[1]交換，使R[1..1]和R[2..n]分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。
……
③第i趟排序
第i趟排序開始時，當前有序區和無序區分別為R[1..i-1]和R(1≤i≤n-1)。該趟排序從當前無序區中選出關鍵字最小的記錄 R[k]，將它與無序區的第1個記錄R交換，使R[1..i]和R分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。
這樣，n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。
常見的選擇排序細分為簡單選擇排序、樹形選擇排序（錦標賽排序）、堆排序。上述演算法僅是簡單選擇排序的步驟。
排序過程
A[0] 、 A[1]、 A[2]、 A[3]、 A[4]、 A[5]、 A[6]：
49 38 65 97 76 13 27
第一趟排序後 13 ［38 65 97 76 49 27]
第二趟排序後 13 27 ［65 97 76 49 38]
第三趟排序後 13 27 38 [97 76 49 65]
第四趟排序後 13 27 38 49 [76 97 65]
第五趟排序後 13 27 38 49 65 [97 76]
第六趟排序後 13 27 38 49 65 76 [97]
最後排序結果 13 27 38 49 49 65 76 97
快速排序演算法
演算法過程
設要排序的數組是A[0]……A[N-1]，首先任意選取一個數據（通常選用第一個數據）作為關鍵數據，然後將所有比它小的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一趟快速排序。一趟快速排序的演算法是：
1）設置兩個變數I、J，排序開始的時候：I=0，J=N-1；
2）以第一個數組元素作為關鍵數據，賦值給key，即 key=A[0]；
3）從J開始向前搜索，即由後開始向前搜索（J=J-1），找到第一個小於key的值A[J]，並與A[I]交換；
4）從I開始向後搜索，即由前開始向後搜索（I=I+1），找到第一個大於key的A[I]，與A[J]交換；
5）重復第3、4、5步，直到 I=J； (3,4步是在程序中沒找到時候j=j-1，i=i+1，直至找到為止。找到並交換的時候i， j指針位置不變。另外當i=j這過程一定正好是i+或j+完成的最後另循環結束)
例如：待排序的數組A的值分別是：（初始關鍵數據：X=49） 注意關鍵X永遠不變，永遠是和X進行比較，無論在什麼位子，最後的目的就是把X放在中間，小的放前面大的放後面。
A[0] 、 A[1]、 A[2]、 A[3]、 A[4]、 A[5]、 A[6]：
49 38 65 97 76 13 27
進行第一次交換後： 27 38 65 97 76 13 49
( 按照演算法的第三步從後面開始找)
進行第二次交換後： 27 38 49 97 76 13 65
( 按照演算法的第四步從前面開始找>X的值，65>49,兩者交換，此時：I=3 )
進行第三次交換後： 27 38 13 97 76 49 65
( 按照演算法的第五步將又一次執行演算法的第三步從後開始找
進行第四次交換後： 27 38 13 49 76 97 65
( 按照演算法的第四步從前面開始找大於X的值，97>49,兩者交換，此時：I=4,J=6 )
此時再執行第三步的時候就發現I=J，從而結束一趟快速排序，那麼經過一趟快速排序之後的結果是：27 38 13 49 76 97 65，即所以大於49的數全部在49的後面，所以小於49的數全部在49的前面。
快速排序就是遞歸調用此過程——在以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} 完成排序。