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

《数据结构与算法排序相关概要.docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构与算法一一排序相关＞区间排序①ShortSort(Oracle)②TopK算法(Knuth)③TopMN算法(P.Linux)数据结构与算法——排序相关冒泡排序•它重复地访问要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。访问数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。•FORI=ITON-lDO•FORJ=1+1TONDO•IF(A[i]>A[j])THENswap(A[i],A[j]);•ENDFOR•ENDFOR数据结构与算法——排序相关冒泡排序・数据结构：数组•最差时间复杂度：O(n2)•

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

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

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

5、ons•最差空间复杂度根据实现的方式不同而不同数据结构与算法——排序相关快速排序数据结构与算法——排序相关归并排序•元素首先分组，每组元素进行比较。然后每组元素看成一个元素，再分组比较。递归此过程直到只有一组元素的时候排序完成。•voidmerge_sort(intarrf],intfirst,intlast){•intmid=0;•if(first

6、);//X—・个分组排用•mergefarra^firstmidjast);//归并两组排序•}•}数据结构与算法——排序相关归并排序•数据结构：数组•最差时间复杂度：O(nlogn)•最优时间复杂度:0(n)•平均时间复杂度：0(nlogn)•最差空间复杂度：0(n)数据结构与算法——排序相关归并排序数据结构与算法——排序相关堆排序•堆积树是一个近似完全二叉树的结构，并同吋满足堆的属性：即子结点的键值或索引总是小于（或者大于）它的父结点。•WHILE（堆不为空）{•A[i++]=GetRootFromHeap;//取出堆根•ShiftHeap;/

7、/调堆•}数据结构与算法——排序相关树排序•首先按照搜索二叉树对数据建树，然后中序遍历搜索树，即可得到有序数列。•普通二叉搜索树，AVL平衡二叉树等。数据结构与算法——排序相关树排序•数据结构：数组•最差时间复杂度：平衡树O(nlogn)•非平衡树O(nA2)•最优时间复杂度：O(nlogn)•平均时间复杂度：G(nlogn)•最差空间复杂度：O(n)total,0(1)auxiliary数据结构与算法——排序相关桶排序•不基于比较，为每个元素设一个计数器，记录每个元素出现多少次。•FORI=1TONDO•C[A[i]]++;//将兀素丢入相]中•E

8、NDFOR•FORI=1TOMAXDO•输出C[i]个I;//讲元素依次倒岀桶•ENDFOR数据结构与算法—