常见排序算法导读(3)[简单选择排序]
这一节将介绍简单选择排序(Simple Selection Sort)。 在介绍简单排序算法之前，先给出排序的确切定义，并简单介绍一下排序算法的稳定性。排序的确切定义
假设含有n个对象的序列为{R, R, ..., R}, 其对应的关键字(key)序列为{K, K, ..., K}。 所谓排序， 就是确定0, 1, ..., n-1的一种排列p, p, ..., p, 使各个关键字满足如下的非递减(升序)或非递增(降序)关系：
K] <= K] <= ... <= K] 或
K] >= K] >= ... >= K]
也就是说， 所谓排序，就是根据关键字递增或递减的顺序，把数据对象依次排列起来，使一组任意排列的对象变成一组按其关键字线性有序的对象。
排序算法的稳定性
如果在对象序列中有两个对象R和R，它们的关键字K == K，且在排序之前，对象R排在R前面。如果在排序之后，对象R仍排在R的前面，则称这个排序算法是稳定的，否则称这个排序算法是不稳定的。 例如：在A中学B年级C班，有两个学霸分别叫陈小明和黎小军，陈小明的学号为007，黎小军的学号为008，在一次期末考试的时候，陈小明和黎小军的总成绩(750分为满分)都是699。按照稳定的排序算法，陈小明应该排在黎小军的前面；如果按照不稳定的排序算法，陈小明就排到了黎小军的后面。虽然使用稳定的排序算法和不稳定的排序算法，排序的结果会有所不同，但不能说不稳定的排序算法就不好，各有各的用途罢了。
注意：后面讨论的所有排序算法，如未特别说明，都是升序排序。
下面以简单选择排序为例讨论选择排序(selection sort)算法。
什么是选择排序?
一种最简单的排序算法是这样的：首先，找到数组中最小的那个元素；其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素，那么它就和自己交换）；再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此循环往复，直到将整个数组都排好序。这种方法叫做选择排序(selection sort)，因为它在不断地选择剩余元素之中的最小的那一个。
典型的简单选择排序过程是这样子滴， 【图片来源戳这里】
o 简单选择排序(simple selection sort)的C代码实现 : 函数s2sort()
/*
* Simple Selection Sort (s2sort in short)
*/
void //
s2sort(int a[], size_t n) // NOTE: a is always sorted and
{ // a is unsorted
for (int i = 0; i < n; i++) { //
int min = i; // Index of minimal element
// Find the minimal element in
for (int j = i + 1; j < n; j++) { // the unsorted a
if (a < a) { // If this element is less, then
min = j; // it is the new minimum and
} // remember its index
} //
//
if (i != min) { // Exchange the new mininum a
exchange(a, i, min); // found in a
} // with the old minimum a
} //
} //
static void exchange(int a[], int i, int j)
{
int t = a;
a= a;
a= t;
}
另外， 为了更好的理解，这里也给出s2sort()的递归实现。
static int getIndexOfMin(int a[], size_t n);
static void exchange(int a[], int i, int j);
void
s2sort(int a[], size_t n)
{
if (n == 1)
return;
int min = getIndexOfMin(a, n);
if (min != 0)
exchange(a, 0, min);
s2sort(++a, --n);
}
static int getIndexOfMin(int a[], size_t n)
{
int min = 0;
for (int i = 0; i < n; i++)
if (a < a)
min = i;
return min;
}
static void exchange(int a[], int i, int j)
{
int t = a;
a= a;
a= t;
}
接下来，给出一个完整的s2sort.c并编译后测试, 以便形象化地理解简单选择排序的全过程。
o s2sort.c // 将s2sort()做稍稍增强以打印详细的排序过程。注意：下面的程序中某些代码行风格很不好是故意的，因为只是为了帮助打印排序过程故一切从简。
#include <stdio.h>
#include <stdlib.h>
typedef struct obs_s {
unsigned int loop;
unsigned int exch;
} obs_t;
obs_t g_obs = { .loop = 0, .exch = 0 };
static void exchange(int a[], int i, int j);
static void show(int a[], size_t n);
static void exchange(int a[], int i, int j)
{
int t = a;
a= a;
a= t;
}
static void show(int a[], size_t n)
{
for (int i = 0; i < n; i++)
printf("%c ", a);
}
void
s2sort(int a[], size_t n)
{
for (int i = 0; i < n; i++) {
int min = i;
for (int j = i + 1; j < n; j++) { g_obs.loop++;
if (a < a) {
min = j;
}
}
if (i != min) { g_obs.exch++;
printf("#%2d:\t\t", i); show(a, n);
printf("\t<-- exchange(a[%d], a[%d])\n", i, min);
exchange(a, i, min);
} else {
printf("#%2d:\t\t", min); show(a, n); printf("\n");
}
}
}
int
main(int argc, char *argv[])
{
if (argc < 2) {
fprintf(stderr, "Usage %s <C1> ...\n", argv);
return -1;
}
argc--;
argv++;
size_t n = argc;
int *a = (int *)malloc(sizeof(int) * argc);
if (a == NULL) {
fprintf(stderr, "failed to malloc()\n");
return -1;
}
for (int i = 0; i < n; i++)
*(a+i) = argv;
printf(" \t0 1 2 3 4 5 6 7 8 9 10\n");
printf("Before sorting:\t"); show(a, n); printf("\n");
s2sort(a, n);
printf("Aftersorting:\t"); show(a, n); printf("\n");
printf("\n");
printf("Total loop times : %2d\n", g_obs.loop);
printf("Total exchange times : %2d\n", g_obs.exch);
free(a); a = NULL;
return 0;
}
o 编译并测试
$ gcc -g -Wall -m32 -std=c99 -o s2sort s2sort.c
$ ./s2sort 0 1 2 3 4 5 6 7 8 9 a #
0 1 2 3 4 5 6 7 8 9 10
Before sorting: 0 1 2 3 4 5 6 7 8 9 a
# 0: 0 1 2 3 4 5 6 7 8 9 a
# 1: 0 1 2 3 4 5 6 7 8 9 a
# 2: 0 1 2 3 4 5 6 7 8 9 a
# 3: 0 1 2 3 4 5 6 7 8 9 a
# 4: 0 1 2 3 4 5 6 7 8 9 a
# 5: 0 1 2 3 4 5 6 7 8 9 a
# 6: 0 1 2 3 4 5 6 7 8 9 a
# 7: 0 1 2 3 4 5 6 7 8 9 a
# 8: 0 1 2 3 4 5 6 7 8 9 a
# 9: 0 1 2 3 4 5 6 7 8 9 a
#10: 0 1 2 3 4 5 6 7 8 9 a
Aftersorting: 0 1 2 3 4 5 6 7 8 9 a
Total loop times : 55
Total exchange times :0
$ ./s2sort a 9 8 7 6 5 4 3 2 1 0 #
0 1 2 3 4 5 6 7 8 9 10
Before sorting: a 9 8 7 6 5 4 3 2 1 0
# 0: a 9 8 7 6 5 4 3 2 1 0 <-- exchange(a, a)
# 1: 0 9 8 7 6 5 4 3 2 1 a <-- exchange(a, a)
# 2: 0 1 8 7 6 5 4 3 2 9 a <-- exchange(a, a)
# 3: 0 1 2 7 6 5 4 3 8 9 a <-- exchange(a, a)
# 4: 0 1 2 3 6 5 4 7 8 9 a <-- exchange(a, a)
# 5: 0 1 2 3 4 5 6 7 8 9 a
# 6: 0 1 2 3 4 5 6 7 8 9 a
# 7: 0 1 2 3 4 5 6 7 8 9 a
# 8: 0 1 2 3 4 5 6 7 8 9 a
# 9: 0 1 2 3 4 5 6 7 8 9 a
#10: 0 1 2 3 4 5 6 7 8 9 a
Aftersorting: 0 1 2 3 4 5 6 7 8 9 a
Total loop times : 55
Total exchange times :5
$ ./s2sort S O R T E X A M P L E #
0 1 2 3 4 5 6 7 8 9 10
Before sorting: S O R T E X A M P L E
# 0: S O R T E X A M P L E <-- exchange(a, a)
# 1: A O R T E X S M P L E <-- exchange(a, a)
# 2: A E R T O X S M P L E <-- exchange(a, a)
# 3: A E E T O X S M P L R <-- exchange(a, a)
# 4: A E E L O X S M P T R <-- exchange(a, a)
# 5: A E E L M X S O P T R <-- exchange(a, a)
# 6: A E E L M O S X P T R <-- exchange(a, a)
# 7: A E E L M O P X S T R <-- exchange(a, a)
# 8: A E E L M O P R S T X
# 9: A E E L M O P R S T X
#10: A E E L M O P R S T X
Aftersorting: A E E L M O P R S T X
Total loop times : 55
Total exchange times :8
以上排序过程(#)截图如下(截图来源: Algorithms Fourth Edition P249)
小结： 对于长度为N的数组，简单选择排序需要大约(N*N/2)次比较和N次交换。 简单排序算法是不稳定的算法，其时间复杂度和空间复杂度是：
Worst-case performance О(N**2)
Best-caseperformance О(N**2)
Average performance О(N**2)
Worst-case space complexity О(N) total, O(1) auxiliary
到此为止，我们已经完全弄明白了简单选择排序的原理。其核心就是：整个序列中最小的元素首先被挑选出来放在序列的最前端。下一节，我们将介绍直接插入排序。
页:
[1]