排序（C语言实现）

1. 交换排序

1.冒泡排序

1.基本原则：

   比较两两相邻记录的关键字，使不满足排序要求的记录交换位置，直到n-1轮循环结束

2.操作顺序（从小到大为例）：

   （1）从头开始，比较 arr[i] 和 arr[i+1] ，如果第二个比第一个小，交换

   （2）指针向后移动，i=i+1，再次比较 arr[i] 和 arr[i+1] ，判断是否需要交换

   （3）循环操作以上步骤，直到指针指到最后一个位置

3.冒泡排序优化：

   如果在排序中间数据已经有序，但是普通的冒泡排序还会继续循环，增加时间的消耗。所以需要在算法中设置一个简单的标记位 flag 来判断这轮循环是否交换了数据，开始时将flag 置为1，进入第一重循环将其置为0，如果有交换就把 flag 置为1，只有交换过数据（即 flag 置为1）才会继续进入下一轮循环，否则排序结束

4.代码实现：

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

void BubbleSort(int arr[],int len) //参数：（数组，数组长度）
{
	int i, j;
	int flag = 1;
	for (i = 0; i < len - 1 && flag; i++)
	{
		flag = 0;
		for (j = 0; j < len - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				swap(&arr[j], &arr[j + 1]);
				flag = 1;
			}
		}
	}
}

2.选择排序

1.简单选择排序

1.基本原则：

   从待排序的数据中选出最值，交换该数据与待排序序列的头部数据，直到所有待排序的数据元素排序完毕

2.特点：

   （1）可以将序列分为两部分，刚开始整个序列都视为待排序序列，有序序列为空

   （2）第一轮循环先把最小值默认为第0个，进入第二轮循环

   （3）第二轮循环先找到最小值的下标，如果循环结束后min的值与开始不同，再进行交换

   （4）不断重复，直到数据排序结束

4.代码实现：

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[min] > arr[j])
				min = j;
		}
		if (min != i)
		{
			swap(&arr[min], &arr[i]);
		}
	}
}

2.归并排序

1.基本思想：

   分治法的典型应用，将已经有序的两个子序列合并，在合并过程中对元素排序，从而得到一个完整有序的序列，也就是保证小范围的数据有序，再让大范围的数据有序

2.过程：

   （1）n个记录的序列，通常先视为n个小序列

   （2）相邻的两个小序列两两比较再合并，就有n/2个序列，即每次序列的数量减半

   （3）当序列数量为2时，进行归并排序，可以使原始序列完全有序