前文知识清单：

一、选择排序

直接选择排序通过每一轮的比较，找到最大值和最小值，将最大值的节点跟右边交换，最小值节点跟左边交换，达到排升序的效果。

一图看懂直接选择排序：

void SelectSort(ShellDataType* a, int n)
{//左下标 和右下标int left = 0;int right = n - 1;//不需要left <= right，最后一个元素不需要再交换,当然给<=也没问题while (left < right){//假设最小最大全部在leftint mini = left, maxi = left;//单趟查找最小值和最大值下标for (int i = left; i < right; i++){//找到最小的，更新下标if (a[i] < a[mini]){mini = i;}//找到最大的，更新下标if (a[i] > a[maxi]){maxi = i;}}//maxi和right交换，mini和left交换Swap(&a[left], &a[mini]);//这里存在特殊情况，如果maxi在left位置，left和mini交换了之后，最大值的下标就是mini了//所以这里需要判断一下，如果真的是这种情况，就更新最大值下标。if (maxi == left){maxi = mini;}Swap(&a[right], &a[maxi]);//后面的不需要再更新了，因为后面就算mini是在right位置，这轮也已经结束了，所以不需要再管它//更新left和right 的下标left++;right--;}}

直接选择排序时间复杂度

每一轮比较都需要遍历数组，查找最大最小值，第一轮遍历N个数据，第二轮是N-2个数据，第三轮N-4 …，遍历次数为：N+N-2+N-4+…+1，一个等差数列求和

所以总的时间复杂度为O(N^2)

二、堆排序

向上调整算法和向下调整算法请参照：数据结构——堆

所谓堆排序，就是排序堆，要求是堆才能够进行排序，所以给任意一个连续数组对数组排序的话，需要先建堆。

使用向上调整法建堆如下图：

结果如下：

时间复杂度为O(N*logN)

使用向下调整建堆如下图：

时间复杂度O(N)

堆排序：

堆排序使用交换之后再向下调整原理：
在建了大根堆之后，堆顶的左右子树都是大根堆，不管最后一个元素是否是最小的，与堆顶元素交换后,
堆顶元素就被放到了堆尾，然后再让堆顶元素向下调整，因为此时堆顶元素是一个较小的元素，会向下调整，调整之后是第二大的元素在堆顶下一次再排序时，排的是堆尾的前一个了，那个最大的元素不用再排了，排的就是第二大的元素，
再让堆的最后一个元素与堆顶元素交换，再进行向下调整，调整完后第三大的元素就上来了。

建好堆后，对堆进行排序，堆排序过程图如下：

堆排序代码如下：

void HeapSort(int* a, int n)
{assert(a);//1.先建堆，向上调整建堆,建堆的时间复杂度为O(N*logN)//也可以采用向下调整的方法建堆，向下调整的方法建堆的时间复杂度为O(N)//强烈建议采用向下调整的建堆方式//for (int i = 0; i < n; ++i)//{//	AdjustUp(a, i);//}//向下调整建堆，是从第一个非叶子节点开始调整，因为所有的叶子节点都不需要进行向下调整//child = (parent-1)/2//此时parent就是n-1for (int i = (n - 1 - 1) / 2; i >=0; -- i){AdjustDown(a, n, i);}//现在是大根堆//2.堆排序，采用向下调整算法进行排序,让最后一个节点和堆顶节点进行交换，然后堆顶节点向下调整//调整完后继续倒数第二个节点和堆顶节点交换,以此类推for (int i = n-1; i >0; --i){swap(&a[0], &a[i]);//这里传参不能传n，传n-1,因为交换之后最后一个数字就不需要参与进来了，相当于size--//堆排序使用交换之后再向下调整原理：//在建了大根堆之后，堆顶的左右子树都是大根堆，不管最后一个元素是否是最小的，与堆顶元素交换后//堆顶元素就被放到了堆尾，然后再让堆顶元素向下调整，因为此时堆顶元素是一个较小的元素，会向下调整，调整之后是第二大的元素在堆顶// //下一次再排序时，排的是堆尾的前一个了，那个最大的元素不用再排了，排的就是第二大的元素，//再让堆的最后一个元素与堆顶元素交换，再进行向下调整，调整完后第三大的元素就上来了。AdjustDown(a, i, 0);}//总结：排升序的话，建大根堆//排降序建小根堆for (int i = 0; i < n; i++){printf("%d ", a[i]);}
}

堆排序时间复杂度

建堆的时间复杂度为O(N)
调整过程遍历N个数的时间复杂度为O(N)
每次调整一个数的时间复杂度为O(logN)
总的时间复杂度为O(N+N*logN)
综上：

堆排序的时间复杂度为：O(N*logN)

409小游戏攻略网