1. 冒泡排序

1.1 思想

选择排序算法思想：以升序为例

• 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
• 针对所有的元素重复以上的步骤，除了最后一个。
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

以10个元素为例（升序）：10个数一共要交换9轮，每一轮归位一个数，9轮后排序完成。

1. 第一轮有10个元素，对这10个元素中的相邻元素进行两两比较，共比较9次，如果前面的元素大于后面的元素，则进行交换，第一轮结束后，最大的元素放在了最后一个位置；
2. 第二轮对剩余的9个元素中的相邻元素进行两两比较，如果前面的元素大于后面的元素，则进行交换，第二轮结束后，这9个元素中最大的元素被放在了倒数第二个位置；
3. …；
4. 第九轮对剩余的2个元素中的相邻元素进行两两比较，如果前面的元素大于后面的元素，则进行交换，第九轮结束后，这2个元素中最大的元素被放在了正数第二个位置，此时最小的元素也放到了第一个位置，排序结束。

假设待排序序列为 [5,1,4,2,8]，其冒泡排序图解如下：

第一轮排序图解：

第二轮排序图解：

第三轮排序图解：

第四轮排序图解：

1.2 代码实现

#include <stdio.h>
#define N 10
int main()
{
	int i, j, t;
	int a[N] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
	
	// 冒泡排序(升序)
	for(i = 1; i < N; i++) // 10个数要交换9轮
		for(j = 0; j < N - i; j++) // 第一轮比较9次，第二轮比较8次...第9轮比较一次
			if(a[j] > a[j+1]) // 如果前面的数比后面的数大，则交换
			{
				t = a[j];
				a[j] = a[j+1];
				a[j+1] = t;
			}
			
	// 打印排序后的数组			
	for(i = 0; i < 10; i++)
		printf("%d ", a[i]);
	printf("\n");
	return 0;
}

注：外层循环i控制交换几轮，内层循环j控制每轮对数字比较几次，因此i 和 j 的边界值需要注意。
1.此处N为10，i=1 和 i<N，i的取值为1-9，共交换9轮，说明i的取值没有问题
2. j=0 和 j<N-i
当i=1时，j的取值为0-8，由于要比较 a[j]>a[j+1]，也就是可以比较到a[8]>a[9]，第一轮对所有数进行了比较（比较9次），说明j的取值没有问题
当i=2时，j的取值为0-7，由于要比较 a[j]>a[j+1]，也就是可以比较到a[7]>a[8]，第二轮对剩余的9个数进行了比较（比较8次）
…
当i=9时，j的取值为0，由于要比较 a[j]>a[j+1]，也就是可以比较到a[0]>a[1]，第九轮对剩余的2个数进行了比较（比较1次）

运行结果如下：

注：如果想让数组中的数据降序排序，则只需要将上述代码中的 a[j] > a[j+1] 改为 a[j] < a[j+1]即可。

将冒泡排序封装成函数，代码如下：

#include <stdio.h>

void bubbleSort(int arr[], int len);
void swap(int *a, int *b);
void printArray(int arr[], int len);

// 冒泡排序（升序）
void bubbleSort(int arr[], int len) {
	int i, j;
	for(i = 1; i < len; i++) { // 外层循环，控制排序的趟数
		for(j = 0; j < len - i; j++) { // 内层循环，控制比较的次数
			if(arr[j] > arr[j+1]) { // 比较相邻的元素的大小
				swap(&arr[j], &arr[j+1]);
			}
		} 
	} 		
}

// 两数交换
void swap(int *a, int *b) {
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

// 打印数组
void printArray(int arr[], int len) {
	int i;
	for(i = 0; i < 10; i++) {
		printf("%d ", arr[i]);
	}	
	printf("\n");
}

int main() {
	int a[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
	int len = sizeof(a) / sizeof(int); // 数组长度
	printf("排序前：");
	printArray(a, len);
	bubbleSort(a, len);
	printf("排序后：");
	printArray(a, len);
	return 0;
}

运行结果：

注：通过传递数组名参数到子函数中，再获得数组长度是不可行的，这样计算出的长度恒为1；只能在数组定义所在的代码区中获取数组长度，再将获取后的数组长度作为实参传给函数。因此函数的的形参两个（数组和数组长度）bubbleSort(int arr[], int len)，而不能只传入数组 bubbleSort(int arr[])。

#include <stdio.h>

void bubbleSort(int arr[]) {
	int len = sizeof(arr)/sizeof(int);
	printf("%d\n", len); // 1
		
}

int main() {
	int a[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
	int len = sizeof(a) / sizeof(int);
	printf("%d\n", len); // 10
	bubbleSort(a);
	return 0;
}

2. 选择排序

2.1 思想

选择排序算法思想：以升序为例

• 首先在未排序序列中找到最小元素，存放到排序序列的起始位置。
• 再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。
• 重复第二步，直到所有元素均排序完毕。

以10个元素为例（升序）：10个数一共要交换9轮，每一轮归位一个数，9轮后排序完成。

1. 第一轮在10个元素找出最小的元素，放在第一个位置；
2. 第二轮在剩余9个元素中找出最小的元素，放在第二个位置；
3. …；
4. 第9轮在剩余2个元素中找出最小的元素，放在第9个位置，此时最后一个元素也放到了最后一个位置，排序结束。

选择排序图解：

2.2 代码实现

代码实现思路：

• 有N个数，N个数需要交换N-1轮，且数组下标从0开始，那么最外层循环是i的取值是[0,N-1)
• 定义k变量，表示当前最小数的下标，每轮循环时，默认假设初始值是最小值，即初始赋值k=i
• 遍历除当前最小数以外剩余的数，如果发现有比当前最小数更小的数，则记录更小的数的下标，然后两数交换

#include <stdio.h>
#define N 10
int main()
{
	int i, j, k, t;
	int a[N] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};

	// 选择排序(升序)
	for(i = 0; i < N - 1; i++) // 10个数要交换9轮
	{
		k = i; // 记录最小数下标，初始值为i(假设当前数就是最小数)
		for(j = i + 1; j < N; j++) // 遍历剩余的数，看有没有比当前最小数更小的数
			if(a[j] < a[k]) // 如果存在比当前数更小的数
				k = j; // 更改最小数的下标值
		// 如果最小数的下标值有更改，则交换两数
		if(k != i) 
		{
			t = a[i];
			a[i] = a[k];
			a[k] = t;
		}
	}
	
	// 打印排序后的数组
	for(i = 0;i < 10; i++)
		printf("%d ", a[i]);
	printf("\n");
	return 0;
}

注：如果想让数组中的数据降序排序，则只需要将上述代码中的 a[j] < a[k] 改为 a[j] > a[k]即 可。

将选择排序封装成函数，代码如下：

#include <stdio.h>

void selectSort(int arr[], int len);
void swap(int *a, int *b);
void printArray(int arr[], int len);

// 选择排序（升序）
void selectSort(int arr[], int len) {
	int i, j, min;
	for(i = 0; i < len; i++) {
		min = i; // 记录最小数下标
		for(j = i + 1; j < len; j++){ // 遍历剩余的数中，判断有没有更小的数，如果有则更改最小数的下标值
			if(arr[j] < arr[min]) {
				min = j;
			}
		}
		// 如果最小数的下标值发生变化，则交换两数
		if(min != i) {
			swap(&arr[i], &arr[min]);
		}
	}
}

// 两数交换
void swap(int *a, int *b) {
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

// 打印数组
void printArray(int arr[], int len) {
	int i;
	for(i = 0; i < 10; i++) {
		printf("%d ", arr[i]);
	}	
	printf("\n");
}

int main() {
	int a[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
	int len = sizeof(a) / sizeof(int); // 数组长度
	printf("排序前：");
	printArray(a, len);
	selectSort(a, len);
	printf("排序后：");
	printArray(a, len);
	return 0;
}