排序算法

冒泡排序

思路

两两元素相比，前一个比后一个大就交换，直到将最大的元素交换到末尾位置。这是第一趟。
一共进行n-1趟这样的交换将可以把所有的元素排好。

代码

void BubbleSort(int *arry,int num) // 小到大
{
	for (int i = 0; i < num-1; i++)
	{
		for (int j = 0; j < num-1; j++)
		{
			if (*(arry + j) > *(arry + j + 1))
			{
				int temp = *(arry + j);
				*(arry + j) = *(arry + j + 1);
				*(arry + j + 1) = temp;
			}
		}
	}
}

特性总结

时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：稳定

插入排序

思路

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

代码

void InsertSort(int* arry, int num)
{
	for (int i = 0; i < num - 1; i++)
	{
		int end = i; // 已经有序的最后一个元素序号
		int temp = *(arry+i+1); // 当前需要排序的元素
		while (end>=0)
		{
			if (*(arry + end)>temp)
			{
				*(arry + end + 1) = *(arry + end);
				end--;
			}
			else
			{
				break;
			}
		}
		*(arry + end + 1) = temp;
	}
}

特性总结

元素集合越接近有序，直接插入排序算法的时间效率越高。
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：稳定

快速排序

思路

选出一个key，一般是最左边或是最右边的。
定义一个begin和一个end，begin从左向右走，end从右向左走。（需要注意的是：若选择最左边的数据作为key，则需要end先走；若选择最右边的数据作为key，则需要bengin先走）。
在走的过程中，若end遇到小于key的数，则停下，begin开始走，直到begin遇到一个大于key的数时，将begin和right的内容交换，end再次开始走，如此进行下去，直到begin和end最终相遇，此时将相遇点的内容与key交换即可。（选取最左边的值作为key）
此时key的左边都是小于key的数，key的右边都是大于key的数
将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作，此时此部分已有序

代码

// arry[10]: arry | 0 | 9
void QuickSort(int* arry, int begin, int end)
{
	int left = begin;
	int right = end;
	if (left >= right)return; // 只有一个数或区间不存在
	int key = *(arry + left);
	while (left<right)
	{
		// 右边选小
		while (*(arry+right)> key && right>left)
		{
			right--;
		}
		// 左边选大
		while (*(arry + left) < key && right > left)
		{
			left++;
		}
		int temp = *(arry + right);
		*(arry + right) = *(arry + left);
		*(arry + left) = temp;
	}
	int mid = left;
	QuickSort(arry, begin, mid-1);
	QuickSort(arry, mid+1, end);
}