冒泡排序:
排序前: 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");
}
}