排序-选择排序（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]); } }选择排序优化思路普通单向选择排序每一轮只找最小值放到数组最左边已排序位置只处理一端。这份双向选择排序逻辑两个指针begin左端待排序起点end右端待排序终点一轮遍历区间[begin, end]同时找出mini当前区间最小值下标maxi当前区间最大值下标把最小值交换到a[begin]把最大值交换到a[end]begin左边界右移end--右边界左缩下一轮处理中间剩下的区间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; } }排序稳定性比较我这里只比较比较常见的七大排序冒泡快速选择插入希尔堆归并。排序稳定性插入排序稳定希尔排序不稳定选择排序不稳定堆排序不稳定冒泡排序稳定快速排序不稳定归并排序稳定结语谢谢你的观看希望可以给你提供帮助