NzN的数据结构--选择排序

接上文，本章我们来介绍选择排序。先三连后看才是好习惯~~~

一、基本思想

二、直接选择排序

三、堆排序

一、基本思想

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

二、直接选择排序

在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素
若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//选择排序
void SelectSort(int* a, int n)
{int begin = 0;int end = n - 1;while (begin < end){int mini = begin;int maxi = begin;for (int i = begin + 1; i <= end; i++) {if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}if (maxi == begin){maxi = mini;}Swap(&a[begin], &a[mini]);Swap(&a[end], &a[maxi]);begin++;end--;}
}

三、堆排序

堆排序算法我们已经在二叉树part2部分详细讲解过了，如果还不理解，可以再返回学习一下。

堆排序(Heapsort)是指利用堆积树（堆）所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

//大堆的向下调整算法
void AdjustDown(HPDataType* a, int size, int parent)
{int child = parent * 2 + 1;while (child < size){//默认左孩子大，假设错误就更新一下  if (child + 1 < size && a[child] < a[child + 1]) //右孩子存在且右孩子大于左孩子  {++child; // child原本是左孩子，+1变成右孩子  }//如果子节点大于父节点则交换 if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}//升序建大堆，降序建小堆
//建小堆如果想要升序，堆顶元素在对应位置，剩余元素重新建小堆，时间复杂度大大增加
void HeapSort(int* a, int n)
{//对数组直接建堆for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, n, i);}// O(N*logN)int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);//上面建的大堆，根节点最大，把大的数据往后放AdjustDown(a, end, 0);//新的根节点可能会破坏大堆性质，需要向下调整end--;}
}

堆排序的特性总结：