1、簡介

排序是將元素按著指定關(guān)鍵字的大小遞增或遞減進(jìn)行數(shù)據(jù)的排列，排序可以提高查找的效率

2、排序算法的分類

排序算法可大致分為四類七種，具體分類如下：

? ? ? ?插入排序：直接插入排序、希爾排序

? ? ? ?交換排序：冒泡排序、快速排序

? ? ? ?選擇排序：直接選擇排序、堆排序

? ? ? ?歸并排序

3、插入排序

算法思想：每次將一個元素按著關(guān)鍵字大小插入到他前面已經(jīng)排好序的子序列中，重復(fù)進(jìn)行這個操作，直至插入所有數(shù)據(jù)。

3、1 直接插入排序

算法描述：假設(shè)前i個元素構(gòu)成的子序列是有序的，然后根據(jù)關(guān)鍵字大小順序?qū)⒌趇+1個元素a[i] 添加到已經(jīng)排好序的子序列中，使得插入a[i]后的序列仍是一個有序序列，這樣當(dāng)元素都插入序列時，則排序完成。

算法實(shí)現(xiàn)：

/*** 直接插入排序* @author chaizepeng*/private static void directInsertSort1(int[] array) {for (int i = 1; i < array.length; i++) {int temp = array[i];//拿到下一個需要插入的數(shù)值for (int j = i-1; j >= 0; j--) {//遍歷已經(jīng)排好序的集合//將想要插入的元素和已經(jīng)排好序的集合中的每一個進(jìn)行比較if (temp < array[j]) {array[j+1] = array[j];}else {array[j+1] = temp;break;}}}}/*** 直接插入排序* @author chaizepeng*/private static void directInsertSort2(int[] array) {for (int i = 1; i < array.length; i++) {int temp = array[i];//拿到下一個需要插入的數(shù)值int j ;for (j = i-1; j >= 0 && temp < array[j]; j--) {//遍歷已經(jīng)排好序的集合//將想要插入的元素和已經(jīng)排好序的集合中的每一個進(jìn)行比較array[j+1] = array[j];}array[j+1] = temp;}}

算法分析：

假設(shè)一個序列{1,2,3,4,5}，使用直接插入排序時，每個個元素需要比較1次，移動兩次（現(xiàn)將第i個給temp，再將第temp給第i個）即可，則完成排序總需比較n-1次，移動2(n-1)次，時間復(fù)雜度是O（n）

再假設(shè)一個序列{5,4,3,2,1},使用直接插入排序時，第i個元素準(zhǔn)備插入時，需要比較i-1次，移動2+（i-1）次（前一個元素往后移動一次，第i元素先給temp，然后temp再給第1個元素）也就是i+1次，所以n個元素總共許比較n（n-1）/2次，移動（n-1）（n+4）/2次，所以時間復(fù)雜度為O（n^2）

所以插入排序算法的時間復(fù)雜度在O（n）到O（n^2）之間，其排序效率與比較次數(shù)和元素長度直接相關(guān)。

3、2 希爾排序

算法描述：

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

/*** 希爾排序* @author chaizepeng*/private static void shellSort1(int[] array) {int len = array.length;int i,j,gap;//步長每次除以2，使用步長來對數(shù)組進(jìn)行分組//步長的直接意思就是，每隔len個元素則為同一組元素,步長在數(shù)值上等于組數(shù)for (gap = len / 2 ; gap > 0 ; gap /= 2){//因?yàn)槊看味际浅?，所以當(dāng)步長越小時，每組中的元素越多，越接近于有序//這里是遍歷根據(jù)步長分割的每一組for (i = 0 ; i < gap ; i++){//將每組中的元素進(jìn)行排序,j是在i+gap開始的，因?yàn)槊扛鬵ap個數(shù)便是同一組數(shù)據(jù)//這是遍歷每組中的每一個數(shù)據(jù)，組內(nèi)數(shù)據(jù)進(jìn)行比較，直接插入排序//i+gap正好是獲取到數(shù)組中的每一個數(shù)據(jù)for (j = i + gap ; j < len ; j += gap){if(array[j] < array[j - gap]){int temp = array[j];int k = j - gap;while (k >= 0 && array[k] > temp){array[k + gap] = array[k];k -= gap;}array[k + gap] = temp;}}}}}/*** 希爾排序* @param array*/private static void shellSort2(int[] array){int len = array.length;int j , gap;for (gap = len / 2 ; gap > 0 ; gap /= 2){for (j = gap ; j < len ; j++){if (array[j] < array[j - gap]){int temp = array[j];int k = j - gap;while (k >= 0 && array[k] > temp){array[k + gap] = array[k];k -= gap;}array[k + gap] = temp;}}}}/*** 希爾排序* @param array*/private static void shellSort3(int[] array) {int i,j,gap;int len = array.length;for (gap = len / 2 ; gap > 0 ; gap /= 2){for (i = gap ; i < len ; i++){for (j = i - gap ; j>= 0 && array[j] > array[j+gap] ; j -= gap){int temp = array[j];array[j] = array[j+gap];array[j+gap] = temp;}}}}

?算法分析：

因?yàn)楦鶕?jù)之前對直接插入排序的分析可以知道直接插入排序算法的效率與比較次數(shù)和元素長度直接相關(guān)，可以看出希爾排序是對直接插入排序算法做了優(yōu)化，針對的就是比較次數(shù)和元素的長度，希爾排序講究先分組排序，這樣就見效了移動的次數(shù)，隨著元素長度的增加，序列趨于有序，減少了比較的次數(shù)，降低了時間復(fù)雜度。另外，希爾排序的時間復(fù)雜度是O(n*(logn)^2)。

排序算法的穩(wěn)定性：是對關(guān)鍵字相同的元素排序性能的描述，當(dāng)兩個元素A,B相等，排序之前A在B前邊，如果排完排完序之后，A仍然在B前邊，則說明排序算法是穩(wěn)定的。自我感覺分析一個算法穩(wěn)定還是不穩(wěn)定是可行的，但是如果說一個算法是穩(wěn)定還是不穩(wěn)定的應(yīng)該不準(zhǔn)確吧？對于穩(wěn)定性而言是不是就是對臨界元素的一種處理方式而已呢？不必糾結(jié)。

?4、交換排序?

4、1 冒泡排序

算法描述：假設(shè)按著升序排序，就是從第一個元素開始比較相鄰兩個元素的值，如果前邊的比后邊的大，則交換兩個值得位置，然后繼續(xù)往后進(jìn)行比較交換操作，一趟下來使得序列中最大的數(shù)在最后邊，假設(shè)長度是n，則第一趟將最大的數(shù)放在第n個位置上，然后再進(jìn)行第二趟，第二趟下來之后保證除第n個數(shù)之外最大數(shù)在第n-1的位置，然后繼續(xù)下一趟，重復(fù)上邊操作，直到不需要繼續(xù)元素交換了便排序結(jié)束了。

算法實(shí)現(xiàn)：

/*** 冒泡排序* @author chaizepeng*/ private static void bubbleSort1(int[] array) {int len = array.length;//控制比較的長度，最長len-1for (int i = len-1; i > 0; i--) {//第二層循環(huán)控制比較大小和交換位置for (int j = 0; j < i; j++) {if (array[j] > array[j+1]) {//如果前一個數(shù)比后一個數(shù)大，則交換位置int temp = array[j];array[j] = array[j+1];array[j+1] = temp;}}System.out.println("共有"+len+"個元素，這是第"+(len - i)+"趟");} }/*** 冒泡排序* @author chaizepeng*/ private static void bubbleSort2(int[] array) {int len = array.length;//外層循環(huán)控制遍歷趟數(shù)，最多循環(huán)len-1次for (int i = 0; i < len-1; i++) {for (int j = 0; j < len - 1 - i; j++) {//第二層循環(huán)控制比較大小和交換位置if (array[j] > array[j+1]) {//如果前一個數(shù)比后一個數(shù)大，則交換位置int temp = array[j];array[j] = array[j+1];array[j+1] = temp;}}System.out.println("共有"+len+"個元素，這是第"+(i+1)+"趟");} }/*** 冒泡排序使用添加標(biāo)記的方式進(jìn)行優(yōu)化，序列越接近有序，效率越高* @author chaizepeng*/ private static void bubbleSort3(int[] array) {int len = array.length;//標(biāo)記boolean flag;//外層循環(huán)控制遍歷趟數(shù)，最多循環(huán)len-1次for (int i = 0; i < len-1; i++) {flag = true;for (int j = 0; j < len - 1 - i; j++) {//第二層循環(huán)控制比較大小和交換位置if (array[j] > array[j+1]) {//如果前一個數(shù)比后一個數(shù)大，則交換位置int temp = array[j];array[j] = array[j+1];array[j+1] = temp;flag = false;}}System.out.println("共有"+len+"個元素，這是第"+(i+1)+"趟");//如果沒有進(jìn)行數(shù)據(jù)交換，也就是flag==trueif (flag) {break;//不再繼續(xù)下一趟}} }

算法分析：冒泡排序記住一點(diǎn)，只要沒有元素交換了，則排序完成。

?

例如序列{1,2,3,4,5}，第一趟比較4次，沒有元素移動，時間復(fù)雜度O（n）

再例如序列{5,4,3,2,1}，第一趟比較4次，移動12次，時間復(fù)雜度為O（n^2）

所以冒泡排序算法的時間復(fù)雜度在O（n）到O（n^2）之間，其時間復(fù)雜度與序列是否有序有直接關(guān)系，并且算法是穩(wěn)定的。此算法每次都借助了一個臨時的中間元素，用來交換兩個數(shù)。

4、2 快速排序

算法描述：快速排序是對冒泡排序的優(yōu)化，快速排序第一趟就根據(jù)某個元素將序列分成兩部分，一部分中所有數(shù)據(jù)比此元素小，另一部分的所有數(shù)比此元素大或等于此元素；然后再對這兩部分分別進(jìn)行分割，整個過程可以遞歸進(jìn)行，直到序列有序。

算法實(shí)現(xiàn)：

/*** 看圖理解代碼，一下子就全明白了* @author chaizepeng*/ private static void quickSort1(int[] array) {int i = 0;int j = array.length - 1;quickSort(i,j,array); }/*** 遞歸實(shí)現(xiàn)快排算法* @author chaizepeng*/ private static void quickSort(int i, int j, int[] array) {int left = i;int right = j;int key = array[i];while (i < j) {//只要不相等就循環(huán)比較，交換操作//從右往左遍歷while(i < j && array[j] >= key) {j--;}if (array[j] < key) {//每次交換的都是一個小于key的元素和key所在位置上的值，也就是key值int temp = array[i];array[i] = array[j];array[j] = temp;}//從左往右遍歷while(i < j && array[i] <= key) {i++;}//交換i處和j處的數(shù)據(jù)if (array[i] > key) {//每次交換的都是一個大于key的元素和key所在位置上的值，也就是key值int temp = array[i];array[i] = array[j];array[j] = temp;}}//遞歸使用if (i > left) {quickSort(0, i, array);}if (j < right) {quickSort(j + 1, array.length-1, array);} }

算法分析：

?這里寫的快排是不穩(wěn)定，快速排序算法效率受標(biāo)記值（基準(zhǔn)值）的影響，假如每次選擇的基準(zhǔn)值都是最值的話，那么就會導(dǎo)致被分割的子序列是不平衡的（一個里邊就一個元素，另一個里邊是其余的n-1個元素），則需要比較的趟數(shù)就會增加，導(dǎo)致算法效率低下，快排的時間復(fù)雜度在O(nlogn)到O(n^2)之間。所以想要提高快排的效率就要保證每次找的基準(zhǔn)值是當(dāng)前序列的中間值。

快排的空間復(fù)雜度在O(logn)到O(n)之間

5、選擇排序

5、1 直接選擇排序

算法描述：以升序?yàn)槔?#xff1a;從第一個元素開始，依次比較序列中的元素，將最小的元素放在第一個位置；接著在第二個元素開始，依次比較序列中的值，將最小的元素放在第二個位置，依次類推，直到排序結(jié)束。

算法實(shí)現(xiàn)：

/*** 以升序?yàn)槔?#xff1a;從第一個元素開始，依次比較序列中的元素，將最小的元素放在第一個位置；接著在第二個元素開始，依次比較序列中的值，將最小的元素放在第二個位置，依次類推，直到排序結(jié)束* 直接選擇排序* @author chaizepeng*/ private static void straightSelectSort(int[] array) {//控制比較的趟數(shù)for (int i = 0; i < array.length - 1; i++) {int minFlag = i;//記錄一下最小值所在的下標(biāo)for (int j = i+1; j < array.length; j++) {//控制從何處開始比較，比較到何處結(jié)束if (array[j] < array[minFlag]) {//比較當(dāng)前值和之前記錄的最小下標(biāo)對應(yīng)的值minFlag = j;}}//將最小值放在最前邊if (minFlag != i) {int temp = array[minFlag];//最小值array[minFlag] = array[i];//將當(dāng)前值賦給最小值所在的位置array[i] = temp;//當(dāng)前位置放最小值}} }

算法分析：

直接選擇排序，最多需要n-1趟，并且每一趟都需進(jìn)行n-i此的比較，所以時間復(fù)雜度是O(n^2)，并且直接選擇排序是不穩(wěn)定的算法。自我感覺這是最容易理解和實(shí)現(xiàn)的排序算法。

5、2 堆排序

算法描述：堆排序是對直接選擇排序的一種優(yōu)化，直接選擇排序算法在每一趟比較兩個數(shù)大小時， 只是比較大小沒有做任何操作， 而堆排序針對此處做了優(yōu)化，他在比較的同時也將其他的元素（不是最小的元素）做了相應(yīng)調(diào)整。堆排序是先使用待排序的序列構(gòu)建一個堆，這里用大頂堆來實(shí)現(xiàn)，然后根據(jù)大頂堆的特點(diǎn)，將根結(jié)點(diǎn)元素放到最后（這里實(shí)現(xiàn)升序排序），然后將剩下的元素再構(gòu)成一個大頂堆，依次進(jìn)行，直到堆的長度為1結(jié)束排序。

說一下什么是堆，堆是一種數(shù)據(jù)結(jié)構(gòu)，首先是一個完全二叉樹（有右子樹必有左子樹的二叉樹），另外，這個完全二叉樹的各個結(jié)點(diǎn)上的數(shù)值從根結(jié)點(diǎn)到每一個葉子結(jié)點(diǎn)都會有一種規(guī)律：
?? ? 父結(jié)點(diǎn)一定大于或者等于其孩子結(jié)點(diǎn)，這樣的稱為大頂堆
?? ? 父結(jié)點(diǎn)一定小于或者等于其孩子結(jié)點(diǎn)，這樣的稱為小頂堆

算法實(shí)現(xiàn)：

/*** * 堆排序：是對直接選擇排序的一種優(yōu)化，直接選擇排序算法在每一趟比較兩個數(shù)大小時， 只是比較大小沒有做任何操作，* 而堆排序針對此處做了優(yōu)化，他在比較的同時也將其他的元素（不是最小的元素）做了相應(yīng)調(diào)整。堆排序是先使用待排序的序列構(gòu)建一個堆，這里用大頂堆來實(shí)現(xiàn)，* 然后根據(jù)大頂堆的特點(diǎn)，將根結(jié)點(diǎn)元素放到最后（這里實(shí)現(xiàn)升序排序），然后將剩下的元素再構(gòu)成一個大頂堆，依次進(jìn)行，直到堆的長度為1結(jié)束排序。* 存儲堆時的數(shù)據(jù)下標(biāo)在1開始，而不是0，因?yàn)榭梢灾苯邮褂枚鏄涞男再|(zhì)進(jìn)行堆的構(gòu)建 * @author chaizepeng*/ private static void heapSort(int[] array) {//這里已經(jīng)-1了int len = array.length-1;//用待排序的序列構(gòu)建一個大頂堆，因?yàn)榕判蚴墙柚呀Y(jié)構(gòu)進(jìn)行的，這里相當(dāng)于初始化堆//存儲序列的數(shù)組下標(biāo)必須在1開始，根據(jù)平衡二叉樹的順序存儲特性可以知道，len/2之后的是葉子節(jié)點(diǎn)，而len/2以及它前邊的結(jié)點(diǎn)是存在子結(jié)點(diǎn)的//依次遍歷每一個存在子結(jié)點(diǎn)的結(jié)點(diǎn)，然后進(jìn)行判斷、交換結(jié)點(diǎn)，使得構(gòu)建一個堆//1、初始化最大堆for (int i = len/2; i > 0; i--) {heapAdjust(array, i, len);}for (int i = 1; i < array.length; i++) {System.out.print(array[i]+" ");}System.out.println("--------------------------");//2、交換根結(jié)點(diǎn)和最后一個結(jié)點(diǎn)位置，將剩下的重新構(gòu)建一個堆for (int i = len; i > 1; i--) {//交換元素int temp = array[i];array[i] = array[1];array[1] = temp;heapAdjust(array, 1, i-1);} }/*** 構(gòu)建大頂堆* 什么是堆：* 堆是一種數(shù)據(jù)結(jié)構(gòu)，首先是一個完全二叉樹（有右子樹必有左子樹的二叉樹），另外，這個完全二叉樹的各個結(jié)點(diǎn)上的數(shù)值從根結(jié)點(diǎn)到每一個葉子結(jié)點(diǎn)都會有一種規(guī)律：* 父結(jié)點(diǎn)一定大于或者等于其孩子結(jié)點(diǎn)，這樣的稱為大頂堆* 父結(jié)點(diǎn)一定小于或者等于其孩子結(jié)點(diǎn)，這樣的稱為小頂堆* @author chaizepeng*/ private static void heapAdjust(int[] array, int i, int len) {//遍歷當(dāng)前操作結(jié)點(diǎn)對應(yīng)的子結(jié)點(diǎn)int j ;for (j = i * 2; j <= len ; j *= 2) {//記錄一下當(dāng)前操作的結(jié)點(diǎn)int temp = array[i];//子結(jié)點(diǎn)的左孩子和右孩子進(jìn)行比較//這里為什么要比較一下呢？假設(shè)子結(jié)點(diǎn)比父節(jié)點(diǎn)大，則需要上浮子結(jié)點(diǎn)，但是有可能有左右兩個結(jié)點(diǎn)，這里比較一下，確定哪一個結(jié)點(diǎn)上浮//此處j < len 必須要加if (j < len && array[j] < array[j+1]) {++j;}//如果當(dāng)前操作的結(jié)點(diǎn) > 子結(jié)點(diǎn) ，不操作if (temp >= array[j]) {break;}//交換父子結(jié)點(diǎn)的值array[i] = array[j];array[j] = temp;//將需要判斷的元素下標(biāo)改成下降的元素下標(biāo)，用于與其子節(jié)點(diǎn)進(jìn)行判斷i = j;} }

?算法分析：

?堆排序的時間復(fù)雜度是O(n㏒n)，算法是不穩(wěn)定的。堆排序算法充分利用了完全二叉樹的性質(zhì)，效率高，比較復(fù)雜，不容易理解，比較適合元素多的序列排序使用。

6、歸并排序

算法描述：歸并排序使用的是算法設(shè)計(jì)中分治的思想，分而治之，然后合并，將小的子序列進(jìn)行排序，然后慢慢的將有序的子序列進(jìn)行合并，最終使得整個序列有序，這里介紹的是二路歸并算法，也就是每次只將兩個子序列進(jìn)行歸并。具體操作是這樣的，每次是將兩個序列A、B進(jìn)行合并，這里假設(shè)這兩個序列是有序的，首先初始一個長度為兩個序列長度之和的容器，然后聲明兩個標(biāo)記位i，j，i指向序列A的第一個元素，j指向序列B的第一個元素，然后比較兩個數(shù)組中標(biāo)記位上數(shù)的大小，哪一個小就將標(biāo)記位上的數(shù)放到初始的容器中，然后將標(biāo)記位指向下一個元素，然后直至其中一個序列中的元素已被移動完畢，則將另一個序列中的元素復(fù)制到容器中，排序完畢，這只是核心的兩個序列歸并邏輯。

算法實(shí)現(xiàn)：

public static void main(String[] args) {int []array = {24, 27 ,41, 44, 19, 47 ,50 ,5,65, 93 ,94 };for (int i = 0; i < array.length; i++) {System.out.print(array[i]+" ");}System.out.println();System.out.println("-----------------------------");//從第一個元素開始，第一次歸并時，每一個歸并的序列長度是1（默認(rèn)每一個序列長度為1的序列是有序的）mergeSort(array,1);for (int i = 0; i < array.length; i++) {System.out.print(array[i]+" ");} }/*** * @author chaizepeng** @param array 排序總序列* @param len 要?dú)w并的序列的長度*/ private static void mergeSort(int[] array ,int len) {//序列{6,5,8,4,7,9,2,1,4}要進(jìn)行歸并，第一次歸并時需要將相鄰的兩個元素進(jìn)行排序歸并，分組如下//6,5,8,4,7,9,2,1,4//此時，需要比較兩個相鄰的元素,所以，就需要進(jìn)行分組和排序//6,5 8,4 7,9 2,1 4//需要先判斷一下要分幾個組int count = array.length / (len * 2);//判斷一下count的值，如果=0的話，則說明len*2已經(jīng)大于序列總長度，這時序列已經(jīng)排序完成，結(jié)束即可if (count == 0) {return;}//然后依次歸并for (int i = 0; i < count; i++) {//i*len 第一個序列的第一個元素位置//len 有序序列長度//(2+i)*len 第二個序列的最后一個元素位置（不包括）merge(array,i*len*2,(i+1)*len*2,len);}//在這里判斷一下是否歸并正好兩兩對應(yīng)，如果有剩下的，則也需要?dú)w并一下(這里是拿剩下的序列組和它的前一組進(jìn)行歸并操作)int rem = array.length % (len * 2);if (rem != 0) {merge(array, array.length-rem-len, array.length,len);}//進(jìn)行完一次歸并后，繼續(xù)下一次操作//子序列長度為len的已經(jīng)歸并完成，下一次使用len*2作為長度繼續(xù)歸并mergeSort(array,len * 2); }/*** 一次歸并過程* @author chaizepeng** @param array* @param leftBegin* @param rightEnd* @param len*/ private static void merge(int[] array, int leftBegin, int rightEnd,int len) {//標(biāo)記位，用于復(fù)制數(shù)組用int flag = leftBegin;//用一個數(shù)組來存一下需要合并的序列 int []temp = new int[rightEnd - leftBegin];int leftEnd = leftBegin + len;int rightBegin =leftEnd;//右邊序列開始的位置//標(biāo)記temp的下標(biāo)int j = 0;//比較兩個序列中的元素大小，進(jìn)行填充while (leftBegin < leftEnd && rightBegin < rightEnd) {if (array[leftBegin] > array[rightBegin]) {temp[j++] = array[rightBegin++];}else {temp[j++] = array[leftBegin++];}}//判斷一下前后兩個被比較的序列那個還有元素剩余，則直接復(fù)制到temp中while(leftBegin < leftEnd) {temp[j++] = array[leftBegin++];}while(rightBegin < rightEnd) {temp[j++] = array[rightBegin++];}//將temp中的數(shù)據(jù)填到array中for (int k = 0; k < temp.length; k++) {array[flag+k] = temp[k];} }

?算法分析：

?歸并算法的時間復(fù)雜度是O(n㏒n)，算法是穩(wěn)定的，效率較高。

7、性能比較

沒有絕對好的算法，要根據(jù)具體的情況來分析那個算法更好，平均情況下快排（個人比較喜歡快排）、堆排序和歸并排序效率高；如果排序的序列基本有序，那么冒泡排序和直接插入排序效率比較高；如果序列基本逆序，則堆排序和歸并排序效率高；在空間復(fù)雜度上看，堆排序是最好的。但是快排是最常用的。

附加一張算法指標(biāo)對比表：

?

總結(jié)

以上是生活随笔為你收集整理的6、java中的排序算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。