第常見(jiàn)的排序算法,一篇就夠了排序算法介紹

排序也稱排序算法(SortAlgorithm)，排序是將一組數(shù)據(jù)，依指定的順序進(jìn)行排列的過(guò)程。

排序的分類：

1)內(nèi)部排序:

指將需要處理的所有數(shù)據(jù)都加載到內(nèi)部存儲(chǔ)器中進(jìn)行排序。

2)外部排序法：

數(shù)據(jù)量過(guò)大，無(wú)法全部加載到內(nèi)存中，需要借助外部存儲(chǔ)進(jìn)行排序。

常見(jiàn)的排序的排序算法分類如圖：

冒泡排序（BubbleSorting）的基本思想是：通過(guò)對(duì)待排序序列從前向后（從下標(biāo)較小的元素開(kāi)始）,依次比較相鄰元素的值，若發(fā)現(xiàn)逆序則交換，使值較大的元素逐漸從前移向后部，就象水底下的氣泡一樣逐漸向上冒。

原始數(shù)組：3,9,-1,10,20

第一趟排序

(1)3,9,-1,10,20//如果相鄰的元素逆序就交換

(2)3,-1,9,10,20

(3)3,-1,9,10,20

(4)3,-1,9,10,20

第二趟排序

(1)-1,3,9,10,20//交換

(2)-1,3,9,10,20

(3)-1,3,9,10,20

第三趟排序

(1)-1,3,9,10,20

(2)-1,3,9,10,20

第四趟排序

(1)-1,3,9,10,20

小結(jié)冒泡排序規(guī)則

(1)一共進(jìn)行數(shù)組的大小-1次大的循環(huán)

(2)每一趟排序的次數(shù)在逐漸的減少

(3)如果我們發(fā)現(xiàn)在某趟排序中，沒(méi)有發(fā)生一次交換，可以提前結(jié)束冒泡排序。這個(gè)就是優(yōu)化

因?yàn)榕判虻倪^(guò)程中，各元素不斷接近自己的位置，如果一趟比較下來(lái)沒(méi)有進(jìn)行過(guò)交換，就說(shuō)明序列有序，因此要在排序過(guò)程中設(shè)置一個(gè)標(biāo)志flag判斷元素是否進(jìn)行過(guò)交換。從而減少不必要的比較。(這

里說(shuō)的優(yōu)化，可以在冒泡排序?qū)懞煤?，在進(jìn)行)

publicstaticvoidbubbleSort(int[]arr){

inttemp=0;

//標(biāo)識(shí)變量，表示是否進(jìn)行過(guò)交換

booleanflag=false;

//時(shí)間復(fù)雜度O(n^2)

for(inti=0;iarr.length-1;i++){//一共要排序幾次

for(intj=0;jarr.length-1-i;j++){//每次排序需要比較的次數(shù)

if(arr[j]arr[j+1]){

flag=true;

temp=arr[j+1];

arr[j+1]=arr[j];

arr[j]=temp;

if(flag){//出現(xiàn)過(guò)交換，重置flag

flag=false;

}else//在上一趟排序中，一次交換也沒(méi)有發(fā)生過(guò)

break;

}

選擇式排序也屬于內(nèi)部排序法，是從欲排序的數(shù)據(jù)中，按指定的規(guī)則選出某一元素，再依規(guī)定交換位置后達(dá)到排序的目的。

選擇排序思想

選擇排序（selectsorting）也是一種簡(jiǎn)單的排序方法。它的基本思想是：第一次從arr[0]~arr[n-1]中選取最小值，與arr[0]交換，第二次從arr[1]~arr[n-1]中選取最小值，與arr[1]交換，第三次arr[2]~arr[n-1]中選取最小值，與arr[2]交換，…，第i次從arr[i-1]~arr[n-1]中選取最小值，與arr[i-1]交換，…,第n-1次從arr[n-2]~arr[n-1]中選取最小值，與arr[n-2]交換，總共通過(guò)n-1次，得到一個(gè)按排序碼從小到大排列的有序序列

原始的數(shù)組：101,34,119,1

第一輪排序:1,34,119,101

第二輪排序:1,34,119,101

第三輪排序:1,34,101,119

小結(jié)選擇排序的規(guī)則

1.選擇排序一共有數(shù)組大小-1輪排序

2.每1輪排序，又是一個(gè)循環(huán),循環(huán)的規(guī)則(代碼)

先假定當(dāng)前這個(gè)數(shù)是最小數(shù)

然后和后面的每個(gè)數(shù)進(jìn)行比較，如果發(fā)現(xiàn)有比當(dāng)前數(shù)更小的數(shù)，就重新確定最小數(shù)，并得到下標(biāo)

當(dāng)遍歷到數(shù)組的最后時(shí)，就得到本輪最小數(shù)和下標(biāo)2.4交換[代碼中再繼續(xù)說(shuō)]

代碼實(shí)現(xiàn)

publicstaticvoidselectSort(int[]arr){

for(inti=0;iarr.length-1;i++){

intminIndex=i;

intmin=arr[i];

for(intj=i+1;jarr.length;j++){

if(minarr[j]){

minIndex=j;

min=arr[j];

//將最小值放在arr[i],即交換

if(minIndex!=i){//如果最小值的下標(biāo)改變了則交換

arr[minIndex]=arr[i];

arr[i]=min;

}

插入排序

插入式排序?qū)儆趦?nèi)部排序法，是對(duì)于欲排序的元素以插入的方式找尋該元素的適當(dāng)位置，以達(dá)到排序的目的。

插入排序思想

插入排序（InsertionSorting）的基本思想是：把n個(gè)待排序的元素看成為一個(gè)有序表和一個(gè)無(wú)序表，開(kāi)始時(shí)有序表中只包含一個(gè)元素，無(wú)序表中包含有n-1個(gè)元素，排序過(guò)程中每次從無(wú)序表中取出第一個(gè)元素，把它的排序碼依次與有序表元素的排序碼進(jìn)行比較，將它插入到有序表中的適當(dāng)位置，使之成為新的有序表。

原始的數(shù)組：(101),34,119,1

橘色箭頭表示待插入的元素下標(biāo)

綠色箭頭表示待插入元素

第一次插入排序

第二次插入排序

第三次插入排序

代碼實(shí)現(xiàn)

publicstaticvoidinsertSort(int[]arr){

intinsertIndex=0;

intinsertValue=0;

for(inti=1;iarr.length;i++){

insertIndex=i-1;

insertValue=arr[i];

while(insertIndex=0arr[insertIndex]insertValue){

arr[insertIndex+1]=arr[insertIndex];

insertIndex--;

//優(yōu)化是否需要賦值

if(insertIndex+1!=i){

arr[insertIndex+1]=insertValue;

}

分析簡(jiǎn)單插入排序存在的問(wèn)題

我們看簡(jiǎn)單的插入排序可能存在的問(wèn)題.

數(shù)組arr={2,3,4,5,6,1}這時(shí)需要插入的數(shù)1(最小),這樣的過(guò)程是：

{2,3,4,5,6,6}

{2,3,4,5,5,6}

{2,3,4,4,5,6}

{2,3,3,4,5,6}

{2,2,3,4,5,6}

{1,2,3,4,5,6}

結(jié)論:當(dāng)需要插入的數(shù)是較小的數(shù)時(shí)，后移的次數(shù)明顯增多，對(duì)效率有影響.

希爾排序是希爾（DonaldShell）于1959年提出的一種排序算法。希爾排序也是一種插入排序，它是簡(jiǎn)單插入排序經(jīng)過(guò)改進(jìn)之后的一個(gè)更高效的版本，也稱為縮小增量排序。

希爾排序基本思想

希爾排序是把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來(lái)越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰被分成一組，算法便終止

為了方便大家理解

希爾排序時(shí)，對(duì)有序序列在插入時(shí)先采用交換法(冒泡法)

publicstaticvoidshellSort(int[]arr){

inttemp=0;

intcount=0;

for(intgap=arr.length/2;gapgap/=2){

for(inti=gap;iarr.length;i++){

for(intj=i-gap;jj-=gap){

if(arr[j]arr[j+gap]){//這里采用交換法

temp=arr[j];

arr[j]=arr[j+gap];

arr[j+gap]=temp;

}

希爾排序時(shí)，對(duì)有序序列在插入時(shí)采用移位法（真正的希爾排序）(插入法)

publicstaticvoidshellSort(int[]arr){

intcount=0;

for(intgap=arr.length/2;gapgap/=2){

for(inti=gap;iarr.length;i++){

intinsertIndex=i-gap;

intinsertValue=arr[insertIndex+gap];

while(insertIndex=0insertValuearr[insertIndex]){

arr[insertIndex+gap]=arr[insertIndex];

insertIndex-=gap;

if(insertIndex!=(i-gap)){

arr[insertIndex+gap]=insertValue;

}

快速排序（Quicksort）是對(duì)冒泡排序的一種改進(jìn)?；舅枷胧牵和ㄟ^(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列

代碼實(shí)現(xiàn)

publicstaticvoidquickSort(int[]arr,intleft,intright){

intr=right;

intl=left;

inttemp=0;

intpivot=arr[(right+left)/2];

while(lr){

while(arr[l]pivot){

l++;

while(arr[r]pivot){

r--;

if(l==r)

break;

temp=arr[r];

arr[r]=arr[l];

arr[l]=temp;

if(arr[l]==pivot){

r--;

if(arr[r]==pivot){

l++;

if(l==r){

l+=1;

r-=1;

//向左遞歸

if(leftr){

quickSort(arr,left,r);

//向右遞歸

if(rightl){

quickSort(arr,l,right);

歸并排序（MERGE-SORT）是利用歸并的思想實(shí)現(xiàn)的排序方法，該算法采用經(jīng)典的分治（divide-and-conquer）策略（分治法將問(wèn)題分(divide)成一些小的問(wèn)題然后遞歸求解，而治(conquer)的階段則將分的階段得到的各答案"修補(bǔ)"在一起，即分而治之)。

說(shuō)明:可以看到這種結(jié)構(gòu)很像一棵完全二叉樹(shù)，本文的歸并排序我們采用遞歸去實(shí)現(xiàn)（也可采用迭代的方式去實(shí)現(xiàn)）。分階段可以理解為就是遞歸拆分子序列的過(guò)程。

再來(lái)看看治階段，我們需要將兩個(gè)已經(jīng)有序的子序列合并成一個(gè)有序序列，比如上圖中的最后一次合并，要將[4,5,7,8]和[1,2,3,6]兩個(gè)已經(jīng)有序的子序列，合并為最終序列[1,2,3,4,5,6,7,8]，來(lái)看下實(shí)現(xiàn)步驟

代碼實(shí)現(xiàn)

治

*@paramarr排序的原始數(shù)組

*@paramleft左邊有序序列的初始索引

*@parammid中間索引

*@paramright右邊索引

*@paramtemp中轉(zhuǎn)數(shù)組

publicstaticvoidmerge(int[]arr,intleft,intmid,intright,int[]temp){

//System.out.println("*****");

inti=left;

intj=mid+1;

intt=0;

先把兩邊有序的數(shù)據(jù)按照規(guī)則填充到temp數(shù)組

指導(dǎo)左右兩邊的有序序列，有一邊處理完畢

while(i=midj=right){

temp[t++]=arr[i]arr[j]arr[j++]:arr[i++];

把所有剩余數(shù)據(jù)的一邊一次全部填充到temp

while(i=mid){

temp[t++]=arr[i++];

while(j=right){

temp[t++]=arr[j++];

將temp數(shù)組的元素拷貝到arr

t=0;

inttempLeft=left;

//System.out.println("tempLeft="+tempLeft+"right="+right);

while(tempLeft=right){

arr[tempLeft++]=temp[t++];

分（遞歸）

publicstaticvoidmergeSort(int[]arr,intleft,intright,int[]temp){

if(leftright){

intmid=(left+right)/2;

mergeSort(arr,left,mid,temp);

mergeSort(arr,mid+1,right,temp);

merge(arr,left,mid,right,temp);

基數(shù)排序（桶排序）

1、基數(shù)排序（radixsort）屬于“分配式排序”（distributionsort），又稱“桶子法”（bucketsort）或binsort，顧名思義，它是通過(guò)鍵值的各個(gè)位的值，將要排序的元素分配至某些“桶”中，達(dá)到排序的作用

2、基數(shù)排序法是屬于穩(wěn)定性的排序，基數(shù)排序法的是效率高的穩(wěn)定性排序法

3、基數(shù)排序(RadixSort)是桶排序的擴(kuò)展

4、基數(shù)排序是1887年赫爾曼·何樂(lè)禮發(fā)明的。它是這樣實(shí)現(xiàn)的：將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個(gè)位數(shù)分別比較。

基數(shù)排序的基本思想

將所有待比較數(shù)值統(tǒng)一為同樣的數(shù)位長(zhǎng)度，數(shù)位較短的數(shù)前面補(bǔ)零。然后，從最低位開(kāi)始，依次進(jìn)行一次排序。這樣從最低位排序一直到最高位排序完成以后,數(shù)列就變成一個(gè)有序序列。

這樣說(shuō)明，比較難理解，下面我們看一個(gè)圖文解釋，理解基數(shù)排序的步驟

數(shù)組的初始狀態(tài)arr={53,3,542,748,14,214}

第1輪排序:

(1)將每個(gè)元素的個(gè)位數(shù)取出，然后看這個(gè)數(shù)應(yīng)該放在哪個(gè)對(duì)應(yīng)的桶(一個(gè)一維數(shù)組)

(2)按照這個(gè)桶的順序(一維數(shù)組的下標(biāo)依次取出數(shù)據(jù)，放入原來(lái)數(shù)組)

數(shù)組的第1輪排序arr={542,53,3,14,214,748}

第2輪排序:

(1)將每個(gè)元素的十位數(shù)取出，然后看這個(gè)數(shù)應(yīng)該放在哪個(gè)對(duì)應(yīng)的桶(一個(gè)一維數(shù)組)

(2)按照這個(gè)桶的順序(一維數(shù)組的下標(biāo)依次取出數(shù)據(jù)，放入原來(lái)數(shù)組)

數(shù)組的第2輪排序arr={3,14,214,542,748,53}

第3輪排序:

(1)將每個(gè)元素百位數(shù)取出，然后看這個(gè)數(shù)應(yīng)該放在哪個(gè)對(duì)應(yīng)的桶(一個(gè)一維數(shù)組)

(2)按照這個(gè)桶的順序(一維數(shù)組的下標(biāo)依次取出數(shù)據(jù)，放入原來(lái)數(shù)組)

數(shù)組的第3輪排序arr={3,14,53,214,542,748}

以上就是基數(shù)排序的實(shí)現(xiàn)過(guò)程

代碼實(shí)現(xiàn)

代碼說(shuō)明

獲取數(shù)組最大元素的位數(shù)

使用二維數(shù)組bucket[10][arr.length]模擬桶

使用bucketElementCounts[10]模擬每個(gè)桶的指針

publicstaticvoidredixSort(int[]arr){

//獲取數(shù)組中最大元素的位數(shù)

intmax=arr[0];

for(inti=0;iarr.length;i++){

if(maxarr[i])

max=arr[i];

intmaxLength=(max+"").length();

//定義一個(gè)二維數(shù)組模擬桶

int[][]bucket=newint[10][arr.length];

//為了記錄每個(gè)桶中的元素個(gè)數(shù)定義一個(gè)一維數(shù)組

int[]bucketElementCounts=newint[10];

for(inti=0,n=1;imaxLength;i++,n*=10){

//入桶

for(intj=0;jarr.length;j++){

intdigitOfElement=arr[j]/n%10;

bucket[digitOfElement][bucketElementCounts[digitOfElement]]=arr[j];

bucketElementCounts[digitOfElement]++;

intindex=0;

//出桶

for(intj=0;jbucketElementCounts.length;j++){

if(bucketElementCounts[j]!=0){

for(intk=0;kbucketElementCounts[j];k++){

arr[index++]=bucket[j][k];

//取出元素后，需要將bucketElementCount中的元素清零

bucketElementCounts[j]=0;

//System.out.println("第"+(i+1)+"次排序后的數(shù)組"+Arrays.toString(arr));

排序算法的速度測(cè)試

下面我創(chuàng)建了一個(gè)長(zhǎng)度分別為80000的隨機(jī)數(shù)組進(jìn)行測(cè)試

硬件:CPU8代i7

publicstaticvoidmain(String[]args){

System.out.println("測(cè)試排序算法的時(shí)間");

int[]arr=newint[80000];

for(inti=0;iarr.length;i++){