快速排序

测试用例： 5 2 1 6 4 7 9 0 8 3

思路：采用的分治算法，结合递归。

1.选择一个基准值，把数组中比基准值大的数据放到基准值的右边，把比基准值小的元素放到左边。（这时，基准值被放在了正确的位置） 2.对基准值左边的数组和右边的数组不但进行步骤1。 3.递归的结束条件是小区间内没有数据或者数据只有一个。即 left>right 或者 left == right

时间复杂度： 平均：O(nlogN) 每次把一个基准值放到最终合适的位置，时间复杂度是longN,一共有n个元素 最坏：O(n^2)

稳定性：不稳定

优化版本：对于快速排序来说，在数组有序时，时间复杂度最高，可以通过基准值的选取来优化。 可以采用随机数法，使得基准值为数组中的任意可能位置； 但是最常用的还是三数取中法，在数组的首，尾和中间处取三个值，选择三个数第二大的数作为基准值。

int GetLocation(int arr[], int left, int right) { //如何将基准值方法合适的地方（也就是将区间划分成 小于基准值，大于基准值，和基准值 三个区间） //方法：从前往后找比基准值大的数据，从后往前找比基准值小的元素，交换这两个数据， //如果是左边的数为基准值，先让右边的数向左移动找比基准值小的， //最后有一步要交换基准值和从右往左走的停下来的位置上的数据 int begin = left; int end = right; int pivot = arr[left]; while (begin < end) { while (begin < end && arr[end] > pivot) end--; while (begin < end && arr[begin] <= pivot) begin++; Swap(&arr[begin],&arr[end]); } //交换的是数组中的内容，而不是随便一个变量和数组中的数据 Swap(&arr[left], &arr[end]); return end; } void QuickSort(int arr[], int left, int right) { if (left >= right) return; int pivotIndex = GetLocation(arr, left, right); QuickSort(arr, left, pivotIndex-1); QuickSort(arr, pivotIndex + 1, right); return; }

---

堆排序

例子：5 2 1 6 4 7 9 0 8 3

首先明确什么是堆： 堆是一种逻辑上是树形结构，但是实际上是数组线性结构的一种数据结构。 堆的性质：大堆的每个节点要比自己的孩子节点大或相等。 思路： 堆排序首先是要建堆, 升序，需要建大堆， 但是建立一次大堆只能找到一个最大的数，所以要对n个数据 进行排序就需要建n次堆， 每建好一次堆，就让和最后一个数据交换，然后在缩小数据规模。

步骤： 1.创建大堆 2.交换大堆第一个元素和最后一个元素 3.每次对这个建好的对进行向下调整，也就是对arr[0]元素进行向下调整

时间复杂度： 平均：O(nlog(n)) 每次向下调整只能确定一个最大的值，然后和数组末尾元素交换， 因此是n，向下调整的时间复杂度是logn，综合结果就是O(nlog(n))空间复杂度： O(1) 没有额外空间开销稳定性：不稳定 void AdjustDown(int tree[], int size, int parentIndex) { int leftIndex = parentIndex * 2 + 1; int rightIndex = parentIndex * 2 + 2; //先判断有没有右孩子 if (leftIndex >= size) { return; } int maxIndex = leftIndex; //假设左右孩子中，左孩子是较大值 if (rightIndex < size && tree[rightIndex] > tree[leftIndex]) //如果想要比较左孩子和右孩子的大小，必须确保右孩子存在，并且要先判断右孩子是否存在 maxIndex = rightIndex; //比较根 与 左右孩子中较大的值的大小 if (tree[parentIndex] > tree[maxIndex]) return; else { //交换根和 孩子节点中较大的值 Swap(tree + parentIndex, tree + maxIndex); //为了保证堆的性质不被破坏，所以要对更换后的位置继续调整 AdjustDown(tree, size, maxIndex); } } void CreateBigHeap(int arr[], int size) { for (int i = (size - 2)/2; i >= 0; i--) { AdjustDown(arr,size,i); } } void HeapSort(int arr[], int size) { //从最后一个非叶子节点开始，逐渐往前面进行向下调整，建立大堆， //全部调整只能找到最大值 CreateBigHeap(arr, size); for (int i = 0; i < size; i++) { Swap(arr+0, arr+size-1-i); AdjustDown(arr,size-i-1, 0); } }