内部排序->选择排序->简单选择排序

文字描述

　　简单排序的基本思想是：每一趟在n-i+1(i=1,2,…,n)个记录中选取关键字最小的记录作为有序列表中的第i个记录。

示意图

　　略

算法分析

　　简单排序算法中，所需进行记录移动的操作次数较少，其最小值为0，最大值为3(n-1)。所需进行的关键字的比较次数相同，都为n(n-1)/2。因此总的时间复杂度为n*n，辅助空间为1，是不稳定的排序方法。

代码实现

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 #define DEBUG
 5 
 6 #define EQ(a, b) ((a) == (b))
 7 #define LT(a, b) ((a) <  (b))
 8 #define LQ(a, b) ((a) <= (b))
 9 
10 #define MAXSIZE 20
11 typedef int KeyType;
12 typedef char InfoType;
13 typedef struct{
14     KeyType key;
15     InfoType otherinfo;
16 }RedType;
17 
18 typedef struct{
19     RedType r[MAXSIZE+1];
20     int length;
21 }SqList;
22 
23 void PrintList(SqList L){
24     int i = 0;
25     printf("下标值：");
26     for(i=0; i<=L.length; i++){
27         printf("[%d] ", i);
28     }
29     printf("
关键字：");
30     for(i=0; i<=L.length; i++){
31         printf(" %-3d", L.r[i].key);
32     }
33     printf("
其他值：");
34     for(i=0; i<=L.length; i++){
35         printf(" %-3c", L.r[i].otherinfo);
36     }
37     printf("

");
38     return ;
39 }
40 
41 /*在L.r[I, I+1, ..., L.length]中选择key最小的记录，并返回其位置下标*/
42 int SelectMinKey(SqList *L, int I)
43 {
44     int i = 0;
45     int min = I;
46     for(i=I; i<=L->length; i++){
47         if(LT(L->r[i].key, L->r[min].key))
48             min = i;
49     }
50     return min;
51 }
52 
53 /*简单选择排序算法*/
54 void SimpleSelectSort(SqList *L)
55 {
56     int i = 0, j = 0;
57     RedType tmp;
58     //从顺序表L中选择第i小的记录，并记录到位
59     for(i=1; i<=L->length; i++){
60         //在L.r[i,...,L.length]中选择key最小的记录
61         j = SelectMinKey(L, i);
62         //于第i各记录交换
63         if(i!=j){
64             tmp = L->r[i];
65             L->r[i] = L->r[j];
66             L->r[j] = tmp;
67         }
68 #ifdef DEBUG
69         printf("第%d趟简单选择排序:
");
70         PrintList(*L);
71 #endif
72     }
73 }
74 int  main(int argc, char *argv[])
75 {
76     if(argc < 2){
77         return -1;
78     }
79     SqList L;
80     int i = 0;
81     for(i=1; i<argc; i++){
82         if(i>MAXSIZE)
83             break;
84         L.r[i].key = atoi(argv[i]);
85         L.r[i].otherinfo = 'a'+i-1;
86     }
87     L.length = (i-1);
88     L.r[0].key = 0;
89     L.r[0].otherinfo = '0';
90     printf("输入数据:
");
91     PrintList(L);
92     //对顺序表L作简单选择排序
93     SimpleSelectSort(&L);
94     return 0;
95 }

简单选择排序

运行