数据结构与算法_排序算法_冒泡排序和选择排序

后面的几个笔记写排序算法：冒泡排序，选择排序，插入排序，希尔排序，快速排序，归并排序，堆排序，基数排序等。

冒泡排序

特点：相邻元素两两比较，把值大的元素往下交换；冒泡排序是所有排序算法中，效率最低的。
缺点：数据交换的次数太多了。
优化： 如果某次不需要交换，直接退出程序。
时间复杂度：两个for循环，每个都是O(n)，所以冒泡排序是O(n^2); 最好的情况下是O(n)，就是比较一趟后，发现flag还是flase，直接退出；
空间复杂度：O(1) 没有占用其他空间。
稳定性定义：在原始的数据中，相同元素，经过排序后，他们的前后顺序并没有改变，就是稳定的，否则是不稳定的。
冒泡是稳定的，因为在交换数据时候，只有相邻两个数大才会交换。

效率：冒泡排序不断的交换数据，导致效率低下。

void BubbleSort(int arr[], int size)
{
	for (int j = 0; j < size - 1; j++)  // size - 1 最后一趟不用比较了 O(n)
	{
		// 一趟的处理
		bool flag = false;  // 加flag 优化
		for (int i = 0; i < size - 1 - j; i++) // 这里要size - 1;否则最后越界 O(n)
		{
			if (arr[i] > arr[i + 1])
			{
				int tmp = arr[i];
				arr[i] = arr[i + 1];
				arr[i + 1] = tmp;
				flag = true;
			}
		}

		if (!flag)
		{
			return;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

选择排序

思想：每次在剩下的元素中选择值最小的元素，和当前元素进行交换。
缺点：相比于冒泡排序，交换的次数少了，但是比较的次数依然很多。
相比冒泡排序：比冒泡排序效率高一些，不用频繁的交换。
是否能优化：不能优化，每次必须比较
时间复杂度：O(n) * O(n)
空间复杂度：O(1)
**稳定性：**不是稳定的排序算法； 比如 5(1) 5(2) 3 三个数据，第一趟：3 5(2) 5(1)

void ChoiceSort(int arr[], int size)
{
	for (int i = 0; i < size - 1; i++) // O(n) 
	{
		int min = arr[i];   
		int k = i; // 最小的下标			// O(n) 
		for (int j = i + 1; j < size ; j++) // 每次从最小值后面开始比较
		{
			if (arr[j] < min)
			{
				min = arr[j];
				k = j;  // 记录最小值的下标
			}
		}
		if (k != i)
		{
			int tmp = arr[i];
			arr[i] = arr[k];
			arr[k] = tmp;
		}

	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24