目次
选择排序
根本头脑
图解
代码
复杂度与稳固性
堆排序
根本头脑
图解
代码
复杂度与稳固性
选择排序
根本头脑
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。 图解
给定如下数组，排成升序： 1.从五个数值中选定最大的数字5，与末了一个数值1举行交换：
2.从剩下四个数值中选定一个最大的，与末了一个数值3举行交换：
3.从剩下的三个数值中选定一个最大的，与末了的数值1举行交换：
4.从剩下两个数值中选定一个最大的，与末了的数值1举行交换，完成排序：
代码
- void SelectSort(int* arr,int size){//选择排序
- for (int i = 0; i < size - 1; i++){
- int pos = 0;//每次从第一个值开始选
- for (int j = 1; j < size-i; j++){
- if (arr[j]>arr[pos]){
- pos=j;//记录最大值的位置
- }
- }
- Swap(&arr[pos],&arr[size-1-i]);
- }
- }
代码中，pos纪录数组中最大值的位置，每一轮比力都会把最大值放置在:size-i的位置，从而实现了选择排序。
复杂度与稳固性
时间复杂度：n个元素，举行n-1轮选则，每轮举行比力的次数从n-1递减到1。以是根本语句的实行次数满足等差序列，举行盘算去掉系数后复杂度为：O(N^2)
空间复杂度:没有利用额外空间，复杂度为O(1)
稳固性：有跨区间交换，不稳固
堆排序
根本头脑
堆排序 (Heapsort) 是指利用堆积树（堆）这种数据结构所操持的一种排序算法，它是选择排序的一种。它是 通过堆来举行选择数据。必要留意的是排升序要建大堆，排降序建小堆。 图解
在之前的文章中已经具体报告了建堆的过程 (3条消息) 堆的实现（C语言）_Enthusiastic_boy的博客-CSDN博客_c语言堆的实现 ，那么接下来就来直接利用堆来举行排序，如下图中有一大堆： 1.利用堆删除的头脑，起首交换堆顶元素和堆末了一个元素：
2.撤消堆末了一个元素的剩余部门，从堆顶开始举行建堆：
3.交换上图赤色部门的堆顶元素4和末了元素1：
4.对上图赤色圈起来部门举行建堆：
5.交换上图赤色圈起来部门的堆顶元素和末了元素：
6.对上图赤色圈起来的部门举行建堆：
7.交换上图中赤色圈起来部门的堆顶元素和末了元素，完成排序：
代码
- void HeapAdjust(int* arr,int size,int parent){//向下调整
- int child = parent * 2 + 1;
- while (child<size){
- if (child + 1 < size&&arr[child + 1] > arr[child]){
- child = child + 1;
- }
- if (arr[child] > arr[parent]){
- Swap(&arr[child],&arr[parent]);
- parent = child;
- child = child * 2 + 1;
- }
- else{
- return;
- }
- }
- }
- void HeapSort(int* arr,int size){//堆排序
- int parent = (size - 2) / 2;
- for (; parent >= 0; parent--){//建堆
- HeapAdjust(arr,size,parent);
- }
- for (; size>1; size--){//利用堆删除的思想进行堆排序
- Swap(&arr[0],&arr[size-1]);
- HeapAdjust(arr, size-1, 0);
- }
- }
留意：建堆时，可以以为数组中元素总数稳定，parent的值在不绝变革。举行堆排序时可以以为parent的值稳定，不停是0，而数组元素个数在变革。这两个过程刚好相反。
复杂度与稳固性
时间复杂度:排序时每次都是从堆顶开始建堆，以是建堆的时间复杂度为O(logN),而要举行N次建堆，以是总的堆排序时间复杂度为：O(NlogN)。
空间复杂度：没有借助辅助空间，以是复杂度为：O(1)
稳固性：举行了跨区间交换，不稳固
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ | 
