五、选择排序
1、直接选择排序
- 基本思想：
每一次遍历待排序的数据元素从中选出最小（或最大）的一个元素，存放在序列的起始（或者末尾）位置，直到全部待排序的数据元素排完
- 动图展示：
- 实现代码：
// 选择排序 void SelectSort(int* a, int n) { int begin = 0, end = n - 1;//记录下标 while (begin < end) { int mini = begin; for (int i = begin; i <= end; i++) { //遍历找到最小数据并记录下标 if (a[i] < a[mini]) mini = i; } Swap(&a[begin], &a[mini]);//交换 begin++;//缩小范围 } }
这里我们还可以对直接选择排序做一个优化：每次遍历待排序数据找出最大和最小的数据，分别排列到序列起始和末尾
- 优化代码：
// 选择排序（优化版） void SelectSort(int* a, int n) { int begin = 0, end = n - 1; while (begin < end) { int maxi = begin, mini = begin; for (int i = begin; i <= end; i++)//遍历找到最大最小的下标 { if (a[i] > a[maxi]) maxi = i; if (a[i] < a[mini]) mini = i; } Swap(&a[begin], &a[mini]);//交换 //当最初始位置begin与对大数据下标重合的情况 if (begin == maxi)//修正下标位置 maxi = mini; Swap(&a[end], &a[maxi]); begin++;//缩小范围 end--; } }
- 直接选择排序的特性总结：
- 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：不稳定
2、堆排序
堆排序是指利用堆（数据结构）进行选择数据的一种排序算法
基本思想:
原则：
先将原数组建成堆，需要注意的是排升序要建大堆，排降序建小堆
注：以大堆为例
建堆：
一个根节点与子节点数据如果不符合大堆结构，那么则对根节点数据进行向下调整，而向下调整的前提是左右子树也符合大堆结构,所以从堆尾数据的根节点位置开始向下调整建大堆
排序：
大堆堆顶数据一定是待排数据中最大的，将堆顶数据与堆尾数据交换,交换后将除堆尾数据看成新堆，对现堆顶数据进行向下调整成大堆,以此循环直至排列完毕
向下调整：
找到子节点中的较大数据节点比较，如果父节点数据比大子节点小则交换，直到不符合则停止向下交换，此时再次构成了一个大堆结构
具体堆排序详解：堆排序超详解
动图展示：大堆排序
- 实现代码：
void Adjustdown(int* a, int n,int parent) { int child = parent * 2 + 1; while (child < n) { //找到数据大的子结点 if (child + 1 < n && a[child + 1] > a[child]) { child++; } //父节点数据小于子节点就交换 if (a[parent] < a[child]) { Swap(&a[parent], &a[child]); //更新下标 parent = child; child = parent * 2 + 1; } else//否则向下调整完毕 break; } } // 堆排序(升序)建大堆 void HeapSort(int* a, int n) { int i; //建大堆 for (i = (n - 1 - 1) / 2; i >= 0; i--) { Adjustdown(a, n, i); } //交换调整 for (i = n - 1; i >= 0; i--) { Swap(&a[0], &a[i]);//与当前堆尾数据交换 Adjustdown(a, i, 0);//对交换后堆顶数据进行向下调整 } }
- 直接选择排序的特性总结：
- 堆排序使用堆来选数，效率就高了很多。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(1)
- 稳定性：不稳定
六、交换排序
1、冒泡排序
- 基本思想：
每次遍历待排序数组，对相邻数据进行比较，不符合排序要求则交换
- 动图展示：
实现代码
// 冒泡排序 void BubbleSort(int* a, int n) { int i, j; for (i = 0; i < n - 1; i++)//遍历趟数 { for (j = 0; j < n - 1 - i; j++)//比较次数 { if (a[j] > a[j + 1])//升序 Swap(&a[j], &a[j + 1]);//交换 } } }
- 冒泡排序的特性总结：
- 冒泡排序是一种非常容易理解的排序
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：稳定
2、快速排序
- 基本思想为：
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列
左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值 然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止
按基准值划分左右的方式有：
1）hoare
注：基本操作过程如图示
- 实现代码：
// 按基准划分hoare版本 int PartSort1(int* a, int left, int right) { int mid = GetMidIndex(a, left, right);//三数取中（优化取基准值，后面会解释） Swap(&a[mid], &a[left]);//使得中间值永远在最左，便于决定谁先走 int key = left; while (left < right) { //Key设在左边，先从右边寻找小于a[key]的 while (left < right && a[right] >= a[key]) { right--; } //再从左边寻找大于a[key]的 while (left < right && a[left] <= a[key]) { left++; } //找到后交换 Swap(&a[left], &a[right]); } //最后相遇时将key与相遇点交换 Swap(&a[key], &a[left]); return left;//返回相遇点下标 }
key的位置与左右下标谁先走的关系：
注：对于排升序来说
一般来说在三数取中后得到中等值key，我们让该值与待排序数组的最左边起始位置交换，使得key永远在最左边，并且之后会让右下标先走找小于key的值，找到后再让左下标走找大于key的值，都找到则交换，相遇后再将key与相遇位置的值交换
右下标先走的话，对于两下标相遇的的情况只有两种：
右下标走着走着遇到左下标，此时左下标的值一定是小于key的值（交换后左下标是原来右下标的小于key的值）
左下标走着走着遇到右下标，此时右下标的值一定是小于key的是（右下标找小于key的值）
所以这样保证了最后下标相遇与key交换后，key左边区间一定小于key，右边区间一定大于key
