數(shù)據(jù)結(jié)構(gòu)各種排序算法總結(jié)

1、 數(shù)據(jù)結(jié)構(gòu)各種排序算法總結(jié)計算機排序與人進行排序的不同：計算機程序不能象人一樣通覽所有的數(shù)據(jù)，只能根據(jù)計算機的"比較"原理，在同一時間內(nèi)對兩個隊員進行比較，這是算法的一種"短視"。1. 冒泡排序 BubbleSort最簡單的一個public void bubbleSort() int out, in; for(out=nElems-1; out>0; out-) / outer loop (backward) for(in=0; in<out; in+) / inner loop (forward) if( ain > ain+1 )

2、/ out of order? swap(in, in+1); / swap them / end bubbleSort()效率：O(N2)2. 選擇排序 selectSortpublic void selectionSort() int out, in, min; for(out=0; out<nElems-1; out+) / outer loop min = out; / minimum for(in=out+1; in<nElems; in+) / inner loop if(ain < amin ) / if min greater, min = in; / we

3、have a new min swap(out, min); / swap them / end for(out) / end selectionSort()效率：O(N2)3. 插入排序 insertSort在插入排序中，一組數(shù)據(jù)在某個時刻實局部有序的，為在冒泡和選擇排序中實完全有序的。public void insertionSort() int in, out; for(out=1; out<nElems; out+) / out is dividing line long temp = aout; / remove marked item in = out; / start sh

4、ifts at out while(in>0 && 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)如果數(shù)據(jù)基本有序，幾乎需要O(N)的時間4. 歸并排序 mergeSort利用遞歸，不斷的分割數(shù)組，然后歸并有序數(shù)組效率為O(N*l

5、ogN),缺點是需要在存儲器中有一個大小等于被排序的數(shù)據(jù)項數(shù)目的數(shù)組。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;

6、/ 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

7、 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 ) workSpac

8、ej+ = theArraylowPtr+; else workSpacej+ = theArrayhighPtr+; while(lowPtr <= mid) workSpacej+ = theArraylowPtr+; while(highPtr <= upperBound) workSpacej+ = theArrayhighPtr+; for(j=0; j<n; j+) theArraylowerBound+j = workSpacej; / end merge()5. 希爾排序 ShellSortpublic void shellSort() int inner,

9、outer; long temp; int h = 1; / find initial value of h while(h <= nElems/3) h = h*3 + 1; / (1, 4, 13, 40, 121, .) while(h>0) / decreasing h, until h=1 / h-sort the file for(outer=h; outer<nElems; outer+) temp = theArrayouter; inner = outer; / one subpass (eg 0, 4, 8) while(inner > h-1 &a

10、mp;& theArrayinner-h >= temp) theArrayinner = theArrayinner-h; inner -= h; theArrayinner = temp; / end for h = (h-1) / 3; / decrease h / end while(h>0) / end shellSort()希爾排序是基于插入排序的，由于插入排序復(fù)制的次數(shù)太多，導(dǎo)致效率的下降，而ShellSort先利用n-增量排序?qū)?shù)據(jù)變?yōu)榛居行?，然后在利用插入排序?-增量排序）。 n在排序中的一系列取值方法：Lnuth序列，間隔h=3h + 1效率：O(N

11、3/2) 到O(N7/6)6. 快速排序其根本機制在于劃分：劃分數(shù)據(jù)就是把數(shù)據(jù)分為兩組，使所有關(guān)鍵字大于特定值的數(shù)據(jù)項在一組，使所有關(guān)鍵字小于特定值的數(shù)據(jù)項在另一組。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 theArr

12、ay+leftPtr < pivot) ; / (nop) while(rightPtr > 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; /

13、 return partition / end partitionIt()快速排序算法本質(zhì)上通過把一個數(shù)組劃分為兩個子數(shù)組，然后遞歸的調(diào)用自身為每一個子數(shù)組進行快速排序。樞紐（Pivot）的選擇：選擇數(shù)組最右端的數(shù)據(jù)項作為樞紐：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 /

14、 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 =

15、 right; / right-1 (after -) while(true) / find bigger item while( theArray+leftPtr < pivot ) ; / (nop) / find smaller item while(rightPtr > 0 && theArray-rightPtr > pivot) ; / (nop) if(leftPtr >= rightPtr) / if pointers cross, break; / partition done else / not crossed, so swap(l

16、eftPtr, rightPtr); / swap elements / end while(true) swap(leftPtr, right); / restore pivot return leftPtr; / return pivot location / end partitionIt()當(dāng)數(shù)據(jù)是有序的或者是逆序時，從數(shù)組的一端或者另外一端選擇數(shù)據(jù)項作為樞紐都不是好辦法，比如逆序時，樞紐是最小的數(shù)據(jù)項，每一次劃分都產(chǎn)生一個有N-1個數(shù)據(jù)項的子數(shù)組以及另外一個只包含樞紐的子數(shù)組三數(shù)據(jù)項取中劃分：選擇第一個、最后一個以及中間位置數(shù)據(jù)項的中值作為樞紐public void recQuick

17、Sort(int left, int right) 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, partition-1); recQuickSort(partition+1, right); / e

18、nd recQuickSort()/- public long 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, right-1); / put