前文知识清单:
一、选择排序
直接选择排序通过每一轮的比较,找到最大值和最小值,将最大值的节点跟右边交换,最小值节点跟左边交换,达到排升序的效果。
一图看懂直接选择排序:
void SelectSort(ShellDataType* a, int n) { //左下标 和右下标 int left = 0; int right = n - 1; //不需要left <= right,最后一个元素不需要再交换,当然给<=也没问题 while (left < right) { //假设最小最大全部在left int 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-1 for (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)