本节研究快速排序、堆排序、最大优先级队列，并给出C++核心代码；
快速排序
特点：（1）快速排序，平均复杂度为O(NlogN)；T(N) = 2T(N/2) + cN;可推出时间复杂度为O(NlogN)；最坏的时间复杂度是O(N*N)；可通过随机取枢纽元或取三数中值取枢纽元来加以避免；快速排序不是稳定的排序，空间复杂度是O（1）；
（2）基于的是典型的分治法，可以利用递归或非递归（栈）来实现子程序的快排调用；是在实践中最快的已知排序算法，快速的原因主要是精炼和高度优化的内部循环；
（3）在Java中一般将归并排序作为排序方法，因为在Java中元素的比较耗时，而移动元素则要快的多，而归并排序使用了较少的比较次数；而在C++中使用快速排序作为默认排序，因为对象的复制消耗很大，归并排序也就不适合了，而比较相对消耗比较少；
pivot的划分方法
划分方法1，，未随机选取；（完整程序）
//第1种划分int _partitionNormal1(vector<int>& array, int left, int right){ int pivot = array[right]; int x = left; for (int i = left; i < right; ++i){if (array[i] < pivot){swap(array[x], array[i]);++x;}} swap(array[x], array[right]);return x;}//递归快排void _quickSortRecursive(vector<int>& array, int left, int right){ if (left >= right)return;int x = _partitionNormal1(array, left, right);//can change partition _quickSortRecursive(array, left, x – 1); _quickSortRecursive(array, x + 1, right);}void quickSort(vector<int>& array){ _quickSortRecursive(array, 0, array.size() – 1);}说明几点：
（1）_partitionNormal1中x指向比pivot大的数，最后将x所在的数和pivot所在的数交换，并返回位置；
（2）pivot的选取可能会造成快排的最坏的时间复杂度为O（n*n），试想一个已经排序的序列进行排序时，每次pivot都将会保持不变，即T(N) = T(N-1) + cN；那么T(N)=O(N*N);
划分方法2
//三数中值int _selectMiddle(vector<int>& array, int left, int right){ int mid = (right -left >> 1) + left; if (array[left] > array[mid])swap(array[left], array[mid]); if (array[left] > array[right])swap(array[left], array[right]); if (array[mid] > array[right])swap(array[mid], array[right]); swap(array[mid], array[right-1]); //将中间值和倒数第二个值对换return array[right – 1];}//第2种划分int _partitionMiddle1(vector<int>& array, int left, int right){ int pivot = _selectMiddle(array, left, right); if (left >= right – 2)return left; int x = left; for (int i = left; i < right – 1; ++i){if (array[i] < pivot){swap(array[x], array[i]);++x;}} swap(array[x], array[right – 1]); //交换return x;}
说明几点：
（1）_partitionMiddle中使用三数中值法，选择最中间的那个数进行划分，那么最后一个right为较大的数，left为较小的数；最后交换的数其实是和right-1数交换的；
划分方法3
//第3种划分int _partitionMiddle2(vector<int>& array, int left, int right){ int pivot = _selectMiddle(array, left, right); if (left >= right – 2)return left; int i = left; int j = right – 1;//important for (;;){while (array[++i] < pivot); //<=时，下面的i<j可能会越界while (array[–j] > pivot); //<=时，下面的i<j可能会越界if (i < j){swap(array[i], array[j]);}else{break;}} swap(array[i], array[right – 1]); return i;}说明几点：
（1）该函数极易出错，采用三数中值法后，越界问题有所减小，但是对于while (array[++i] < pivot); while (array[–j] > pivot);都要注意，因为如果加上<=或>=，那么就使得if(i<j)报错，试想如果array中所有的数目都相同，那么while (array[++i] <= pivot);while (array[–j] >= pivot);都将会越界的；
堆排序
特点
（1）堆排序，平均复杂度为O(NlogN)；最好的时间复杂度是O(NlogN)；
（2）堆排序是不稳定的排序，空间复杂度是O（1）；
（3）本题要求升序排序，因此建立的是一个大根堆，进行排序的；
核心代码
void _makeHeapDown(vector<int>& array, int top, int end){ while (left(top) < end){int leftChild = left(top);int rightChild = right(top);int min = top;if (array[top] < array[leftChild])min = leftChild;if (rightChild < end && array[min] < array[rightChild])min = rightChild;if (top == min)break;swap(array[min], array[top]);top = min;}}void heapSort(vector<int>& array){ for (int i = array.size() / 2; i >= 0; –i)_makeHeapDown(array, i, array.size()); for (int i = array.size()-1; i >= 1; –i){swap(array[i], array[0]);_makeHeapDown(array, 0, i);}}说明几点：
（1）在_makeHeapDown(vector<int>& array, int top, int end)参数中top为违反堆性质的元素位置，end是维护堆性质的位置上限（不包括end）;
最大优先级队列
特点
（1）最大优先级队列类似stl中queue的操作，只是对于元素在队列中的元素优先级是不一样的，在最大优先级中，队列头为值最大元素；
（2）可利用大根堆来维护一个最大优先级队列；向优先级队列中push元素，类似像堆的末尾添加一个元素，然后使用_makeHeapUp寻找该元素的存放位置，进而维护大根堆；当向优先级队列中pop元素，将首元素和最后一个元素对换，然后使用_makeHeapDown来从首元素向下维护大根堆，类似堆排序，最后再将尾部元素pop_back；
开始的时侯，我们就知道，总会有终结。
