> For the complete documentation index, see [llms.txt](https://aye10032.gitbook.io/data-structure/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aye10032.gitbook.io/data-structure/8-pai-xu.md). # 8、排序 基于比较的排序，n个关键字，比较次数为 $$\lceil \log\_2(n!) \rceil$$ ## 1、插入排序 * 每次把一个元素插入到前面的已排序序列中 * 可以用折半查找快速找到插入位置 * 对当前插入节点前面的顺序队列使用折半查找 * 先确定位置再插入 ```c //直接插入排序 void InsertSort(int A[],int n){ int i,j, temp ; for(i=1;i=0 && A[j]>temp;-- j){ //检查所有前面已排好序的元素 A[j+1]=A[j];//所有大于temp的元素都向后挪位 } A[j+1]=temp; //复制到插入位置 } } } ``` * 空间复杂度：$$O(1)$$，使用常数辅助单元 * 时间复杂度：$$O(n^2)$$ * 最好情况：$$O(n)$$ * 本身正序 * 比较次数：$$n-1$$，只需要各与前面一个比较一次 * 无需移动 * 最坏情况：$$O(n^2)$$ * 本身倒序 * 比较次数：$$n(n-1)/2$$，不带哨兵，若带哨兵则每轮多一次与哨兵的比较 * 移动次数：$$n(n-1)/2$$，不带哨兵，若带哨兵则每轮多两次存取哨兵的值 * 折半插入排序：$$O(n^2)$$ * 比较次数少了，但是移动次数不变 * 比较次数：$$O(n\log\_2n)$$ * 稳定 * 可用于链表，但不再能使用折半查找确定插入位置 ## 2、希尔排序 * 按照不同的间隔分为几个子表 * 对每个子表进行插入排序 * 间隔每轮**缩短**一次 * 距离每次缩小一半 * 表现为每次的子表中元素数量为2、4、6…… * 直到间隔变为1 ```c //希尔排序 void ShellSort(int A[],int n){ //A[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到 for(int d= n/2; d>=1; d=d/2){ //步长变化 //遍历每一个子表 for (int i = 1; i <= d; i++) { //对每一个子表插入排序 for (int j = i + d; j <= n; j += d) { if (A[j] < A[j - d]) { A[0] = A[j]; for (int k = j - d; k > 0; k -= d) { if (A[k] > A[0]) { A[k + d] = A[k]; A[k] = A[0]; } } } } } } } ``` * 空间复杂度：$$O(1)$$，使用常数辅助单元 * 时间复杂度：最坏情况下为$$O(n^2)$$ * 不稳定 * 不适用于链表 ## 3、冒泡排序 ![](https://2472502332-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FUddTfPz1UQGspJpAxLN6%2Fuploads%2Fgit-blob-59a0fe0643d5a2d9e8b18d5b7e23d8ed8706e107%2F%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F.gif?alt=media) * 从**最后开始**，相邻的两两对比 * 决定是否交换顺序 * 每次确定最小的一个（即最前面的一个） * 下一次对比不再管已经对了的 * 共需要n-1次冒泡 ```c //冒泡排序. void BubbleSort(int A[],int n){ for(int i=0;ii;j--){ if(A[j-1]>A[j]){ //若为逆序 swap(A[j-1],A[j]); //交换 flag=true; } } if(flag==false) return ; //本趟遍历后没有发生交换，说明表已经有序 } } ``` * 空间复杂度：$$O(1)$$，不使用辅助单元 * 时间复杂度：$$O(n^2)$$ * 最好情况：$$O(n)$$ * 本身有序 * 比较次数：$$n-1$$ * 无需移动 * 最坏情况：$$O(n^2)$$ * 本身逆序 * 比较次数：$$n(n-1)/2$$，每个数与前面的比较一次 * 移动次数：$$3n(n-1)/2$$，每次交换需要3次赋值操作 * 稳定 * 可用于链表 ## 4、快速排序 ![](https://2472502332-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FUddTfPz1UQGspJpAxLN6%2Fuploads%2Fgit-blob-734735e08ff9eff2de54f36b01460c6693d6ba82%2F%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F.gif?alt=media) * 每一趟确定一个点的最终位置 * 左边全部比他小，右边全部比他大 * 将目标点的位置腾空，之后low和high哪一个指向不空的就移动哪一个 * 对左右两部分再次做如上处理 ![快速排序](https://2472502332-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FUddTfPz1UQGspJpAxLN6%2Fuploads%2Fgit-blob-add4313c62e6169102d10c301a1f194575ab43e3%2F%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F.png?alt=media) 快速排序： ```c void QuickSort(int A[], int low, int high){ if(low < high){ //跳出的条件 int pivotpos = Partition(A, low, high); //划分 QuickSort(A, low, pivotpos-1); //左子表 QuickSort(A, pivotpos+1, high); //右子表 } } ``` 划分左右子表： ```c int Partition(int A[], int low, int high){ int pivot = A[low]; while(low < high){ //直到两个指针碰面，退出循环 while(low < high && A[high] >= pivot){ high--; //high左边全部大于pivot } A[low] = A[high]; //将小于pivot的移到右边 while(low0;i--) //从后往前调整所有非终端结点 HeadAdjust(A,i,len); } //将以k为根的子树调整为大根堆（元素K不断下坠） void HeadAdjust(int A[],int k,int len){ A[0]=A[k]; //A[0]暂存子树的根结点 //沿key较大的子结点向下筛选 for(int i=2*k;i<=len;i*=2){ //先指向左孩子2k if(i=A[i]) break; //筛选结束 else{ A[k]=A[i] ; //将A[i]调整到双亲结点上 k=i; //修改k值，以便继续向下筛选 } A[k]=A[0]; //被筛选结点的值放入最终位置 } //堆排序 void HeapSort(int A[] ,int Len){ BuildMaxHeap(A, len); //初始建堆 //n-1趟的交换和建堆过程 for(int i=len;i>1;i--){ swap(A[i],A[1]); //堆顶元素和堆底元素交换 HeadAdjust(A,1,i-1); //把剩余的待排序元素整理成堆 } } ``` * 节点每下坠一层，最多对比2次 * 树高h，节点在第i层，则 * 最多下坠 h-i 层 * 最多对比 2(h-i) 次 * n个元素（节点）的完全二叉树高：$$\lfloor\log\_2n\rfloor+1$$ * 第i层最多有$$2^(i-1)$$个节点（根为0层） * 只有非底层（1\~(h-1)）层节点可能下坠 * **空间复杂度**：$$O(1)$$，没有递归 * **时间复杂度**：$$O(n\log\_2n)$$ * 建堆：$$O(n)$$ * 关键字对比次数**不超过4n** * 排序：$$O(n\log\_2n)$$ * n-1趟 * 每趟时间等于树高 * 不稳定 ## 7、归并排序 将两个有序的序列合成一个 ![](https://2472502332-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FUddTfPz1UQGspJpAxLN6%2Fuploads%2Fgit-blob-f73af53c2db8a1d3cf74d2c3956fad5759b1165b%2F%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F.gif?alt=media) ### K路归并排序 * 将序列分为多个小序列 * 小序列的大小从1开始 * 相邻的K个小序列归并成新序列 * 直到归并为1个 ![image-20221001111552762](https://2472502332-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FUddTfPz1UQGspJpAxLN6%2Fuploads%2Fgit-blob-93bb48ea1954868f9c87b3c163916ca3271ee09a%2F%E4%BA%8C%E8%B7%AF%E5%BD%92%E5%B9%B6.png?alt=media) * **空间复杂度**：$$O(n)$$，同样大小的辅助数组 * **时间复杂度**：$$O(n\log\_2n)$$ * 归并的趟数：$$\log\_2n$$ * 每趟的时间复杂度：$$O(n)$$ ## 8、基数排序 ![](https://2472502332-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FUddTfPz1UQGspJpAxLN6%2Fuploads%2Fgit-blob-7d77afaeb403b6880e56798c82c444199fc35c9f%2F%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F.gif?alt=media) 设关键字有d位，分成r组 * **空间复杂度**：$$O(r)$$，r个辅助队列 * **时间复杂度**：$$O(d(r+n))$$ * 需要d趟排序 * 每趟分配n次，收集r次 ## 9、内部排序 ### 算法性能总结 ![](https://2472502332-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FUddTfPz1UQGspJpAxLN6%2Fuploads%2Fgit-blob-488ac55340def6c157ffce6541421a27165e01a7%2F%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.png?alt=media) ### 算法选择 * **数量较小时**：直接插入排序、简单排序 * **数量较大时**：快速排序、堆排序、归并排序 * **文件本身基本有序**：直接插入排序、冒泡排序 * **数量非常大且关键字可分解**：基数排序 ## 10、外部排序 * 构造初始归并段 * 合并归并段时，两个输入缓冲区分别存放来自两个归并段的元素 ![](https://2472502332-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FUddTfPz1UQGspJpAxLN6%2Fuploads%2Fgit-blob-12287cac8b654993f8aa78f64ab9c8973547bc60%2F%E5%A4%96%E9%83%A8%E6%8E%92%E5%BA%8F1.png?alt=media) ![](https://2472502332-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FUddTfPz1UQGspJpAxLN6%2Fuploads%2Fgit-blob-ca9cf86151cd88d7a814e669a67cd712f99960f8%2F%E5%A4%96%E9%83%A8%E6%8E%92%E5%BA%8F2.png?alt=media) ![](https://2472502332-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FUddTfPz1UQGspJpAxLN6%2Fuploads%2Fgit-blob-2e33b2bf1a74bed1cea4e2a655eb75c919ef5042%2F%E5%A4%96%E9%83%A8%E6%8E%92%E5%BA%8F3.png?alt=media) * 读写磁盘次数：$$文件块数\times (1+归并趟数) \times 2$$ * 时间开销：读写磁盘时间 + 内部排序时间 + 内部归并时间 ## 11、败者树 ![](https://2472502332-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FUddTfPz1UQGspJpAxLN6%2Fuploads%2Fgit-blob-8ca1c56350b6e7b6f99dd5b24b514791875195c6%2F%E8%B4%A5%E8%80%85%E6%A0%91.gif?alt=media) * 是一颗满二叉树 * 叶子节点为比较的元素 * 每一层的非叶节点代表该次对比输的一方所属的归并段 * 对于K路归并，构造完败者树需要比较k-1次 * 构造完成后每次选出最小元素需要对比：$$\log\_2k$$次 ## 12、置换-选择排序 ![](https://2472502332-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FUddTfPz1UQGspJpAxLN6%2Fuploads%2Fgit-blob-4c1ed80dddd3b4e7f8b87a482e452a2cf04f80c2%2F%E7%BD%AE%E6%8D%A2-%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F.gif?alt=media) * 用于构建初始归并段 * 工作区满了则构造下一个归并段 ## 13、最佳归并树 * 就是一颗类**哈夫曼树** * 一定是严格的K叉树 * 磁盘读写次数=2\*带权路径长度 ![](https://2472502332-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FUddTfPz1UQGspJpAxLN6%2Fuploads%2Fgit-blob-a612b4c43f767ac47a0cbedce3da2a2a652a1e34%2F%E6%9C%80%E4%BD%B3%E5%BD%92%E5%B9%B6%E6%A0%91.png?alt=media) * 若初始归并段的数量无法恰好满足，补充长度为0的“虚段” * 设采用K路归并，初始归并段数量为n，若 * $$(n-1)%(k-1)=0$$，则不用补充虚段 * $$(n-1)%(k-1)=u\neq0$$，补充$$(k-1)-u$$个虚段