數(shù)據(jù)結(jié)構(gòu)與算法之排序算法

排序算法的介紹

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

排序的分類

• 1）內(nèi)部排序：指將需要處理的數(shù)據(jù)都加載到內(nèi)部存儲(chǔ)器(內(nèi)存) 中進(jìn)行排序
• 2）外部排序：數(shù)據(jù)量過(guò)大，無(wú)法全部加載到內(nèi)存中，需要借助外部存儲(chǔ)(文件等) 進(jìn)行排序
• 3）常見(jiàn)的排序算法分類

算法的時(shí)間復(fù)雜度

度量一個(gè)程序（算法）執(zhí)行時(shí)間的兩種方法

• 1）事后統(tǒng)計(jì)的方法：

  ? 這種方法可行，但是有兩個(gè)問(wèn)題，一是要想對(duì)設(shè)計(jì)的算法的運(yùn)行性能進(jìn)行評(píng)測(cè)，需要實(shí)際運(yùn)行該程序；二是所得時(shí)間的統(tǒng)計(jì)量依賴于計(jì)算機(jī)的硬件、軟件等環(huán)境因素，這種方式，要在同一臺(tái)計(jì)算機(jī)的相同狀態(tài)下運(yùn)行，才能比較哪個(gè)算法速度更快。

• 2）事前估算的方法

  ? 通過(guò)分析某個(gè)算法的時(shí)間復(fù)雜度來(lái)判斷哪個(gè)算法更優(yōu)

時(shí)間頻度

介紹

一個(gè)算法花費(fèi)的時(shí)間與算法中語(yǔ)句的執(zhí)行次數(shù)成正比例，哪個(gè)算法中語(yǔ)句執(zhí)行次數(shù)多，它花費(fèi)的時(shí)間就多。一個(gè)算法中的語(yǔ)句執(zhí)行次數(shù)成為語(yǔ)句頻度或時(shí)間頻度 。記為T(n)

案例1：計(jì)算1-100所有數(shù)字的和

int total = 0; int end = 100; //使用for循環(huán)計(jì)算 for(int i = 1;i <= end; i++){total += i; } // T(n) = n+1; //直接計(jì)算 total = (1+end)*end/2; // T(n) = 1;

案例2：忽略常數(shù)項(xiàng)

結(jié)論：

• 1）2n+20和2n 隨著n變大，執(zhí)行曲線無(wú)限接近，20可以忽略
• 2）3n+10和3n 隨著n變大，執(zhí)行曲線無(wú)限接近，10可以忽略

案例3：忽略低次項(xiàng)

結(jié)論：

• 1）2n^2+3n+10 和2n^2 隨著n變大，執(zhí)行曲線無(wú)限接近，3n+10可以忽略
• 2）n^2+5n+20 和n^2 隨著n變大，執(zhí)行曲線無(wú)限接近，5n+20可以忽略

案例4：忽略系數(shù)

結(jié)論：

• 1）隨著n值變大，5n^ 2+7n和3n^2+2n，執(zhí)行曲線重合，說(shuō)明這種情況下，5和3可以忽略
• 2）而n^ 3+5n和6n^3+4n，執(zhí)行曲線分離，說(shuō)明多少次方關(guān)是鍵

時(shí)間復(fù)雜度

• 一般情況下，算法中的基本操作語(yǔ)句 重復(fù)執(zhí)行次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)，用T(n)表示，若有某個(gè)輔助函數(shù)f(n)，使得當(dāng)n趨近于無(wú)窮大時(shí)，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記做T(n)=O(f(n))，稱O(f(n))為算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。
• T(n)不同，但時(shí)間復(fù)雜度可能相同。如：T(n)=n^ 2+7n+6與T(n)=3n^ 2+2n+2，他們的T(n)不同，但時(shí)間復(fù)雜度相同，都為O(n^2)
• 計(jì)算時(shí)間復(fù)雜度的方法：
  • 用常數(shù)1代替運(yùn)行時(shí)間中的所有加法常數(shù) :T(n)=n^ 2+7n+6=>T(n)=n^2+7n+1
  • 修改后的運(yùn)行此數(shù)函數(shù)中，只保留最高階項(xiàng) :T(n)=n^ 2+7n+1=>T(n)=n^2
  • 去除最高階項(xiàng)的系數(shù) :T(n)=n^ 2=>T(n)=n^ 2 =>O(n)=n^2

常見(jiàn)的時(shí)間復(fù)雜度

• 1）常數(shù)階 O(1)

無(wú)論代碼執(zhí)行了多少行，只要沒(méi)有循環(huán)等復(fù)雜結(jié)構(gòu)，那這個(gè)代碼的時(shí)間復(fù)雜度就都是O(1)

int i=1; int j=1; ++i; j++; int m = i + j;

上述代碼在執(zhí)行的時(shí)候，它消耗的時(shí)間并不隨著某個(gè)變量的增長(zhǎng)而增長(zhǎng)，那么無(wú)論這類代碼有多長(zhǎng)，即使有幾萬(wàn)幾十萬(wàn)行，都可以用O()

• 2）對(duì)數(shù)階O(nlog2n)

int i=1; while(i<n){i = i * 2;}

說(shuō)明： 在while循環(huán)里面，每次都將i乘以2，乘完之后，i距離n就越來(lái)越近了。假設(shè)循環(huán)x次之后，i就大于2了，此時(shí)這個(gè)循環(huán)就退出了，也就是說(shuō)2的x次方等于n，那么x=log2n也就是說(shuō)循環(huán)log2n次以后，這個(gè)代碼就結(jié)束了。因此這個(gè)代碼的時(shí)間復(fù)雜度為：O(log2n)。O(log2n)的這個(gè)2時(shí)間上是根據(jù)代碼變化的，i=i*3，則是O()

• 3）線性階O(n)

for(int i = 0;i < n;i++){j = i;j++; }

說(shuō)明： 這段代碼，for循環(huán)里面的代碼會(huì)執(zhí)行n遍，因此它消耗的時(shí)間是隨著n的變化而變化的，因此這類代碼都可以用O()

• 4）線性對(duì)數(shù)階O(nlog2n)

for(int i = 0;i < n;i++){m = 1;while(m < n){m = m * 2;} }

說(shuō)明： 線性對(duì)數(shù)階其實(shí)非常容易理解，將時(shí)間復(fù)雜度為O(logn)的代碼循環(huán)N遍的話，那么它的時(shí)間復(fù)雜度就是n*O(logN)，也就是O(nlogN)

• 5）平方階O(n^2)（雙層for循環(huán)）

for(int i = 0;i<=n;i++){for(int j = i;j<=n;j++){m = i * j;} }

說(shuō)明： 平方階就更容易理解了，如果把O(n)的代碼再嵌套循環(huán)一遍，它的時(shí)間復(fù)雜度就是O(n^ 2),這段代碼其實(shí)就是嵌套了2層n循環(huán)，它的時(shí)間復(fù)雜度就是O(nn)，即O(n^2)，如果將其中一層循環(huán)的n改成m，那么它的時(shí)間復(fù)雜度就變成了O(mn)

• 6）立方階O(n^3)（三層for循環(huán))

• 7）k次方階O(n^k)（k層for循環(huán)）

說(shuō)明： 參考上面的O(n^2)去理解就好了，O()

• 8）指數(shù)階O(2^n)（應(yīng)盡量避免指數(shù)階算法）

常見(jiàn)的時(shí)間復(fù)雜度對(duì)應(yīng)的圖

說(shuō)明：

• 常見(jiàn)的算法時(shí)間復(fù)雜度由小到大依次為：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n^ 2)<O(n^ 3)<O(n^k)<O(n!)，隨著問(wèn)題規(guī)模n的不斷增大，上述時(shí)間復(fù)雜度不斷增大，算法的執(zhí)行效率越低
• 從圖中可見(jiàn)，我們應(yīng)該盡量避免使用指數(shù)階的算法

平均時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度

• 1）平均時(shí)間復(fù)雜度是指所有可能的輸入實(shí)例均以等概率出現(xiàn)的情況下，該算法的運(yùn)行時(shí)間
• 2）最壞情況下的時(shí)間復(fù)雜度稱最壞時(shí)間復(fù)雜度。一般討論的時(shí)間復(fù)雜度均是最壞情況下的時(shí)間復(fù)雜度。 這樣做的原因是：最壞情況下的時(shí)間復(fù)雜度是算法在任何輸入實(shí)例上運(yùn)行時(shí)間的界限，這就保證了算法的運(yùn)行時(shí)間不會(huì)比最壞情況更長(zhǎng)
• 3）平均時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度是否一致，和算法有關(guān)（如圖）：

算法的空間復(fù)雜度

• 1）類似時(shí)間復(fù)雜度的討論，一個(gè)算法的空間復(fù)雜度(Space Complexity)定義為該算法所耗費(fèi)的存儲(chǔ)空間，它也是問(wèn)題規(guī)模n的函數(shù)。
• 2）空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間大小的量度。有的算法需要占用的臨時(shí)工作單元數(shù)與解決問(wèn)題的規(guī)模n有關(guān)，它隨著n的增大而增大，當(dāng)n較大時(shí)，將占用較多的存儲(chǔ)單元，例如快速排序和歸并排序算法，基數(shù)排序 就屬于這種情況。
• 3）在做算法分析時(shí)，主要討論的是時(shí)間復(fù)雜度。從用戶使用體驗(yàn)上看，更看重的是程序執(zhí)行的速度。 一些緩存產(chǎn)品（redis,memcache)和算法（基數(shù)排序）本質(zhì)就是用空間換時(shí)間。

常用的排序算法

冒泡排序

基本介紹

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

優(yōu)化：

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

圖解冒泡排序

小結(jié)：

• 1）一共進(jìn)行 數(shù)組的大小-1 次大的循環(huán)
• 2）每一堂排序的次數(shù)在逐漸的減少
• 3）如果我們發(fā)現(xiàn)在某趟排序中，沒(méi)有發(fā)生一次交換，可以提前結(jié)束冒泡排序，這就是優(yōu)化。

案例

有五個(gè)無(wú)序的數(shù)：3,9，-2,10，-2，使用冒牌排序法將其排成一個(gè)從小到大的有序數(shù)列

package cn.aixuxi.sort;import java.util.Arrays;public class BubbleSort {public static void main(String[] args) {int arr[] = {3, 9, -1, 10, -2};//測(cè)試冒泡排序System.out.println("排序前：");System.out.println(Arrays.toString(arr));bubble(arr);System.out.println("排序后：");System.out.println(Arrays.toString(arr));//為了容易理解，我們把冒泡排序的演變過(guò)程，展示出來(lái)//第一趟排序，將最大的數(shù)排在最后 // int temp = 0;//臨時(shí)變量 // for (int i = 0; i < arr.length - 1; i++) {//如果前面的數(shù)比后面的數(shù)大，則交換 // if (arr[i] > arr[i + 1]) { // temp = arr[i]; // arr[i] = arr[i + 1]; // arr[i + 1] = temp; // } // } // System.out.println("第一趟排序后的數(shù)組"); // System.out.println(Arrays.toString(arr));//第二趟排序，就是將第二大的數(shù)字排在倒數(shù)第二位 // for (int i = 0; i < arr.length - 1 - 1; i++) {//如果前面的數(shù)比后面的數(shù)大，則交換 // if (arr[i] > arr[i + 1]) { // temp = arr[i]; // arr[i] = arr[i + 1]; // arr[i + 1] = temp; // } // } // System.out.println("第二趟排序后的數(shù)組"); // System.out.println(Arrays.toString(arr));//第三趟排序，就是將第三大的數(shù)字排在倒數(shù)第三位 // for (int i = 0; i < arr.length - 1 - 2; i++) {//如果前面的數(shù)比后面的數(shù)大，則交換 // if (arr[i] > arr[i + 1]) { // temp = arr[i]; // arr[i] = arr[i + 1]; // arr[i + 1] = temp; // } // } // System.out.println("第三趟排序后的數(shù)組"); // System.out.println(Arrays.toString(arr));//第四趟排序，就是將第四大的數(shù)字排在倒數(shù)第四位 // for (int i = 0; i < arr.length - 1 - 3; i++) { // 如果前面的數(shù)比后面的數(shù)大，則交換 // if (arr[i] > arr[i + 1]) { // temp = arr[i]; // arr[i] = arr[i + 1]; // arr[i + 1] = temp; // } // } // System.out.println("第四趟排序后的數(shù)組"); // System.out.println(Arrays.toString(arr));}//封裝的優(yōu)化冒泡排序算法public static void bubble(int[] arr) {int temp = 0;//冒泡排序 時(shí)間復(fù)雜度為O(n^2)//優(yōu)化boolean flag = true;//標(biāo)識(shí)變量，表示是否進(jìn)行過(guò)交換for (int i = 0; i < arr.length - 1; i++) {for (int j = 0; j < arr.length - 1; j++) {//如果前面的數(shù)比后面的大，則交換if (arr[j] > arr[j + 1]) {flag = true;temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}if (!flag) {//在一趟排序中，一次交換都沒(méi)有發(fā)生過(guò)break;} else {flag = false;//重置flag，進(jìn)行下次的判斷}}} }

選擇排序

基本介紹

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

選擇排序思想

? 選擇排序（select sorting)也是一種簡(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è)排序碼從小到大排列的有序序列。

思路分析圖

說(shuō)明：

• 1）選擇排序一共有數(shù)組大小-1 輪排序
• 2）每一輪排序，又是一個(gè)循環(huán)，循環(huán)的規(guī)則（代碼）
• 3）先假定當(dāng)前這個(gè)數(shù)是最小數(shù)
• 4）然后和后面的每個(gè)數(shù)進(jìn)行比較，如果發(fā)現(xiàn)有比當(dāng)前數(shù)更小的數(shù)，就重新確定最小數(shù)，并得到下標(biāo)
• 5）當(dāng)遍歷到數(shù)組的最后時(shí)，就得到每輪最小數(shù)和下標(biāo)
• 6）交換代碼中在繼續(xù)循環(huán)

案例

使用選擇排序從低到高進(jìn)行排序：101 34 119 1

package cn.aixuxi.sort;import java.util.Arrays;public class SelectSort {public static void main(String[] args) {int[] arr = {101,34,119,1};selectSort(arr);System.out.println(Arrays.toString(arr));}//算法：先簡(jiǎn)單 ==> 做復(fù)雜，就是可以把一個(gè)復(fù)雜的算法，拆分成簡(jiǎn)單的問(wèn)題，并逐步解決public static void selectSort(int[] arr){// 根據(jù)以下推導(dǎo)，簡(jiǎn)化代碼for (int i = 0; i < arr.length; i++) {int minIndex = i;int min = arr[i];for (int j = i+1; j < arr.length; j++) {if (min>arr[j]){min = arr[j];minIndex = j;}}if (minIndex!=i){arr[minIndex] = arr[i];arr[i] = min;}}//使用逐步的方式，講解選擇排序//第一輪//原始的數(shù)組：101,34,119,1//第一輪排序：1,34,119,101 // int minIndex = 0; // int min = arr[minIndex]; // for (int i = 1; i < arr.length ; i++) { // if (min>arr[i]){//說(shuō)明假定的最小值，并不是最小值 // min = arr[i];//重置min // minIndex = i;//重置minIndex // } // }//將最小值，放在arr[0],即交換 // if (minIndex!=0){ // arr[minIndex] = arr[0]; // arr[0] = min; // }//第二輪 // minIndex = 1; // min = arr[minIndex]; // for (int i = 2; i < arr.length ; i++) { // if (min>arr[i]){//說(shuō)明假定的最小值，并不是最小值 // min = arr[i];//重置min // minIndex = i;//重置minIndex // } // }//將最小值，放在arr[0],即交換 // if (minIndex!=1){ // arr[minIndex] = arr[1]; // arr[1] = min; // }//第三輪 // minIndex = 2; // min = arr[minIndex]; // for (int i = 3; i < arr.length ; i++) { // if (min>arr[i]){//說(shuō)明假定的最小值，并不是最小值 // min = arr[i];//重置min // minIndex = i;//重置minIndex // } // }//將最小值，放在arr[2],即交換 // if (minIndex!=2){ // arr[minIndex] = arr[2]; // arr[2] = min; // }} }

插入排序

基本介紹

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

插入排序法思想

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

插入排序思路圖

案例

請(qǐng)用插入排序法將101,34,119,1從小到大進(jìn)行排序

package cn.aixuxi.sort;import java.util.Arrays;public class InsertSort {public static void main(String[] args) {int[] arr = {101,34,119,1};insertSort(arr);System.out.println(Arrays.toString(arr));}//插入排序public static void insertSort(int[] arr){//根據(jù)以下推導(dǎo),簡(jiǎn)化代碼for (int i = 1; i < arr.length; i++) {int insertVal = arr[i];int insertIndex = i - 1;while (insertIndex >= 0 && insertVal<arr[insertIndex]){arr[insertIndex+1] = arr[insertIndex];insertIndex--;}arr[insertIndex+1] = insertVal;}//逐步推導(dǎo)，便于理解//第一輪 {101,34,119,1} => {34,101,119,1}//定義待插入的數(shù) // int insertVal = arr[1]; // int insertIndex = 0;//即arr[1]前面這個(gè)數(shù)的下標(biāo)//給insertVal找到插入的位置/*** 說(shuō)明：* 1.insertIndex >= 0 保證在給insertVal找插入位置，不越界* 2.insertVal < arr[insertIndex] 待插入的數(shù)，還沒(méi)有找到插入位置* 3.就需要將arr[insertIndex]后移*/ // while (insertIndex >= 0 && insertVal<arr[insertIndex]){ // arr[insertIndex+1] = arr[insertIndex];// // insertIndex--; // }//當(dāng)退出while循環(huán)時(shí)，說(shuō)明插入的位置找到，insertIndex+1; // arr[insertIndex+1] = insertVal;//第二輪 // insertVal = arr[2]; // insertIndex = 1; // while (insertIndex >= 0 && insertVal<arr[insertIndex]){ // arr[insertIndex+1] = arr[insertIndex];// // insertIndex--; // } // arr[insertIndex+1] = insertVal;//第三輪 // insertVal = arr[3]; // insertIndex = 2; // while (insertIndex >= 0 && insertVal<arr[insertIndex]){ // arr[insertIndex+1] = arr[insertIndex];// // insertIndex--; // } // arr[insertIndex+2] = insertVal;} }

希爾排序

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

假設(shè)數(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ì)效率有影響。

希爾排序算法介紹

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

希爾排序算法基本思想

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

希爾排序的示意圖

案例

請(qǐng)對(duì)數(shù)組arr={8,9,1,7,2,3,5,4,6,0}從小到大進(jìn)行排序，要求：

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

2）希爾排序時(shí)，對(duì)有序序列在插入時(shí)采用移動(dòng)法

package cn.aixuxi.sort;import java.util.Arrays;public class ShellSort {public static void main(String[] args) {int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};//換位法shellSort(arr);System.out.println(Arrays.toString(arr));//移位法shellSort2(arr);System.out.println(Arrays.toString(arr));}public static void shellSort(int[] arr) {int temp = 0;//根據(jù)逐步推導(dǎo)，使用循環(huán)處理(交換法）for (int gap = arr.length / 2; gap > 0; gap /= 2) {for (int i = gap; i < arr.length; i++) {//遍歷各組中所有元素（共gap組）步長(zhǎng)gapfor (int j = i - gap; j >= 0; j -= gap) {//如果當(dāng)前元素大于加上步長(zhǎng)后的元素，則交換if (arr[j] > arr[j + gap]) {temp = arr[j];arr[j] = arr[j + gap];arr[j + gap] = temp;}}}}//逐步推導(dǎo)的方式編寫希爾排序（交換法）//希爾排序的第一輪//第一輪排序，將10個(gè)數(shù)據(jù)分成了5組 // for (int i = 5; i < arr.length; i++) { // //遍歷個(gè)組中的所有元素（共5組，每組有2個(gè)元素)，步長(zhǎng)5 // for (int j = i - 5; j >= 0; j -= 5) { // //如果當(dāng)前元素大于加上步長(zhǎng)后的那個(gè)元素，說(shuō)明交換 // if (arr[j] > arr[j + 5]) { // temp = arr[j]; // arr[j] = arr[j + 5]; // arr[j + 5] = temp; // } // } // }//希爾排序第二輪//第二輪排序，將10個(gè)數(shù)據(jù)分成了5/2組 // for (int i = 2; i < arr.length; i++) { // for (int j = i - 2; j >= 0; j -= 2) { // //如果當(dāng)前元素大于加上步長(zhǎng)后的那個(gè)元素，說(shuō)明交換 // if (arr[j] > arr[j + 2]) { // temp = arr[j]; // arr[j] = arr[j + 2]; // arr[j + 2] = temp; // } // } // }//希爾排序第三輪//第三輪排序，將10個(gè)數(shù)據(jù)分成了2/2組 // for (int i = 1; i < arr.length; i++) { // for (int j = i - 1; j >= 0; j -= 1) { // //如果當(dāng)前元素大于加上步長(zhǎng)后的那個(gè)元素，說(shuō)明交換 // if (arr[j] > arr[j + 1]) { // temp = arr[j]; // arr[j] = arr[j + 1]; // arr[j + 1] = temp; // } // } // }}//對(duì)交換式的希爾排序的優(yōu)化==>移位法public static void shellSort2(int[] arr){//增量gap，并逐步的縮小增量for (int gap = arr.length / 2; gap > 0; gap /= 2) {//從第gap個(gè)元素，逐個(gè)對(duì)其所在的組進(jìn)行直接插入排序for (int i = gap; i < arr.length; i++) {int j = i;int temp = arr[i];if (arr[j]<arr[j-gap]){while (j-gap>=0 && temp < arr[j-gap]){//移動(dòng)arr[j] = arr[j-gap];j-=gap;}//當(dāng)退出while循環(huán)后，就給temp找到了插入的位置arr[j] = temp;}}}} }

快速排序

快速排序法介紹

快速排序(Quicksort)是對(duì)冒泡排序的一種改進(jìn)。基本思想是：通過(guò)一趟排序，將要排序的數(shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分?jǐn)?shù)據(jù)都要小，然后再按此方法對(duì)著兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列

快速排序法示意圖

案例

對(duì)arr={-9,78,0,23,-567,70}進(jìn)行從小到大的排序，要求使用快速排序法

package cn.aixuxi.sort;import java.util.Arrays;public class QuickSort {public static void main(String[] args) {int[] arr = {-9, 78, 0, 23, -567, 70};quickSort(arr, 0, arr.length - 1);System.out.println(Arrays.toString(arr));}public static void quickSort(int[] arr, int left, int right) {int l = left;//左下標(biāo)int r = right;//右下標(biāo)//pivot 中軸值int pivot = arr[(left + right) / 2];int temp = 0;//臨時(shí)變量，用于交換時(shí)使用/*** while循環(huán)的目的是讓比pivot值小的放到左邊* 比pivot值大的放到右邊*/while (l < r) {//在pivot 的左邊一直找，找到大于等于pivot的值退出while (arr[l] < pivot) {l += 1;}//在pivot 的右邊一直找，找到小于等于pivot的值退出while (arr[r] > pivot) {r -= 1;}//如果l>=r成立，說(shuō)明pivot的左右兩邊的值，已經(jīng)按照左邊全部是//小于等于pivot的值，右邊全部是大于等于pivot的值if (l >= r) {break;}//交換temp = arr[l];arr[l] = arr[r];arr[r] = temp;//判斷交換完后發(fā)現(xiàn)arr[l] == pivot值相等，r--，前移if (arr[l] == pivot) {r -= 1;}//判斷交換完后發(fā)現(xiàn)arr[r] == pivot值相等，l++，后移if (arr[r] == pivot) {l += 1;}}//如果l==r，必須l++,r--，否則會(huì)出現(xiàn)棧溢出if (l == r) {l += 1;r -= 1;}//向左遞歸if (left < r) {quickSort(arr, left, r);}//向右遞歸if (right > l) {quickSort(arr, l, right);}} }

歸并排序

歸并排序介紹

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

歸并排序思想示意圖

基本思想

合并相鄰有序子序列

在治階段，我們需要將兩個(gè)已經(jīng)有序的子序列合并成一個(gè)有序序列，比如上圖中的最后一次合并，要將[4,5,7,8]和[1,2,3,6]兩個(gè)已經(jīng)有序的子序列，合并為最終序列[1,2,3,4,5,6,7,8]，步驟如下：

案例

對(duì)數(shù)組arr={8,4,5,7,1,3,6,2}進(jìn)行從小到大的排序，要求：使用歸并排序

package cn.aixuxi.sort;import java.util.Arrays;public class MergetSort {public static void main(String[] args) {int[] arr = {8, 4, 5, 6, 1, 3, 6, 2};int[] temp = new int[arr.length];//歸并排序需要額外的空間mergetSort(arr,0,arr.length-1,temp);System.out.println(Arrays.toString(arr));}//分+合的方法public static void mergetSort(int[] arr,int left,int right,int[] temp) {if (left<right){int mid = (left+right)/2;//中間的索引//向左遞歸進(jìn)行分解mergetSort(arr,left,mid,temp);//向右遞歸進(jìn)行分解mergetSort(arr,mid+1,right,temp);//到合并merge(arr,left,mid,right,temp);}}/*** 合并的方法** @param arr 排序的原始數(shù)組* @param left 左邊有序序列的初始索引* @param mid 中間索引* @param right 右邊索引* @param temp 做中轉(zhuǎn)的數(shù)組*/public static void merge(int[] arr, int left, int mid, int right, int[] temp) {int i = left;//初始化i，左邊有序序列的初始索引int j = mid + 1;//初始化j，右邊有序序列的初始索引int t = 0;// 指向temp數(shù)組的當(dāng)前索引//(一)//先把左右兩邊(有序)的數(shù)據(jù)按照規(guī)則填充到temp數(shù)組//直到左右兩邊的有序序列，有一邊處理完畢為止while (i <= mid && j <= right) {//繼續(xù)if (arr[i] <= arr[j]) {//如果左邊的有序序列的當(dāng)前元素，小于等于右邊的有序序列的元素//就把左邊的當(dāng)前元素拷貝到temp數(shù)組//然后t++,i++temp[t] = arr[i];t += 1;i += 1;} else {//反之,將右邊有序序列的當(dāng)前元素，填充到temp數(shù)組temp[t] = arr[j];t += 1;j += 1;}}//(二)//把有剩余數(shù)據(jù)的一邊的數(shù)據(jù)依次全部填充到tempwhile (i <= mid){//說(shuō)明左邊的有序序列還有剩余的元素，就全部填充到temp中temp[t] = arr[i];t++;i++;}while (j <= right){//說(shuō)明右邊的有序序列還有剩余的元素，就全部填充到temp中temp[t] = arr[j];t++;j++;}//(三)//將temp數(shù)組的元素拷貝到arr//注意，并不是每次都拷貝所有的t = 0;int tempLeft= left;//while (tempLeft<=right){//當(dāng)前數(shù)組：//第一次合并，tempLeft = 0;right = 1//第二次合并，tempLeft = 1;right = 3//第三次合并，tempLeft = 0;right = 3//……//最后一次合并，tempLeft = 0;right = 7arr[tempLeft] = temp[t];t++;tempLeft++;}} }

基數(shù)排序

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

• 1）基數(shù)排序（radix sort）屬于“分配式排序”（distribution sort），又稱“桶子法”（bucket sort）或bin sort，顧名思義，它是通過(guò)鍵值的各個(gè)位的值，將要排序的元素分配到某些“桶”中，達(dá)到排序的作用
• 2）基數(shù)排序法是屬于穩(wěn)定性的排序，基數(shù)排序法是效率高的穩(wěn)定性排序法
• 3）基數(shù)排序是桶排序的擴(kuò)展
• 4）基數(shù)排序是1887年郝?tīng)柭?#96;何樂(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è)有序序列

基數(shù)排序示意圖

將數(shù)組{53,3,542,748,14,214}使用基數(shù)排序，進(jìn)行升序排序

案例

將數(shù)組{53,3,542,748,14,214}使用基數(shù)排序，進(jìn)行升序排序

package cn.aixuxi.sort;import java.util.Arrays;public class RadixSort {public static void main(String[] args) {int[] arr = {53, 3, 542, 748, 14, 214};radixSort(arr);System.out.println(Arrays.toString(arr));}//基數(shù)排序public static void radixSort(int[] arr) {//定義一個(gè)二維數(shù)組，表示10個(gè)桶，每個(gè)桶就是一個(gè)一維數(shù)組//說(shuō)明//1.二維數(shù)組包含10個(gè)一維數(shù)組//2.為了防止在放入數(shù)的時(shí)候，數(shù)據(jù)溢出，則每個(gè)一維數(shù)組（桶），大小為arr.length//3.明顯，基數(shù)排序是明顯的空間換時(shí)間的算法int[][] bucket = new int[10][arr.length];//為了記錄每個(gè)桶中，實(shí)際存放了多少個(gè)數(shù)據(jù)，我們定義一個(gè)一維數(shù)組來(lái)定義各個(gè)桶每次放入的數(shù)據(jù)個(gè)數(shù)int[] bucketElementCounts = new int[10];int index;//根據(jù)推導(dǎo)過(guò)程，我們可以得到基數(shù)排序的//1.得到數(shù)組最大的數(shù)的位數(shù)int max = arr[0];//假設(shè)第一個(gè)數(shù)就是最大數(shù)for (int i = 0; i < arr.length; i++) {if (max < arr[i]) {max = arr[i];}}//2.得到最大數(shù)是幾位數(shù)int maxLength = (max + "").length();for (int k = 0, n = 1; k < maxLength; k++, n *= 10) {//針對(duì)每個(gè)元素的對(duì)應(yīng)位進(jìn)行排序處理，第一次個(gè)位，第二次十位等for (int i = 0; i < arr.length; i++) {//取出每個(gè)元素對(duì)應(yīng)位的值int digitOfElement = arr[i] / n % 10;//放入到對(duì)應(yīng)的桶中bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[i];bucketElementCounts[digitOfElement]++;}//按照這個(gè)桶的順序（一維數(shù)組的下標(biāo)依次取出數(shù)據(jù)，放入原來(lái)數(shù)組中）index = 0;//遍歷每一桶，并將桶中的數(shù)據(jù)放入原數(shù)組for (int i = 0; i < bucketElementCounts.length; i++) {//如果桶中有數(shù)據(jù)，我們才放入到原數(shù)組if (bucketElementCounts[i] != 0) {//循環(huán)該桶，即第i個(gè)桶（即第i個(gè)一維數(shù)組），放入數(shù)據(jù)for (int j = 0; j < bucketElementCounts[i]; j++) {//取出元素，放入到arr中arr[index++] = bucket[i][j];}}//每一輪處理后，需要將每個(gè)bucketElementCounts[i] = 0bucketElementCounts[i] = 0;}}//第一輪排序（針對(duì)每個(gè)元素的個(gè)位進(jìn)行排序處理 // for (int i = 0; i < arr.length; i++) {//取出每個(gè)元素的個(gè)位的值 // int digitOfElement = arr[i] % 10;//放入到對(duì)應(yīng)的桶中 // bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[i]; // bucketElementCounts[digitOfElement]++; // }//按照這個(gè)桶的順序（一維數(shù)組的下標(biāo)依次取出數(shù)據(jù)，放入原來(lái)數(shù)組中） // int index = 0;//遍歷每一桶，并將桶中的數(shù)據(jù)放入原數(shù)組 // for (int i = 0; i < bucketElementCounts.length; i++) {//如果桶中有數(shù)據(jù)，我們才放入到原數(shù)組 // if (bucketElementCounts[i] != 0) {//循環(huán)該桶，即第i個(gè)桶（即第i個(gè)一維數(shù)組），放入數(shù)據(jù) // for (int j = 0; j < bucketElementCounts[i]; j++) {//取出元素，放入到arr中 // arr[index++] = bucket[i][j]; // } // }//第一輪處理后，需要將每個(gè)bucketElementCounts[i] = 0 // bucketElementCounts[i] = 0; // }//第二輪排序（針對(duì)每個(gè)元素的十位進(jìn)行排序處理 // for (int i = 0; i < arr.length; i++) {//取出每個(gè)元素的個(gè)位的值 // int digitOfElement = arr[i] / 10 % 10;//放入到對(duì)應(yīng)的桶中 // bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[i]; // bucketElementCounts[digitOfElement]++; // }//按照這個(gè)桶的順序（一維數(shù)組的下標(biāo)依次取出數(shù)據(jù)，放入原來(lái)數(shù)組中） // index = 0;//遍歷每一桶，并將桶中的數(shù)據(jù)放入原數(shù)組 // for (int i = 0; i < bucketElementCounts.length; i++) {//如果桶中有數(shù)據(jù)，我們才放入到原數(shù)組 // if (bucketElementCounts[i] != 0) {//循環(huán)該桶，即第i個(gè)桶（即第i個(gè)一維數(shù)組），放入數(shù)據(jù) // for (int j = 0; j < bucketElementCounts[i]; j++) {//取出元素，放入到arr中 // arr[index++] = bucket[i][j]; // } // } // bucketElementCounts[i] = 0; // }//第三輪排序（針對(duì)每個(gè)元素的百位進(jìn)行排序處理 // for (int i = 0; i < arr.length; i++) {//取出每個(gè)元素的個(gè)位的值 // int digitOfElement = arr[i] / 100 % 10;//放入到對(duì)應(yīng)的桶中 // bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[i]; // bucketElementCounts[digitOfElement]++; }//按照這個(gè)桶的順序（一維數(shù)組的下標(biāo)依次取出數(shù)據(jù)，放入原來(lái)數(shù)組中） // index = 0;//遍歷每一桶，并將桶中的數(shù)據(jù)放入原數(shù)組 // for (int i = 0; i < bucketElementCounts.length; i++) {//如果桶中有數(shù)據(jù)，我們才放入到原數(shù)組 // if (bucketElementCounts[i] != 0) {//循環(huán)該桶，即第i個(gè)桶（即第i個(gè)一維數(shù)組），放入數(shù)據(jù) // for (int j = 0; j < bucketElementCounts[i]; j++) {//取出元素，放入到arr中 // i arr[index++] = bucket[i][j]; // } // } // }} }

基數(shù)排序的說(shuō)明

• 1）基數(shù)排序是對(duì)傳統(tǒng)桶排序的擴(kuò)展，速度很快
• 2）基數(shù)排序是經(jīng)典的空間換時(shí)間的方式，占用內(nèi)存很大，當(dāng)對(duì)海量數(shù)據(jù)排序時(shí)，容易造成OutOfMemoryError
• 基數(shù)排序是穩(wěn)定的。【注：假定在待排序的記錄序列中，存在多個(gè)具有相同的關(guān)鍵字的記錄，若經(jīng)過(guò)排序，這些記錄的相對(duì)次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的】
• 有負(fù)數(shù)的數(shù)組，我們不用基數(shù)排序來(lái)進(jìn)行排序，如果要支持負(fù)數(shù)，參考https://code.i-harness.com/zh-CN/q/e98fa9

基數(shù)排序

總結(jié)和對(duì)比

一張圖對(duì)比排序算法

相關(guān)術(shù)語(yǔ)

• 1）穩(wěn)定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面
• 2）不穩(wěn)定：如果a原本在b前面，而a=b，排序之后a可能會(huì)出現(xiàn)在b的后面
• 3）內(nèi)排序：所有排序操作都在內(nèi)存中完成
• 4）外排序：由于數(shù)據(jù)太大，因此把數(shù)據(jù)放在磁盤中，而排序通過(guò)磁盤和內(nèi)存的數(shù)據(jù)傳輸才能進(jìn)行
• 5）時(shí)間復(fù)雜度：一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間
• 6）空間復(fù)雜度：運(yùn)行完一個(gè)程序所需內(nèi)存的大小
• 7）n：數(shù)據(jù)規(guī)模
• 8）k：“桶”的個(gè)數(shù)
• 9）In-place：不占用額外內(nèi)存
• 10）Out-place：占用額外內(nèi)存

今日小結(jié)

其實(shí)排序算法中還有一個(gè)堆排序，不過(guò)和我接下來(lái)要繼續(xù)復(fù)習(xí)的二叉樹(shù)內(nèi)容相關(guān)。這些算法以前也學(xué)過(guò)，但是現(xiàn)在重新看一下，還是受益良多，感覺(jué)感觸更深。溫故而知新，古人誠(chéng)不欺我。

總結(jié)

以上是生活随笔為你收集整理的数据结构与算法之排序算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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