当前位置：首页 > article >正文

数据结构和算法｜排序算法系列（五）｜排序总结（时间复杂度和是否稳定）

article 2024/9/22 16:05:59

文章目录

选择排序
冒泡排序
插入排序
快排
归并排序
堆排序

选择排序

一句话总结，开启一个循环，每轮从未排序区间选择****最小的元素，将其放到已排序区间的末尾。「未排序区间一般也放在后面，已排序区间放在前面」

选择排序

时间复杂度：O(n^2)
非稳定排序

void selectionSort(vector<int>& nums) {
	// 未排序区间逐渐缩小
	for (int i = 0; i < nums.size(); i++) {
		int k = i;
		// 找到未排序区间中最小的值与排序区间最后一个值交换
		for (int j = i + 1; j < nums.size(); j++) {
			if (nums[j] < nums[k]) k = j;
		}
		swap(nums[i], nums[k]);
	}	
}

冒泡排序

通过连续得比较与交换相邻元素实现排序。这个过程就像气泡从底部升到顶部一样。

冒泡过程可以利用元素交换操作来模拟：从数组最左端开始向右遍历，依次比较相邻元素的大小，如果“左元素>右元素”就交换二者。遍历完成后，最大的元素会被移动到数组的最右边。

<交换完成后，最大的泡泡浮出水面>

在这里插入图片描述
与选择排序的未排序区间不一样：
冒泡排序的未排序区间是前面的元素。

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

时间复杂度O(n^2)
稳定排序：在“冒泡”中遇到相等元素不交换

插入排序

插入排序像手动整理手牌一样。

分两个区，排序区和未排序区。

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

一句话就是把第一个元素定为已排序区，然后把未排序区的第一个元素作为待定元素插入到一排序区中。

算法流程：

初始状态下，第一个元素已经完成排序；
选取第二个元素作为 base ，将其插入到正确位置后，此时已排序区中有两个元素
以此类推，最后一轮中，选取最后一个元素作为 base，将其插入到正确位置后，所有元素均已排序。

在这里插入图片描述

voidd insertSort(vector<int> &nums) {
	// 外循环：已排序区[0, i - 1]
	for (int i = 1; i < nums.size(); i++) {
		int base = nums[i], j = i - 1;
		// 内循环来插入
		while (j >= 0 && nums[j] > base) {
			nums[j + 1] = nums[j];//指针向右移
			j--;
		}
		nums[j + 1] = base; // 将 base 赋值到正确位置
	}
}