冒泡排序:
排序前: 11 5 8 1 2 12 0 19 2 4
第 1 次排序: 5 8 1 2 11 0 12 2 4 [19]
第 2 次排序: 5 1 2 8 0 11 2 4 [12 19]
第 3 次排序: 1 2 5 0 8 2 4 [11 12 19]
第 4 次排序: 1 2 0 5 2 4 [8 11 12 19]
第 5 次排序: 1 0 2 2 4 [5 8 11 12 19]
第 6 次排序: 0 1 2 2 [4 5 8 11 12 19] 此時已經有序了,不會發生交換動作,提前結束
平均復雜度為:O(n^2)
1 /*
2 按升序排序
3 */
4 void bubSort(int number[]){
5 int i, j, k, flag = 1; //用flag作一標志,可以提高效率
6 for(i = 0; (i < MAX -1) && (flag ==1); i++){ /*外循環控制排序的總趟數*/
7 flag = 0;//把標志位標為0,如果沒有進行內排序,表示之后的i+1到MAX-1趟均是有序的,不用排列了
8 for(j = 0; j <MAX - i - 1; j++){ /*內循環控制一趟排序的進行*/
9 if(number[j] > number[j+1]){
10 int temp = number[j+1];
11 number[j+1] = number[j];
12 number[j] =temp;
13 flag = 1; //發生交換后,把flag置為1
14 }
15 }
16
17 printf("第 %d 次排序: ", i+1);
18 for(k = 0; k < MAX; k++){
19 printf("%d ", number[k]);
20 }
21 printf("\n");
22
23 }
24
25 }
選擇排序:
排序前: 8 5 1 9 9 11 9 18 4 10
第 1 次排序: [1] 5 8 9 9 11 9 18 4 10
第 2 次排序: [1 4] 8 9 9 11 9 18 5 10
第 3 次排序: [1 4] 5 9 9 11 9 18 8 10
第 4 次排序: [1 4 5] 8 9 11 9 18 9 10
第 5 次排序: [1 4 5 8 ]9 11 9 18 9 10
第 6 次排序: 1 4 5 8 9 9 11 18 9 10
第 7 次排序: 1 4 5 8 9 9 9 18 11 10
第 8 次排序: 1 4 5 8 9 9 9 10 11 18
第 9 次排序: 1 4 5 8 9 9 9 10 11 18
第 10 次排序: 1 4 5 8 9 9 9 10 11 18
Press any key to continue
平均復雜度為:O(n^2)
1 /*
2 選擇排序
3 將要排序的對象分作兩部分，一個是已經排序的，一個是未排序的，在示排序中找一個最小的元素
4 然后把它追加到已排序的最后一個位置
5 */
6 void selSort(int number[]){
7 int i, j, k, m;
8 for(i = 0; i < MAX; i++ ){
9 m = i; //記錄當前最小數的下標
10 //一次遍列把最小的數的下標找出來
11 for(j = i +1 ; j < MAX; j++){
12 if(number[j] < number[m] )
13 m = j; //從開始向末尾遍列,如果遇到比number[m]小的數,把它的下標記下來
14 }
15 //交換第i個和第m個元素
16 if( i != m){
17 int temp = number[i];
18 number[i] = number[m];
19 number[m] =temp;
20 }
21 printf("第 %d 次排序: ", i+1);
22 for(k = 0; k < MAX; k++){
23 printf("%d ", number[k]);
24 }
25 printf("\n");
26
27 }
28 }
插入排序:
排序前: 4 14 7 5 16 11 2 18 8 2
第 1 次排序：4 14 7 5 16 11 2 18 8 2
第 2 次排序：4 7 14 5 16 11 2 18 8 2 把7插入到4后面
第 3 次排序：4 5 7 14 16 11 2 18 8 2
第 4 次排序：4 5 7 14 16 11 2 18 8 2
第 5 次排序：4 5 7 11 14 16 2 18 8 2
第 6 次排序：2 4 5 7 11 14 16 18 8 2
第 7 次排序：2 4 5 7 11 14 16 18 8 2
第 8 次排序：2 4 5 7 8 11 14 16 18 2
第 9 次排序：2 2 4 5 7 8 11 14 16 18
Press any key to continue
1 /*
2 插入排序，就像玩撲克一樣，我們將牌分為兩堆，每次從后面的一堆牌中抽出
3 最前端的牌，然后插入到前一堆牌的合適位置
4 */
5
6 void inSort(int number[]){
7 int i, j, k , temp;
8 for(j = 1; j < MAX; j++){
9 temp = number[j];//保存在抽取出來的元素
10 i = j -1;
11 while(temp < number[i]){
12 number[i+1]=number[i];//元素往后移
13 i--;
14 if(i == -1) //當i==1時,已經到了數組的始端
15 break;
16 }
17 number[i+1] = temp;
18 printf("第 %d 次排序：", j);
19 for(k = 0; k < MAX; k++)
20 printf("%d ", number[k]);
21 printf("\n");
22 }
23 }
總結:這三種排序算法是其它排序算法的基礎,理解過程是非常主要的,然后加以推廣應用.
測試代碼:
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define MAX 10
void SWAP(int &x,int &y){
int temp;
temp = x;
x = y;
y =temp;
}
void bubSort(int[]);
void selSort(int[]);
void inSort(int []);
int main(){
int number[MAX] ={0};
int i;
srand(time(NULL));
printf("排序前: ");
for(i = 0; i < MAX; i++){
number[i] = rand() %20;
printf("%d ", number[i]);
}
printf("\n");
printf("\n選擇排序方式：\n");
printf("(1)選擇排序\n(2)插入排序\n(3)冒泡排序\n:");
scanf("%d", &i);
switch(i) {
case 1:
selSort(number); break;
case 2:
inSort(number); break;
case 3:
bubSort(number); break;
default:
printf("選項錯誤(1..3)\n");
}
return 0;
}
/*
按升序排序
*/
void bubSort(int number[]){
int i, j, k, flag = 1; //用flag作一標志,可以提高效率
for(i = 0; (i < MAX -1) && (flag ==1); i++){ /*外循環控制排序的總趟數*/
flag = 0;//把標志位標為0,如果沒有進行內排序,表示之后的i+1到MAX-1趟均是有序的,不用排列了
for(j = 0; j <MAX - i - 1; j++){ /*內循環控制一趟排序的進行*/
if(number[j] > number[j+1]){
int temp = number[j+1];
number[j+1] = number[j];
number[j] =temp;
flag = 1; //發生交換后,把flag置為1
}
}
printf("第 %d 次排序: ", i+1);
for(k = 0; k < MAX; k++){
printf("%d ", number[k]);
}
printf("\n");
}
}
/*
選擇排序
將要排序的對象分作兩部分，一個是已經排序的，一個是未排序的，在示排序中找一個最小的元素
然后把它追加到已排序的最后一個位置
*/
void selSort(int number[]){
int i, j, k, m;
for(i = 0; i < MAX; i++ ){
m = i; //記錄當前最小數的下標
//一次遍列把最小的數的下標找出來
for(j = i +1 ; j < MAX; j++){
if(number[j] < number[m] )
m = j; //從開始向末尾遍列,如果遇到比number[m]小的數,把它的下標記下來
}
//交換第i個和第m個元素
if( i != m){
int temp = number[i];
number[i] = number[m];
number[m] =temp;
}
printf("第 %d 次排序: ", i+1);
for(k = 0; k < MAX; k++){
printf("%d ", number[k]);
}
printf("\n");
}
}
/*
插入排序，就像玩撲克一樣，我們將牌分為兩堆，每次從后面的一堆牌中抽出
最前端的牌，然后插入到前一堆牌的合適位置
*/
void inSort(int number[]){
int i, j, k , temp;
for(j = 1; j < MAX; j++){
temp = number[j];//保存在抽取出來的元素
i = j -1;
while(temp < number[i]){
number[i+1]=number[i];//元素往后移
i--;
if(i == -1) //當i==1時,已經到了數組的始端
break;
}
number[i+1] = temp;
printf("第 %d 次排序：", j);
for(k = 0; k < MAX; k++)
printf("%d ", number[k]);
printf("\n");
}
}