数据结构和算法——交换排序

• 一、内排序和外排序
• 二、交换排序
• • （一）冒泡排序
  • （二）快速排序

根据待排序的内容是否在内存中可将排序分为内排序和外排序，内排序的整个排序过程在内存在进行，而外排序由于排序的内容太多，内存无法容纳，需要借助外存，即其排序过程在内、外存之间交换数据才能进行。

冒泡排序通过两两比较相邻元素，如果反序（a[j]>a[j+1]），即大的在前面小的在后面时则交换，小的元素被交换至前面，一直到没有反序的情况为止，之所以叫做冒泡排序是因为在排序过程中，越小的元素会经过交换像一个个气泡一样浮到水面，即最小的元素会到数列的最前面，而最大的元素将会沉到数列的最底端。
程序代码如下：

#include
//冒泡排序函数
void BubbleSort(int arr[],int length)
{
	int i, j, n, temp;
	for (i = 0; i < length; i++)
	{
		for (j = 0; j < length - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])//若相邻两元素反序
			{
				temp = arr[j + 1];
				arr[j + 1] = arr[j];
				arr[j] = temp;
			}
		}
	}
	for (n = 0; n < length; n++)//依次输出排序好的数组元素
	{
		printf("%d ", arr[n]);
	}
}
//主函数
void main()
{
	int a[] = { 20, 30, 1, 5, 15, 0, 9, 26, 3, 4, 7 };
	BubbleSort(a,11);//调用冒泡排序函数
}

运行结果如下，可见数组内的元素由小到大排序：

#include
void QuickSort(int arr[], int first, int end)
{
	int i, j, temp;
	i = first;
	j = end;
	temp = arr[i];
	while (i < j)
	{
		while (arr[j] >= temp && j > i)
		{
			j--;
			arr[i] = arr[j];
		}
		while (arr[i] <= temp && j > i)
		{
			i++;
			arr[j] = arr[i];
		}
	}
	arr[i] = temp;
	if (first < i - 1)
		QuickSort(arr, first, i - 1);
	if (i + 1 < end)
		QuickSort(arr, i + 1, end);
}
int main()
{
	int n;
	int a[] = { 1,0,3,9,2,15,36,14,7,10 };
	QuickSort(a, 0, 9);
	for (n = 0; n < 10; n++)
		printf("%d ", a[n]);
	return 0;
}