leetcodehot100刷题——排序算法总结

冒泡排序

介绍

冒泡排序（Bubble Sort）是一种简单的比较排序算法，其工作原理类似于气泡在水中上升的过程。它通过重复遍历要排序的列表，比较相邻的两个元素，如果它们的顺序不正确就交换它们的位置。这个过程会持续进行，直到整个列表没有需要交换的元素为止。

步骤（以升序排序为例）

1. 从列表的第一个元素开始，比较相邻的两个元素，如果前者比后者大，则交换它们的位置。
2. 继续这个过程，直到遍历完整个列表。此时，最大的元素会“冒泡”到列表的末尾。
3. 重复以上过程，每次遍历的范围逐渐减少（因为每次遍历都会把最大的元素放在正确的位置），直到整个列表有序。

算法实现

void bubbleSort(vector<int> &arr){
	int n=arr.size();//复习size()
	for(int i=0;i<n-1;i++){//控制比较次数
		for(int j=0;j<n-1-i;j++){//控制相邻元素的比较和交换，上层循环完一次，最大的数会到最右边固定住，所以循环次数是n-1-i
		if(arr[j]>arr[j+1]{
			swap(arr[j],arr[j+1]);
			}
		}
	}
}

复杂度分析

时间复杂度

（1）最好情况：当输入数组已经是有序的时候，冒泡排序只需要遍历一次数组即可完成排序。时间复杂度为 O(n)。
（2）最坏情况：当输入数组完全倒序时，每两个相邻元素都需要进行比较和交换，时间复杂度为 O(n^2)。
（3）平均情况：对于一个随机排列的数组，需要进行多次比较和交换操作，时间复杂度为 O(n^2)。

空间复杂度

冒泡排序是一种原地排序算法，它只需要一个额外的临时变量用于交换元素，不需要额外的空间。因此，其空间复杂度为 O(1)。

是否为稳定排序：是

稳定排序的定义

如果一个排序算法能够保证在排序后，数据中相同元素之间的相对顺序与排序前相同，那么这个算法就是稳定排序算法。

在冒泡排序中，当比较和交换相邻元素时，只有当前者大于后者时才会交换它们的位置。如果两个元素相等，它们不会被交换，因此它们的相对顺序得以保持不变。

选择排序

介绍

选择排序（Selection Sort）工作原理是：每次从未排序的部分中找到最小（或最大）的元素，然后将其交换到未排序部分的起始位置，直到整个数组排序完成。

步骤（以升序排序为例）

1.从数组的第 i 个元素开始，找到从第 i 到第 n−1 个元素中最小的元素。
2. 将找到的最小元素与第 i 个元素交换位置。
3. 重复步骤 1 和 2，每次从下一个位置开始，直到整个数组有序。

算法实现

void selectionSort(vector<int> &arr){
	int n=arr.size();//复习size()
	for(int i=0;i<n-1;i++){//对应步骤1的话
		int minIndex=i;// 当前最小元素的索引
		for(int j=i+1;j<n;j++){
			if(arr[j]<arr[minIndex]){
				minIndex=j;
			}
		}
		// 将找到的最小元素与第 i 个元素交换
		if(minIndex!=i)
			swap(arr[minIndex],arr[i]);
	}
}

复杂度分析

时间复杂度

（1）最好情况：即使数组已经完全有序，选择排序仍然需要遍历整个数组来寻找最小元素。因此，最好情况下的时间复杂度为O(n^2)。
（2）最坏情况：数组完全倒序时，同样需要遍历整个数组，且每次都需要交换元素。最坏情况下的时间复杂度为 O(n^2)。
（3）平均情况：对于一个随机排列的数组，需要进行多次比较和交换操作，时间复杂度为 O(n^2)。

空间复杂度

选择排序是一种原地排序算法，它只需要一个额外的临时变量用于交换元素，不需要额外的空间。因此，其空间复杂度为 O(1)。

是否为稳定排序：否

选择排序不是稳定排序算法。在选择排序中，当找到一个更小的元素并与前面的元素交换时，可能会改变相同元素之间的相对顺序。

举个栗子！

假设有一个数组 [3a, 3b, 2]，其中 3a 和 3b 是两个值相同的元素，但它们的相对顺序在排序前是 3a 在前，3b 在后。我们的目标是通过选择排序对这个数组进行升序排序。
（1）第一轮：

• 初始数组：[3a, 3b, 2]
• 从索引 0 开始，寻找数组中最小的元素。
• 比较 3a、3b 和 2，发现最小元素是 2，位于索引 2。
• 将 2 与 3a 交换位置。
• 结果数组：[2, 3b, 3a]
  （2）第二轮：
• 数组状态：[2, 3b, 3a]
• 从索引 1 开始，寻找子数组 [3b, 3a] 中的最小元素。 比较 3b 和3a，它们的值相同，因此最小元素可以认为是任意一个。 由于 3b 在索引 1，而 3a 在索引 2，但它们的值相同，所以不需要进行交换。
• 结果数组：[2, 3b, 3a]
  （3）第三轮：
• 数组状态：[2, 3b, 3a]
• 从索引 2 开始，子数组只剩下 [3a]，已经有序，无需操作。
• 最终数组：[2, 3b, 3a]

可以发现：排序后的数组是 [2, 3b, 3a]。虽然数组已经按值正确排序，但原来的 3a 和 3b 的相对顺序发生了变化。
so，不稳定！