排序-选择排序（Selection Sort）冒泡排序（Bubble Sort）

目录

前言：

冒泡排序思路：

核心思想

时间复杂度：O(n^2)

代码如下：

选择排序思路

核心思想

时间复杂度：O(n^2)

代码如下：

选择排序优化思路：

优化代码如下：

排序稳定性比较

结语：

前言：

选择排序与冒泡排序比较简单，为补齐排序，就讲一下思路与时间复杂度，给一下代码。

然后补充一下所以排序的稳定性。

其他排序：

快速排序：排序-快速排序（Quick sort）（基础版）-CSDN博客

归并排序：排序-归并排序（Merge Sort）-CSDN博客

插入排序：排序—插入排序(Insertion Sort)-CSDN博客

希尔排序：排序-希尔排序(Shell Sort)-CSDN博客

冒泡排序思路：

核心思想

重复遍历数组，相邻元素两两比较，顺序错误则交换。每轮遍历后，最大元素"浮"到末尾。

冒泡排序有教学价值，但是时间复杂度比较高，使用少。

时间复杂度：O(n^2)

代码如下：

void BubbleSort(int* a, int n) { for (int j = 0; j < n; j++) { // 单趟 int flag = 0; for (int i = 1; i < n - j; i++) { if (a[i - 1] > a[i]) { Swap(&a[i - 1], &a[i]); flag = 1; } } if (flag == 0) { break; } } }

选择排序思路

核心思想

每轮从未排序区间选出最小元素，放到已排序区间的开头。

时间复杂度：O(n^2)

不管怎么样时间复杂度都比较高，因为选择排序一直都是选择最小的拿出，

代码如下：

void SelectionSort(int* a, int n) { for (int i = 0; i < n-1; i++) { int Min = i; for (int j = i + 1; j < n; j++) { if (a[Min] > a[j]) { Min = j; } } swap(a[i], a[Min]); } }

选择排序优化思路：

普通单向选择排序

每一轮只找最小值，放到数组最左边已排序位置，只处理一端。

这份双向选择排序逻辑

1. 两个指针：begin（左端待排序起点），end（右端待排序终点）
2. 一轮遍历区间[begin, end]，同时找出：
   • mini：当前区间最小值下标
   • maxi：当前区间最大值下标
3. 把最小值交换到a[begin]；把最大值交换到a[end]
4. begin++左边界右移，end--右边界左缩，下一轮处理中间剩下的区间
5. while(begin < end)循环直到左右指针相遇，排序完成

优化代码如下：

void SelectSort(int* a, int n) { int begin = 0, end = n - 1; while (begin < end) { int mini = begin, maxi = begin; for (int i = begin + 1; i <= end; ++i) { if (a[i] > a[maxi]) { maxi = i; } if (a[i] < a[mini]) { mini = i; } } Swap(&a[begin], &a[mini]); Swap(&a[end], &a[maxi]); ++begin; --end; } }

排序稳定性比较

我这里只比较比较常见的七大排序：冒泡，快速，选择，插入，希尔，堆，归并。

结语：

谢谢你的观看，希望可以给你提供帮助！！！