冒泡排序

冒泡算法是我接触的第一个算法，我一直觉得，冒泡算法不是很好理解的一个算法……第一次在课堂上至少花了5分钟来理解，也许是十分钟……反正是很长很长的时间，我今天看这算法还是觉得晕……

言归正传，冒泡算法是一种流行的排序算法，它重复地交换相邻的两个反序元素。这句话简直是太含糊了，不过《算法导论》上就是这么写的，来看代码

#include "array_sort.h"
#include "base.h"

/**
 * @brief Bubble Sort for array.
 *
 * Repeatedly swapping adjacent elements that are out of order.
 *
 * @note Complexity: O(n^2).
 * @param array The array need to be sort.
 * @param len Length of array.
 * @return The sorted array.
 */
int *bubble_sort (int *array, int len)
{
	/* array[0, i) for the sorted sequence */
	int i, j;
	for (i = 0; i < len; i++)
	{
		for (j = len - 1; j > i; j--)
		{
			if (array[j] < array[j - 1])
			{
				swap (&array[j], &array[j - 1]);
			}
		}
	}

	return array;
}

其中array[0, i)是已经排好序的子数组，array[j, len)是乱序的子数组。
外层循环中，i是当前要选出的第i小的泡泡……这个泡泡是从底部浮上来的，内层循环中，每次都从最后一个元素开始选择，然后依次从[i+ 1, len)这个区间把最小的元素交换到i中……

其实我觉得我根本就没法描述清楚这个算法……而且我发现之前实现的“冒泡排序”其实是一种选择排序……