数据结构各种排序算法总结.doc

数据结构各种排序算法总结计算机排序与人进行排序的不同：计算机程序不能象人一样通览所有的数据，只能根据计算机的比较原理，在同一时间内对两个队员进行比较，这是算法的一种短视。1. 冒泡排序 BubbleSort最简单的一个public void bubbleSort() int out, in; for(out=nElems-1; 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(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 void insertionSort() int in, out; for(out=1; out0 & ain-1 = 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利用递归，不断的分割数组，然后归并有序数组效率为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, 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() /- 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+ = theArraylowPtr+; else workSpacej+ = theArrayhighPtr+; while(lowPtr = mid) workSpacej+ = theArraylowPtr+; while(highPtr = upperBound) workSpacej+ = theArrayhighPtr+; for(j=0; jn; j+) theArraylowerBound+j = workSpacej; / end merge()5. 希尔排序 ShellSortpublic void shellSort() int inner, outer; long temp; int h = 1; / find initial value of h while(h 0) / decreasing h, until h=1 / h-sort the file for(outer=h; outer h-1 & theArrayinner-h = temp) theArrayinner = theArrayinner-h; inner -= h; theArrayinner = temp; / end for h = (h-1) / 3; / decrease 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) 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 crossed, 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 sorted 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 left, int right, long pivot) int leftPtr = left-1; / left (after +) int rightPtr = right; / right-1 (after -) while(true) / find bigger item while( theArray+leftPtr 0 & theArray-rightPtr pivot) ; / (nop) if(leftPtr = rightPtr) / if pointers cross, break; / partition done else / not crossed, so swap(leftPtr, rightPtr); / swap 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) int size = right-left+1; if(size theArraycenter ) swap(left, center); / order left & right if( theArrayleft theArrayright ) swap(left, right); / order center & right if( theArraycenter theArrayright ) swap(center, right); swap(center, right-1); / 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 smaller ; / (nop)