算法与数据结构——简单排序算法（选择、冒泡、插入）

news/2024/9/28 1:10:26

简单排序算法

时间复杂度均为O(n²)

选择排序

选择排序（selection sort）的工作原理非常简单：开启一个循环，每轮从未排序区间选择最小的元素，将其放到已排序的区间的末尾。

算法流程

设数组长度为n，选择排序的算法流程如下。

初识状态下，所有元素未排序，即未排序（索引）区间为[1, n-1]。
选取区间[0，n-1]中的最小元素，将其与索引0处的元素交换。完成后，数组前1一个元素已排序。
选取区间[1，n-1]中的最小元素，将其与索引1处的元素交换，完成后，数组前2个元素已排序。
以此类推。经过n - 1轮选择与交换后，数组前 n-1个元素已排序。
仅剩的一个元素必定是最大元素，无需排序，因此数组排序完成。

/*选择排序*/
void selectionSort(vector<int> &nums){int n = nums.size();// 外循环：未排序区间为[i , n-1]for (int i = 0; i < n - 1; ++i){int  k = i;// 内循环：找到未排序区间的最小元素for (int j = i; j < n; ++j){if (nums[j] < nums[k])k = j;}// 将该最小元素与未排序区间的首个元素交换swap(nums[i], nums[k]);}
}

算法特性

时间复杂度为O(n²)、非自适应排序：外循环共n-1轮，第一轮的未排序区间长度为n，最后一轮的未排序区间长度为2，即各轮外循环分别包含 𝑛、𝑛 − 1、…、3、2 轮内循环，求和为 (𝑛−1)(𝑛+2)/2 。
空间复杂度为O(1)、原地排序：指针i和j使用常数大小的额外空间。
*非稳定排序**：如下图所示，元素nums[i]有可能被交换至与其相等的元素右边，导致两者的相对顺序发生改变。

冒泡排序

冒泡排序（bubble sort）通过连续地比较与交换相邻元素实现排序。整个过程就像气泡从底部升到顶部一样，因此得名冒泡排序。

冒泡过程可以利用元素交换操作来模拟：从数组最左端开始向右遍历，依次比较相邻元素大小，如果相邻左边的元素大于右边，则交换两者位置，这样最大的数就会逐渐冒到右端。

算法流程

设数组长度为n，冒泡排序步骤如下。

首先，对n个元素执行“冒泡”，将数组的最大元素交换至正确位置。
接下来，对剩余n-1个元素执行“冒泡”，将剩余元素中的最大元素交换至正确位置。
以此类推，经过n-1轮“冒泡”后，前n-1大的元素都被交换至正确位置。
仅剩的一个元素必定是最小元素，无需排序，因此数组排序完成。

/*冒泡排序*/
void bubbleSort(vector<int> &nums){int n = nums.size();// 外循环：未排序区间为 [0, i]for (int i = n - 1; i > 0; --i){// 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端for (int j = 0; j < i; ++j){if (nums[j] > nums[j + 1])// 交换 nums[j] 与 nums[j + 1]swap(nums[j], nums[j + 1]);}}
}

效率优化

可以发现，如果某轮“冒泡”中没有执行任何交换操作，说明数组已经完成排序，可以直接返回结果。因此可以增加一个标志位flag来监测这种情况，一旦出现就立即返回。

经过优化，冒泡排序的最差时间复杂度和平均之间复杂度仍为O(n²);但当输入数组完全有序时，可达到最佳时间复杂度O(n)。

/*冒泡排序(标志优化)*/
void bubbleSortWithFlag(vector<int> &nums){int n = nums.size();// 外循环：未排序区间为 [0, i]for (int i = n - 1; i > 0; --i){bool flag = true; // 初始化标志位// 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端for (int j = 0; j < i; ++j){if (nums[j] > nums[j + 1]){// 交换 nums[j] 与 nums[j + 1]swap(nums[j], nums[j + 1]);flag = false; // 记录交换元素}}if (flag)break;  // 此轮“冒泡”未交换任何元素，直接跳出}
}

算法特性

时间复杂度为O(n²)、自适应排序：各轮“冒泡”遍历的数组长度依次为 𝑛 − 1、𝑛 − 2、…、2、1 ，总和为 (𝑛 − 1)𝑛/2 。在引入 flag 优化后，最佳时间复杂度可达到 𝑂(𝑛) 。
空间复杂度为O(1)、原地排序：指针i和j使用常数大小的额外空间。
稳定排序：在“冒泡”中遇到相等元素不交换。

插入排序

插入排序（insertion sort）是一种简单的排序算法，它的工作原理与手动整理一副牌的过程非常相似。

具体来说，我们在未排序区间选择一个基准元素，将该元素与其左侧已排序区间的元素逐一比较大小，并将该元素插入到正确的位置。

下图展示了数组插入元素的操作流程。设基准元素为base，我们需要将从目标索引到base之间的所有元素右移一位，然后将base赋值给目标索引。

算法流程

初识状态下，数组的第1个元素已完成排序。
选取数组的第2个元素作为base，将其插入到正确的位置后，数组的前2个元素已排序。
选取第3个元素作为base，将其插入到正确位置后，数组的前3个元素一排序。
以此类推，在最后一轮中，选取最后一个元素作为base，将其插入到正确位置后，所有元素均已排序。

/*插入排序*/
void insertionSort(vector<int> &nums){// 外循环：已排序区间为[0, i-1]for (int i = 1; i < nums.size(); ++i){int base = nums[i], j = i - 1;// 内循环：将 base 插入到已排序区间 [0, i-1] 中的正确位置while (j >= 0 && base < nums[j]){nums[j + 1] = nums[j]; // 将nums[j]向右移动一位j--;}nums[j + 1] = base; // 将base赋值到正确位置}
}

算法特性

** 时间复杂度为O(n²)、自适应排序**：在最差情况下，每次插入操作分别需要循环 𝑛 − 1、𝑛 − 2、…、2、1 次，求和得到 (𝑛 − 1)𝑛/2 ，因此时间复杂度为 𝑂(𝑛²)。在遇到有序数据时，插入操作会提前终止，当输入数组完全有序时，插入排序达到最佳时间复杂度O(n)。
空间复杂度为O(1)、原地排序：指针i和j使用常数大小的额外空间。
稳定排序：在插入操作过程中，我么会将元素插入到相等元素的右侧，不会改变它们的顺序。