排序算法

快速排序 1.快速排序 注：经典快速排序总是指定数组的最后一个元素作为基准值，随机快速排序指定数组或者某一部分中的随机值作为基准值。 （1）主要思想快速排序的主要思想是分治思想： 任取一个元素作为分界点pivot 对数组区间进行调整（调整方式有很多种），所有比pivot小的元素都放在前面，比pivot大的元素都放在后面，形成左右两个子表 递归处理左右两端区间 （2）局限性快速排序局限性： 快速排序是所有内部排序方法中最好的一个 快速排序是一种不稳定的排序方法 快速排序不是原地排序（程序中使用了递归需要递归调用栈的支持，而栈的长度取决于递归调用的深度） 平均时间复杂度O(nlog2n)：QSort—O(log2n)、Partition—O(n) 平均情况下需要使用O(logn)的栈空间，最坏情况下栈空间可以达到O(n) 快速排序不适用与对原本有序或基本有序的记录序列进行排序（划分元素值的随机性越好，排序速度越快，即非自然排序） 改变划分元素的选取方法，最多只能改变算法平均时间性能，无法改变最坏情况下的时间性能O(n2) 由于每次枢轴pivot记录的关键字都是大于其他所有记录的关键字，致使一次划分之后得到的子序列（1）的长度为0，这时的快速排序就已经退化成为了没有改进措施的冒泡排序了。 2.快速排序模板（1）思路1： 将low值取出单独存放在key中， 对数组进行排序，排序方式为：当右侧比key小时将high覆盖low处值、当左侧比key大时将low覆盖high处 直到low与high相遇时，将key放回low与high相遇的位置 一轮排序完毕（key所在位置为最终有序位置） 递归处理左右两边区间 1234567891011121314151617181920//写法1:使用2个变量 low highint partition(int arr[], int low, int high) { int key = arr[low];//取low处元素的值作为比较参考 while(low < high) {\] while(low < high && arr[high] >= key) --high;//右侧比key元素大的元素结点不动 arr[low] = arr[hi ...

归并排序 1.归并排序（1）基本思想 确定分界点mid = (low + high) / 2 先对左边进行归并排序，然后对右边进行归并排序 将两个有序子序列归并为一个有序序列 （2）归并排序特性 归并排序时间效率为O（nlog2n） 归并排序空间效率为O（n） 归并排序是一个稳定的排序算法 注：关于2路归并的归并树（倒立的二叉树） 二叉树的第h层最多有2h-1个结点，即满足 n ≤ 2h-1 即为 h - 1 = $\lceil log_2n \rceil$ n个元素进行2路归并，归并趟数为$\lceil log_2n \rceil$ 2.归并排序模板12345678910111213141516171819202122//写法1:for循环写法//[low...mid]和[mid+1...high]各自有序 将两个部分归并void merge(int A[], int n, int low, int mid, int high) {//需要传入数组大小n以节省不必要的空间浪费 int i, j, k; int *B = (int *)malloc(n * sizeof(int));//辅助数组B for (k = low; k <= high; ++k) B[k] = A[k]; for (i = low, j = mid + 1, k = i; i <= mid && j <= high; ++k) {//核心归并操作 if (B[i] <= B[j]) A[k] = B[i++]; else A[k] = B[j++]; } while(i <= mid) A[k++] = B[i++];//未归并完的部分直接复制到尾部 while(j <= high) A[k++] = B[j++];}void mergeSort(int A[], int n, int low, int high) { if (low < high) { int mid = (low + high)/2;//从中间划分 mergeSort(A, n, ...