数据结构与算法排序相关概要

1、 数据结构与算法一一排序相关 区间排序 ShortSort (Oracle) TopK算法(Knuth) TopMN算法(P.Linux) 数据结构与算法排序相关 冒泡排序 它重复地访问要排序的数列，一次比较两 个元素，如果他们的顺序错误就把他们交 换过来。访问数列的工作是重复地进行直 到没有再需要交换，也就是说该数列已经 排序完成。 FOR I = ITO N-l DO FOR J = 1+1 TO N DO IF (AiAj) THEN swap(Ai,Aj); END FOR END FOR 数据结构与算法排序相关 冒泡排序 数据结构：数组 最差时间复杂度：O(n2) 最优时间复杂度：O

2、何一一因为可以通过判 断一轮比较后是否有交换来判定排序是否 完成 平均时间复杂度：O(n2) 最差空间复杂度：O(n)total, 0(1) auxiliary 数据结构与算法排序相关 冒泡排序 数据结构与算法排序相关 选择排序 首先在未排序序列中找到最小元素，存放 到排序序列的起始位置，然后，再从剩余 未排序元素中继续寻找最小元素，然后放 到排序序列末尾。以此类推，直到所有元 素均排序完毕。 FOR I = 1 TO N DO Ai = FindMin(bN); END FOR 数据结构与算法排序相关 选择排序 数据结构：数组 最差时间复杂度：O(n2) 最优时间复杂度：O(n2) 平均时间

3、复杂度：O(n2) 最差空间复杂度:OG丿total, Oauxiliary 数据结构与算法排序相关 选择排序 数据结构与算法排序相关 插入排序 它的工作原理是通过构建有序序列，对于 未排序数据，在已排序序列中从后向前扫 描，找到相应位置并插入。 FOR I = 2 TO N DO J = FindPos(lJ-l,x); 在有序的序列中找X的位置 MoveNext(JJ); /将需要占用位置的元素后移 AJ = x; /空出的位置放入X END FOR 数据结构与算法排序相关 插入排序 数据结构：数组 最差时间复杂度：O(n2) 最优时间复杂度：O(n2) 平均时间复杂度：O(n2) 最差空

4、间复杂度：OG丿total, Oauxiliary 数据结构与算法排序相关 快速排序 从数列中挑出一个元素，称为”基准”，重 新排序数列，所有元素比基准值小的摆放 在基准前面，所有元素比基准值大的摆在 基准的后面(相同的数可以到任一边)。 这个称为分割操作。递归地(recursive)把 小于基准值元素的子数列和大于基准值元 素的子数列排序。 数据结构与算法排序相关 快速排序 数据结构：Varies 最差时间复杂度：0(n2) 最优时间复杂度：O(nlogn) 平均时间复杂度：0(nlogn)comparisons 最差空间复杂度根据实现的方式不同而不 同 数据结构与算法排序相关 快速排序 数

5、据结构与算法排序相关 归并排序 元素首先分组，每组元素进行比较。然后 每组元素看成一个元素，再分组比较。递 归此过程直到只有一组元素的时候排序完 成。 void merge_sort(int arrf, int first, int last) intmid = 0; if(firstlast) mid = (first+last)/2; /分成两组分别排序 merge_sort(airay,first, mid);/对一个分组排序 merge_sort(array/ mid+ljast);/X个分组排用 mergefarrafirstmidjast);/ 归并两组排序 数据结构与算法排序相关

6、 归并排序 数据结构：数组 最差时间复杂度：O(nlogn) 最优时间复杂度:0(n) 平均时间复杂度：0(nlogn) 最差空间复杂度：0(n) 数据结构与算法排序相关 归并排序 数据结构与算法排序相关 堆排序 堆积树是一个近似完全二叉树的结构，并 同吋满足堆的属性：即子结点的键值或索 引总是小于（或者大于）它的父结点。 WHILE （堆不为空） Ai+ = GetRootFromHeap; / 取出堆根 ShiftHeap;/ 调堆 数据结构与算法排序相关 树排序 首先按照搜索二叉树对数据建树，然后中 序遍历搜索树，即可得到有序数列。 普通二叉搜索树，AVL平衡二叉树等。 数据结构与算法排

7、序相关 树排序 数据结构：数组 最差时间复杂度：平衡树O(nlogn) 非平衡树O(nA2) 最优时间复杂度：O(nlogn) 平均时间复杂度：G(nlogn) 最差空间复杂度：O(n) total, 0(1) auxiliary 数据结构与算法排序相关 桶排序 不基于比较，为每个元素设一个计数器， 记录每个元素出现多少次。 FOR I = 1 TO N DO CAi+; /将兀素丢入相中 END FOR FOR I = 1 TO MAX DO 输出Ci个I; /讲元素依次倒岀桶 END FOR 数据结构与算法排序相关 桶排序 数据结构：数组 最差时间复杂度：0(n) 最优时间复杂度：0(n)

8、 平均时间复杂度：0(n) 最差空间复杂度：O(MAX)total 数据结构与算法排序相关 基数排序 将所有待比较数值(正整数)统一为同样的数位长度 ，数位较短的数前面补零.然后,从最低位开始，依 次进行一次排序这样从最低位排序一直到最高位 排序完成以后，数列就变成一个有序序列. 基数排序的方式町以采用LSD (Least significant digital)或MSD (Most significant digital) , LSD的 排序方式由键值的最右边开始，而MSD则相反， 由键值的最左边开始。 数据结构与算法排序相关 希尔排序 对有n个元素的可比较资料，先取一个小于n的整 数dl作

9、为第一个增量，把文件的全部记录分成dl 个组。所有距离为dl的倍数的记录放在同一个组 中。先在各组内进行直接插入排序；然后，取第 二个增量d2vdl重复上述的分纽和排序，直至所取 的增量dt=l(dtdt-l.d2 H0) H0 = Ai; /替换堆根 ShiftHeap(); 调堆 END FOR 数据结构与算法排序相关 ShortSort 数据结构：数组 最差时间复杂度：O(n+nlogk) 最优时间复杂度：O(n+klogk) 平均时间复杂度：G(n+xlogn) k x K) 如果左堆元素多于K个则继续二分 LeftGroupl-now = Split(LeftGroupnow); S

10、ort(LeftGroupl-now ); /在左堆中排序 数据结构与算法排序相关 TopK 数据结构：数组 最差时间复杂度：O(n+k)log(n/k)+k/ogk) 最优时间复杂度：O(n+k)log(n/k)+k/ogk) 平均时间复杂度：O(n+k)log(n/k)+k/ogk) 最差空间复杂度根据实现的方式不同而不 同 优势：利用随机的基准，可以有效避免全排序 数据结构与算法一一排序相关 TopMN 排序M.N位的元素，则需要抛弃l.M-l,N+l.MAX 两部分的元素。利用二分思想，每次对元素分成 左大右小两堆，分别处理。左堆继续二分分出前 M1个元素，右堆继续二分分出N+1个之后的元素 o排除无效元素后的元素集，再进行排序。 H = Split(A); /元素分成两堆 利用TopK的思想将前个元素排到一组。 利用TopK的思想将N+1位后的元素排到一组。 Sort(A,M,N). 备注：可以不用严格