(2021年整理)数据结构各种排序算法总结

1、数据结构各种排序算法总结数据结构各种排序算法总结 编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（数据结构各种排序算法总结）的内容能够给您的工作和学习带来便利。同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快 业绩进步，以下为数据结构各种排序算法总结的全部内容。 数据结构各种排序算法总结计算机排序与人进行排序的不同：计算机程序不能象人一样通览所有的数据,只能根据计算机的比较原理

2、,在同一时间内对两个队员进行比较,这是算法的一种短视。1。 冒泡排序 bubblesort最简单的一个public void bubblesort（) int out， in; for（out=nelems1； out0; out） / outer loop (backward） for（in=0; in ain+1 ） / out of order？ swap(in， in+1); / swap them / end bubblesort()效率：o(n2）2。 选择排序 selectsortpublic void selectionsort（） int out， in， min； for(

3、out=0; outnelems-1； out+) / outer loop min = out； / minimum for（in=out+1; innelems； in+) / inner loop if(ain amin ） / if min greater, min = in； / we have a new min swap（out, min）; / swap them / end for(out） / end selectionsort(）效率：o（n2)3。 插入排序 insertsort在插入排序中，一组数据在某个时刻实局部有序的，为在冒泡和选择排序中实完全有序的。public

4、 void insertionsort(） int in， out; for（out=1; out0 & ain1 = temp） / until one is smaller, ain = ain-1; / shift item to right in； / go left one position ain = temp； / insert marked item / end for / end insertionsort(）效率：比冒泡排序快一倍，比选择排序略快，但也是o（n2)如果数据基本有序,几乎需要o(n）的时间4. 归并排序 mergesort利用递归,不断的分割数组，然后归并有序

5、数组效率为o(n*logn）,缺点是需要在存储器中有一个大小等于被排序的数据项数目的数组。public void mergesort（） / called by main() / provides workspace long workspace = new longnelems； recmergesort（workspace, 0, nelems-1）； /- private void recmergesort（long workspace, int lowerbound， int upperbound) if(lowerbound = upperbound） / if range is 1

6、， return; / no use sorting else / find midpoint int mid = (lowerbound+upperbound) / 2; / sort low half recmergesort（workspace， lowerbound， mid); / sort high half recmergesort(workspace, mid+1, upperbound）； / merge them merge（workspace， lowerbound, mid+1， upperbound); / end else / end recmergesort（）

7、/- private void merge(long workspace, int lowptr, int highptr， int upperbound) int j = 0； / workspace index int lowerbound = lowptr; int mid = highptr-1； int n = upperbound-lowerbound+1; / of items while(lowptr = mid & highptr = upperbound） if( thearraylowptr thearrayhighptr ) workspacej+ = thearray

8、lowptr+; else workspacej+ = thearrayhighptr+； while（lowptr = mid) workspacej+ = thearraylowptr+； while（highptr 0） / decreasing h， until h=1 / hsort the file for（outer=h; outer h-1 & thearrayinnerh = temp） thearrayinner = thearrayinner-h; inner = h; thearrayinner = temp; / end for h = （h-1) / 3; / de

9、crease h / end while（h0) / end shellsort（)希尔排序是基于插入排序的，由于插入排序复制的次数太多,导致效率的下降，而shellsort先利用n-增量排序将数据变为基本有序，然后在利用插入排序（1-增量排序）。 n在排序中的一系列取值方法：lnuth序列，间隔h=3h + 1效率：o(n3/2） 到o（n7/6）6。 快速排序其根本机制在于划分：划分数据就是把数据分为两组，使所有关键字大于特定值的数据项在一组，使所有关键字小于特定值的数据项在另一组。public int partitionit(int left， int right, long pivot

10、) int leftptr = left 1; / right of first elem int rightptr = right + 1； / left of pivot while（true） while（leftptr right & / find bigger item thearray+leftptr left & / find smaller item thearray-rightptr pivot） ； / （nop） if(leftptr = rightptr） / if pointers cross， break; / partition done else / not c

11、rossed, so swap(leftptr， rightptr); / swap elements / end while(true） return leftptr； / return partition / end partitionit()快速排序算法本质上通过把一个数组划分为两个子数组，然后递归的调用自身为每一个子数组进行快速排序。枢纽（pivot）的选择：选择数组最右端的数据项作为枢纽：public void recquicksort（int left， int right） if(right-left = 0) / if size = 1, return; / already s

12、orted else / size is 2 or larger long pivot = thearrayright; / rightmost item / partition range int partition = partitionit（left, right, pivot); recquicksort(left, partition-1); / sort left side recquicksort（partition+1, right)； / sort right side / end recquicksort（)/- public int partitionit（int lef

13、t, int right， long pivot） int leftptr = left1; / left (after +) int rightptr = right； / right-1 (after -） while(true) / find bigger item while（ thearray+leftptr pivot) ; / (nop) if(leftptr = rightptr） / if pointers cross， break; / partition done else / not crossed, so swap(leftptr， rightptr）； / swap

14、 elements / end while（true) swap（leftptr， right)； / restore pivot return leftptr； / return pivot location / end partitionit(）当数据是有序的或者是逆序时，从数组的一端或者另外一端选择数据项作为枢纽都不是好办法，比如逆序时,枢纽是最小的数据项,每一次划分都产生一个有n-1个数据项的子数组以及另外一个只包含枢纽的子数组三数据项取中划分：选择第一个、最后一个以及中间位置数据项的中值作为枢纽public void recquicksort（int left， int right)

15、 int size = right-left+1； if（size = 3） / manual sort if small manualsort（left, right); else / quicksort if large long median = medianof3（left， right）； int partition = partitionit（left， right， median); recquicksort（left, partition1); recquicksort(partition+1， right)； / end recquicksort（）/- public lon

16、g medianof3（int left， int right） int center = (left+right）/2； / order left center if( thearrayleft thearraycenter ) swap(left, center); / order left & right if( thearrayleft thearrayright ) swap（left， right); / order center & right if（ thearraycenter thearrayright ） swap（center， right）； swap（center，

17、 right1）； / put pivot on right return thearrayright-1； / return median value / end medianof3(）public int partitionit(int left, int right， long pivot） int leftptr = left; / right of first elem int rightptr = right 1; / left of pivot while(true) while（ thearray+leftptr pivot ） / find bigger ; / （nop） while( thearrayrightptr pivot ) / fi