幾種常見排序

1、幾種常見的排序排序方法平均時間復(fù)雜度最壞時間復(fù)雜度輔助存儲空間冒泡排序O(nA2)O(nA2)O(1)直接插入排序O(nA2)O(nA2)O(1)簡單選擇排序O(nA2)O(nA2)O(1)希爾排序O(nlog2n)至0m人2)O(nA2)O(1)快速排序O(nlogn)O(nA2)O(logn)堆排序O(nlogn)O(nlogn)O(1)歸并排序O(nlogn)O(nlogn)O(n)基數(shù)排序O(d(n+rd)O(d(n+rd)O(rd)1冒泡排序冒泡排序算是手寫排序的入門了，思想比較簡單。它是通過對相鄰數(shù)據(jù)元素進行交換,逐步講待排序序列變成有序序列的過程。算法思想：反復(fù)掃描待排序序列，在

2、掃描的過程中順次比較相鄰兩個元素的大小，若逆序則交換位置，因排序過程元素在冒泡，所以叫冒泡排序（誤2333）對于序列48,62,35,77,55,14,一趟冒泡排序如下所示：為比較數(shù)兩邊大小,若不符合要求則交換,這里按從小到大排序時第一趟冒泡的486235775514486235775514483562775514483562775514483562557714483562551477結(jié)果第一趟結(jié)果：483562551477第二趟結(jié)果：354855146277第三趟結(jié)果：354814556277第四趟結(jié)果：351448556277第五趟結(jié)果：143548556277以上為序列48,62,35,

3、77,55,14,冒泡排序全過程代碼:voidbublleSort(intdata,intn)/冒泡排序(for(inti=0;in;i+)for(intj=0;jdataj+1)std:swap(dataj+1,dataj);算法分析：每一趟冒泡都能確定一個值，所以內(nèi)層循環(huán)從每次長度-1;代碼簡單容易記得，但時間復(fù)雜度過高，對于大量數(shù)據(jù)的排序時間太長。時間復(fù)雜度接近O(n2);2 .直接插入排序思想：無序數(shù)列中有n個數(shù),把第i個數(shù)(i=n)插入到前i-1個已排好序的數(shù)列中如無序數(shù)列48,62,35,77,55,14】【48,62,35,775514】486235775514】35486277

4、5514】354862775514】【35,48,55,62,72,14【14,35,48,55,62,77】中為已排序數(shù)列代碼：voidinsertsort(intdata,intn)/直接插入排序for(inti=1,j;i=0;j-)if(datajx)dataj+1=dataj;elsebreak;if(j!=i)dataj+1=x;算法分析：時間復(fù)雜度接近O(nA2),優(yōu)化方法：將尋找前i-1個數(shù)中可以插入的位置的時間復(fù)雜度降低，把線性查找O(n)查找優(yōu)化成二分查找O(logn)3 .簡單選擇排序思想：每一次從待排序的數(shù)列中選出最?。ɑ蜃畲螅┑囊粋€元素，存放在序列的起始位置,直到全部

5、待排序的數(shù)據(jù)元素排完。48,62,35,77,55,14,9814,62,35,77,55,48,9814,35,62,77,55,48,9814,35,48,14,35,48,14354814354877,55,62,55,77,62,55627755627798989898中為未排序序列代碼：voidselectsort(intdata,intn)/簡單選擇排序for(inti=0;in;i+)intindex=i;for(intj=i+1;jdataindex)index=j;if(index!=i)std:swap(dataindex,datai);4 .希爾排序思想：先將整個待排元素

6、序列分割成若干個子序列(由相隔某個增量的元素組成的)分別進行直接插入排序，然后依次縮減增量再進行排序，待整個序列中的元素基本有序(增量足夠小)時，再對全體元素進行一次直接插入排序。因為直接插入排序在元素基本有序的情況下(接近最好情況)，效率是很高的，因此希爾排序在時間效率上比前兩種方法有較大提高。以無序數(shù)列503,087,512,061,908,170,897,275,653,426為例將“增量”gap設(shè)為10/2=5進行分組503,087,512,061,908,170,897,275,653,4261A1B2A2B3A3B4A4B5A5B注：數(shù)字相同為同一組，A為第一個數(shù)，B為第二個數(shù)此時

7、無序數(shù)列被分為五組(503,170)(087,897)(512,275)(061,653)(908,426)現(xiàn)在，進行組內(nèi)直接插入排序(170,503)(087,897)(275,512)(061,653)(426,908)此時的無序數(shù)列更改為170,087,275,061,426,503,897,512,653,908以上為希爾排序第一趟排序?qū)ⅰ霸隽俊眊ap設(shè)為5/2=2進行分組170,087,275,061,426,503,897,512,653,9081A1B1C1D1E2A2B2C2D2E此時無序數(shù)列被分為兩組(170.275,426,897,653)(087,061,503,512,

8、908)在組內(nèi)進行直接插入排序(170.275,426,653,897)(061,087,503,512,908)此時的無序數(shù)列更改為170,061,275,087,426,503,653,512,897,908以上為希爾排序第二趟排序?qū)ⅰ霸隽俊眊ap設(shè)為2/2=1進行分組170,061,275,087,426,503,653,512,897,9081A1B1C1D1E1F1G1H1I1J在組內(nèi)進行直接插入排序為061,087,170,275,426,503,512,653,897,908以上為希爾排序第三趟排序?qū)ⅰ霸隽俊眊ap設(shè)為1/2=0進行分組061,087,170,275,426,503,512,653,897,908此時已為有序數(shù)列，排序完成voidshellsort(intdata,intn)/希爾排序(for(intgap=n/2;gap0;gap/=2)for(inti=0;igap;i+)for(intj=i+gap;jn;j+=gap)if(dataj=0&dataktemp)datak+gap=datak;k-=gap;datak+gap=temp;以上為