冒泡排序、插入法排序以及选择排序是排序算法中比较基础的三种，其平均时间复杂度都是O(n^2)。
原理介绍
冒泡排序
冒泡排序的步骤是：比较相邻两个数，看是否满足大小关系，如果不满足则交换这两个数，使他们满足大小关系，这样可以保证最大（最小）的数始终会向后流动，循环一次之后，最大（最小）的数就会被交换到数组的最后。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。
插入法排序
插入法排序的思路是：把数组分成两个部分：排好序的，和未排序的。开始的时候，数组的第一个元素会被当做拍好序的部分，对其余未排好序的数值进行迭代，将其插入到排好序的部分中合适的位置。
选择法排序
选择法排序和插入法排序类似，都是将数组分为排好序的和未排序的两个部分。不同的是，选择法排序每次迭代都会选择未排序部分中的最小（最大）值，将其插入到排好序部分的队首（队尾）。
C语言实现
需要实现四个函数， 第一个是打印数组，接下来三个函数分别实现三种排序算法：
- void print_arry(int *a, int len)
- static inline void insertion_sort(int *a, int len)
- static inline void bubble_sort(int *a, int len)
- static inline void selection_sort(int *a, int len)
main函数中，首先需要用户输入指定数目(#define LEN 10)的数值，如果用户输入-1则随机生成这些数值。然后需要用户输入排序算法。输入完成后打印排序前的数组，然后根据相应的排序算法进行排序，最后再打印出排序后的数组。代码如下：
代码语言：javascript复制#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define LEN 10
#define NR_METHOD 3
#define RAND_RANGE 100
void print_arry(int *a, int len) {
int i = 0;
for (int i = 0; i < len; i ) {
printf("%d ", a[i]);
}
printf("\n");
}
static inline void insertion_sort(int *a, int len) {
int tmp = 0;
int i, j;
for (i = 1; i < len; i ) {
tmp = a[i];
for (j = i - 1; j >= 0; j--) {
if (a[j] > tmp) {
a[j 1] = a[j];
} else {
break;
}
}
a[j 1] = tmp;
}
}
static inline void bubble_sort(int *a, int len) {
int i, j;
int tmp;
int swapped = 0;
for (i = len - 1; i >= 0; i--) {
for (j = 0; j < i; j ) {
if (a[j] > a[j 1]) {
tmp = a[j];
a[j] = a[j 1];
a[j 1] = tmp;
swapped = 1;
}
}
if (!swapped) {
break;
}
}
}
static inline void selection_sort(int *a, int len) {
int i, j, min, tmp;
for (i = 0; i < len -1; i ) {
min = i;
for (j = i 1; j < len; j ) {
if(a[j] < a[min]) {
min = j;
}
}
if (min != i) {
tmp = a[min];
a[min] = a[i];
a[i] = tmp;
}
}
}
int main(int argc, char **argv) {
srand(time(NULL));
int a[LEN];
int data;
for (int i = 0; i < LEN; i ) {
printf("Please input a number: %d left: (-1 for random numbers)", LEN - i);
scanf("%d", &data);
if(data != -1) {
a[i] = data;
} else {
for (int j = 0; j < LEN; j ) {
a[j] = rand() % RAND_RANGE;
}
break;
}
}
while (1) {
printf("Please select a sort method:\n");
printf("0: Insertion sort\n");
printf("1: Bubble sort \n");
printf("2: Selection sort \n");
scanf("%d", &data);
if(data >= 0 && data < NR_METHOD) {
break;
} else {
printf("Please input a valid number!\n");
}
}
printf("Original Array: \n");
print_arry(a, LEN);
switch(data) {
case 0:
printf("You selected insertion sort\n");
insertion_sort(a, LEN);
break;
case 1:
printf("You selected bubble sort\n");
bubble_sort(a, LEN);
break;
case 2:
printf("You selected selection sort\n");
selection_sort(a, LEN);
break;
}
printf("Sorted Array: \n");
print_arry(a, LEN);
return 0;
}
