C++实现排序算法

冒泡算法

将元素进行两两比较，将大的元素往后移动

平均时间复杂度是O(n^2)，最坏时间复杂度是O(n^2)，最好时间复杂度是O(n)，排序结果具有稳定性。

这里所提到的稳定性主要是针对相同元素而言的，比如5,5,3进行冒泡排序，第一个5始终在第二个5的前面，这两个5的顺序不会发生变化。

void bubblesort(int arr[], int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		bool finished = true;
		for (int j = 0; j < n - 1-i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				swap(arr[j], arr[j + 1]);
				finished = false;
			}
		}
		if (finished)return;//如果finished为true就代表没有元素发生交换，也就是说所有元素都已经有序了
	}
}

选择排序算法

 假设队首元素为最小值，然后遍历后续的元素找到真正的最小值，并与队首进行交换，每次在剩余元素中选择最小的元素与当前元素进行交换。

平均时间复杂度是O(n^2)，最好时间复杂度是O(n^2)，最坏时间复杂度是O(n^2)，排序结果不稳定。

假如有一个5,5,3的序列，那么当使用选择排序进行排序时，第一个5就和最后的一个3进行交换了，但实际上第一个5是在第二个5的前面的，但是排完序后，第一个5到第二个5后面去了，所以是不稳定的。

void choicesort(int arr[], int n)
{

	for (int i = 0; i < n; i++)
	{
		int min_element = arr[i];
		int min_index = i;
		for (int j = i; j < n; j++)
		{
			if (arr[j] < min_element)
			{
				min_element = arr[j];
				min_index = j;
			}
		}
		swap(arr[i], arr[min_index]);
	}
}