-
-
Save ismdeep/5b38b0310d42e91f75400e6e15662834 to your computer and use it in GitHub Desktop.
| 从最简单的C语言基础开始，一步一步编写一个选择排序（从小到大）的程序。 |
既然是要对数组进行排序，那我们直接搞一个数组进来，直接声明数组时就对初始值进行设定了。这里暂时不去写读取数据到数组到代码，这部分代码可以后面再去完善，我们先搞一个测试数据在这里来先把排序到部分测试通过了再说。
#include <stdio.h>
int main() {
int a[] = {5, 1, 3, 2, 8, 13, 98, 21, 1};
return 0;
}
为了方便查看数组里元素的值，我们干脆写一个函数来做这件事情，毕竟后面可能很多地方都需要这样一个功能。
实现一个 print_arr(int a[], int n) 的函数，打印数组的内容，这里需要两个参数，一个是数组 a ，一个是数组的大小 n ，毕竟我们讲过，函数传参数的时候，数组传递的其实是数组首元素的地址，那么这样就不知道数组的大小了，所以还需要另一个参数 n 来告诉数组传过来的这个数组有多少个元素。
实现完了这个打印数组的函数，顺便调用一下，看看函数有没有问题。
**注：**函数写完都先测试一下，确认这个函数没有问题，再去写接下来的问题，不要等着程序全部写完再去测试全部的，这样就不容易判断程序出错的位置了。
#include <stdio.h>
void print_arr(int a[], int n) {
printf("[");
for (int i = 0; i < n; i++) {
printf("%d ", a[i]);
}
printf("]");
printf("\n");
}
int main() {
int a[] = {5, 1, 3, 2, 8, 13, 98, 21, 1};
print_arr(a, 9);
return 0;
}
接下来就是核心部分了，我们先完成一个简单的功能：找出一组数字中的最小值，然后将这个最小值与这组数字中最左边交换。这对我们后面写排序算法有很大的帮助。
我们将这个函数命名为： core ，函数原型为：void core(int a[], int l, int r) 表示在数组 a 中的下标 l 与下标 r 之间找最小值，并与最左边(a[l])的交换。**注：**这里范围是包括下标为 l 和下标为 r 的。
我们都知道，C语言中数组下标是从 0 开始的。我们这里给的样例数组大小是 9 ，这样在调用程序对整个数组对范围进行操作时，参数应该如下：
core(a, 0, 8);
对数组完整数组找出其中最小值并与最左边交换，完整代码如下：
#include <stdio.h>
void core(int a[], int l, int r) {
for (int i = l + 1; i <= r; i++) {
if (a[i] < a[l]) {
int t = a[i];
a[i] = a[l];
a[l] = t;
}
}
}
void print_arr(int a[], int n) {
printf("[");
for (int i = 0; i < n; i++) {
printf("%d ", a[i]);
}
printf("]");
printf("\n");
}
int main() {
int a[] = {5, 1, 3, 2, 8, 13, 98, 21, 1};
print_arr(a, 9);
core(a, 0, 8);
print_arr(a, 9);
return 0;
}
以上核心函数 core 理解了的话，那选择排序基本上就理解差不多了。我们来回想一下 core 函数是干嘛的，其实 core 函数就是将 [l,r] 这个范围数组中的值最小的那一个放到最左边来，这样排序工作这个位置的值就完成了，接下来让程序去执行 core(a, l+1, r) 就行了。像极了体育课排队，老师找一个最矮的学生安排在第一个位置，然后说你别动了，你就这个位置了。于是这个时候，无论后面怎么排序，这位同学都始终是这个位置。那么接下来排序呢？老师就在剩下这堆学生里再去找一个最矮的同学放到剩下学生的第一个位置。这个工作依旧是跟上面的操作一样。
这样理解下来，选择排序就比较好理解了。
那我们依次来调用一下这个 core 函数对数组进行一次完整的排序。
#include <stdio.h>
void core(int a[], int l, int r) {
for (int i = l + 1; i <= r; i++) {
if (a[i] < a[l]) {
int t = a[i];
a[i] = a[l];
a[l] = t;
}
}
}
void print_arr(int a[], int n) {
printf("[");
for (int i = 0; i < n; i++) {
printf("%d ", a[i]);
}
printf("]");
printf("\n");
}
int main() {
int a[] = {5, 1, 3, 2, 8, 13, 98, 21, 1};
print_arr(a, 9);
core(a, 0, 8);
core(a, 1, 8);
core(a, 2, 8);
core(a, 3, 8);
core(a, 4, 8);
core(a, 5, 8);
core(a, 6, 8);
core(a, 7, 8);
print_arr(a, 9);
return 0;
}这里调用 core 函数，最后的范围是 [7,8] 就行了，毕竟当范围只有一个数字的时候，就不存在找什么最小值放在最左边这样的操作了。
看到上面调用 core 函数，一眼就能看出来是个循环吧。那我们用一个循环替代了吧。很简单，找到变化的地方，然后让循环变量从开始到最后进行迭代就行了。
#include <stdio.h>
void core(int a[], int l, int r) {
for (int i = l + 1; i <= r; i++) {
if (a[i] < a[l]) {
int t = a[i];
a[i] = a[l];
a[l] = t;
}
}
}
void print_arr(int a[], int n) {
printf("[");
for (int i = 0; i < n; i++) {
printf("%d ", a[i]);
}
printf("]");
printf("\n");
}
int main() {
int a[] = {5, 1, 3, 2, 8, 13, 98, 21, 1};
print_arr(a, 9);
for (int i = 0; i <= 7; i++) {
core(a, i, 8);
}
print_arr(a, 9);
return 0;
}
那么，我们接下来继续把这个循环调用 core 函数的部分写进一个函数，我们命名为：sort，注意，我们在写这样的一个函数的时候，需要考虑这个函数的通用性，对于传进这个函数的参数当然是用变量去代替，也就是说：我们这个函数既可以排序元素为 9 个的数组，也可以排序元素个数是任意个的数组。
sort 函数原型：void sort(int a[], int n) ，同上面 print_arr() 函数，数组大小需要单独的一个参数进行表示。
#include <stdio.h>
void core(int a[], int l, int r) {
for (int i = l + 1; i <= r; i++) {
if (a[i] < a[l]) {
int t = a[i];
a[i] = a[l];
a[l] = t;
}
}
}
void print_arr(int a[], int n) {
printf("[");
for (int i = 0; i < n; i++) {
printf("%d ", a[i]);
}
printf("]");
printf("\n");
}
void sort(int a[], int n) {
for (int i = 0; i <= n - 2; i++) {
core(a, i, n - 1);
}
}
int main() {
int a[] = {5, 1, 3, 2, 8, 13, 98, 21, 1};
print_arr(a, 9);
sort(a, 9);
print_arr(a, 9);
return 0;
}因为数组大小是 9，那么传入 sort 函数的参数 n 的值是9，那么根据之前循环的代码，我们需要将其中的 7 和 8 改成对应的变量表示形式。
至此，我们一个完整的选择排序的程序算是基本完成了。
这也是一个完整的写程序思考的过程，写代码从来就不是从上到下一口气写完了，你需要对程序进行拆解，然后一步一步从最简单的功能函数开始编写，当这个基础的函数已经测试确认没问题了，接下来需要用到的时候，就可以直接拿过来用，在使用的时候就不需要过多地去追究内部实现细节是啥了。
以下部分我们将对这个程序进行改进，让这个程序支持用户自己输入排序数据，而不是以上那种在程序里将数据写死在代码里的样子（我们称这种将数据写死在代码里称之为“硬编码”）。
#include <stdio.h>
#include <stdlib.h>
void print_arr(int a[], int n) {
printf("[");
for (int i = 0; i < n; i++) {
printf("%d ", a[i]);
}
printf("]");
printf("\n");
}
void core(int a[], int l, int r) {
for (int i = l + 1; i <= r; i++) {
if (a[i] < a[l]) {
int t = a[i];
a[i] = a[l];
a[l] = t;
}
}
}
void sort(int a[], int n) {
for (int i = 0; i <= n - 2; i++) {
core(a, i, n - 1);
}
}
int main() {
int n;
int *a;
scanf("%d", &n);
a = (int *) malloc(sizeof(int) * n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
print_arr(a, n);
sort(a, n);
print_arr(a, n);
return 0;
}程序输入:
9
5 1 3 2 8 13 98 21 1
第一行的数字9表示需要排序的数组一共有多少个数字。
第二行9个数字，一次表示数组中各个元素的值。
程序输出：
[5 1 3 2 8 13 98 21 1 ]
[1 1 2 3 5 8 13 21 98 ]
两行输出数组对应着两次 print_arr 函数的调用。
第一行是原始数组。
第二行是排序后的数组。
这个排序往后面还有更多的思考以及更多的程序实现可以写。比如：
- 程序输入上面，如何实现输入一行数字然后对这行数字进行排序。（毕竟输入搞成两行并不太友好，我们想更加随意一些，让程序判断我输入的数字有多少个，而不是我们去告诉程序。）
- 如何实现排序函数既可以从小到大也可以从大到小排序，可以通过什么样的方式告诉这个程序该怎么做。
- 如何实现排序函数让程序员在使用这个排序函数进行排序时，可以自定义排序规则，比如：我想利用这个函数对一组数字排序，这组数字排序是按照绝对值从小到大进行排序。但是我调用这个排序函数时却不去改变这个排序函数内部对源代码。该如何实现呢？（这样实现的函数将变得更加灵活，可用性更强。）
- 我看输出函数有些不爽，我想将数组转化成字符串，然后再输出。这样我们如果想将数组保存至文本，保存至数据库，就可以调用将数组转化成字符串的函数，接下来再拿字符串去处理。函数拆分开来好处这里就能体现出来了。
- 这个程序解决的是固定类型数据排序，只能处理
int类型的数组排序，那如何实现一个函数可以对任意类型元素的数组进行排序呢？ - ...
先写一个C语言程序最基础的框架。