1、堆排序
时间复杂度：O(NlogN)
这里可以分解为两个过程：建堆、进行排序
①建堆：实际上是一个Insert操作，不断的将元素加入堆中，从而按照待排序数列的顺序构建一个堆。
建堆
这里建一个大根堆，因为要满足堆得特性（即父节点>子节点），需要对插入的元素进行判定，比较它和它的父节点的值，如果新插入的值比较大，便交换两个的位置，这里涉及到一个交换的函数Swap（）
Swap（）函数
②排序：堆排的主要过程是：
A，将根与最后一个节点交换；
B，调整除了最后一个节点之外的堆，使得这个长度为size-1的堆能够符合堆得特性；
C，重复A、B的操作，直到排到根。
主要代码如下：
Heapify（）函数是调整堆结构的函数，即从根节点开始比较该节点与左右孩子节点的值，比较三者的大小，将最大的置换为父节点，同时，置换完成后将指针下沉到被置换的孩子节点，重复上述操作，直到调整完整个堆得结构。
HeapSort（）线调用HeapInsert完成建堆，随后不断循环调用Swap（）和Heapify（）函数完成置换一次，调整一次堆结构的目的，从而通过多次循环实现对整个堆的排序。
2、归并排序
时间复杂度：O(NlogN)
归并排序的本质是将两个有序的数组合并成一个有序的数组，那么我们可以将待排序的数组通过一次次一分为二，然后将两个数组分别排列有序后再合并起来，这样将数组细分，分别排序后再合并从而完成整体的排序。
①细分
通过递归，将数组不断的一分为二，start—mid视为第一个数组，mid+1—end视为第二个数组，然后调用函数Merge（）堆两个有序数组合并
②合并
合并的本质是不断比较两个数组中的元素，两个指针分别指向两个数组（注意：这里的两个数组实际还是待排序数组的前后两部分，即start—mid和mid+1—end，而不是单独的两个数组）中的元素，比较之后将较小的元素填入新的数组，然后指针后移一位，重复比较的操作实现合并，需要注意的是：当其中一个数组的指针已经指向最后一个元素后，直接将另一个数组的剩余元素填入新的数组即可，因此需要设定两个判定条件，来判断是哪一个数组先填完。
通过调用这两个函数即可完成对整个数组的排序。
3、快速排序
时间复杂度：O(NlogN)
快速排序本质上是先设定一个key值，将数组中的所有元素和key进行比较，将所有比key小的元素放在左边，所有比key大的元素放在右边，然后在左右两个以key值分界的数组中重复上述操作，不断的通过与key值得比较，完成对数组的排序。
left指针从前向后，找到第一个比key大的值，right指针从后向前，找到第一个比key小的值，两者交换，然后指针继续往中间汇集，直到两者相遇，完成一次排序。
主程序
完成后，调整key的值，然后对左右两个由key分割开来的数组重复上述排序操作，通过递归调用，实现对整个数组的排序。
注意：key值的选取，这里使用待排数组的第一个元素的值，如果数组是从大到小排列的，那么此时将面临最坏的情况，时间复杂度上升到O（N2），这是我们不想见到的，因此可以random数组中的一个元素，从而消除这种最坏的情况。
网友评论