一、基本介紹
- 排序也稱排序算法(Sort Algorithm)，排序是將一組數(shù)據(jù)，依指定的順序進(jìn)行排列的過程。
- 排序的分類：
- 內(nèi)部排序:指將需要處理的所有數(shù)據(jù)都加載到內(nèi)部存儲器中進(jìn)行排序。
- 外部排序法：數(shù)據(jù)量過大，無法全部加載到內(nèi)存中，需要借助外部存儲進(jìn)行排序。
- 而在面試中問道的一般都是內(nèi)部排序，常見的排序算法分類(見下圖):
在介紹排序算法之前，我們首先需要了解算法的時(shí)間復(fù)雜度來衡量各個(gè)算法的效率：
-
舉個(gè)栗子，下面兩種方法求1到100的和，哪種方法的時(shí)間復(fù)雜度更小一點(diǎn)呢？答案顯而易見，第二種會更好一點(diǎn)。
時(shí)間復(fù)雜度的基本概念
一般情況下，算法中的基本操作語句的重復(fù)執(zhí)行次數(shù)是問題規(guī)模n的某個(gè)函數(shù)，用T(n)表示，若有某個(gè)輔助函數(shù)f(n)，使得當(dāng)n趨近于無窮大時(shí)，T(n) / f(n) 的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作 T(n)=Ｏ( f(n) )，稱Ｏ( f(n) ) 為算法的漸進(jìn)時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度。
T(n) 不同，但時(shí)間復(fù)雜度可能相同。 如：T(n)=n2+7n+6 與 T(n)=3n2+2n+2 它們的T(n) 不同，但時(shí)間復(fù)雜度相同，都為O(n2)。
計(jì)算時(shí)間復(fù)雜度的方法： 用常數(shù)1代替運(yùn)行時(shí)間中的所有加法常數(shù) T(n)=n2+7n+6 => T(n)=n2+7n+1修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng) T(n)=n2+7n+1 => T(n) = n2去除最高階項(xiàng)的系數(shù) T(n) = n2 => T(n) = n2 => O(n2)
常見的幾個(gè)時(shí)間復(fù)雜度
- 常數(shù)階 O(1)
- 對數(shù)階 O(log2n)
- 線性階 O(n)
- 線性對數(shù)階 O(nlog2n)
- 平方階 O(n^2)
- 立方階 O(n^3)
- k次方階 O(n^k)
- 指數(shù)階 O(2^n)
- 常見的算法時(shí)間復(fù)雜度由小到大依次為：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜ Ο(nk) ＜Ο(2n) ，隨著問題規(guī)模n的不斷增大，上述時(shí)間復(fù)雜度不斷增大，算法的執(zhí)行效率越低，從圖中可見，我們應(yīng)該盡可能避免使用指數(shù)階的算法
1.常數(shù)階O(1)
無論代碼執(zhí)行了多少行，只要是沒有循環(huán)等復(fù)雜結(jié)構(gòu)，那這個(gè)代碼的時(shí)間復(fù)雜度就都是O(1)：
上述代碼在執(zhí)行的時(shí)候，它消耗的時(shí)候并不隨著某個(gè)變量的增長而增長，那么無論這類代碼有多長，即使有幾萬幾十萬行，都可以用O(1)來表示它的時(shí)間復(fù)雜度。
2.對數(shù)階O(log2n)
設(shè)2的t次方等于n，看需要乘多少個(gè)2，i才能等于n，故時(shí)間復(fù)雜度為O(log2n)
3.線性階O(n)
這段代碼，for循環(huán)里面的代碼會執(zhí)行n遍，因此它消耗的時(shí)間是隨著n的變化而變化的，因此這類代碼都可以用O(n)來表示它的時(shí)間復(fù)雜度
4.線性對數(shù)階O(nlogN)
線性對數(shù)階O(nlogN) 其實(shí)非常容易理解，將時(shí)間復(fù)雜度為O(logn)的代碼循環(huán)N遍的話，那么它的時(shí)間復(fù)雜度就是 n * O(logN)，也就是O(nlogN)
5.平方階O(n2)
平方階O(n2) 就更容易理解了，如果把 O(n) 的代碼再嵌套循環(huán)一遍，它的時(shí)間復(fù)雜度就是 O(n2)，這段代碼其實(shí)就是嵌套了2層n循環(huán)，它的時(shí)間復(fù)雜度就是 O(n * n)，即 O(n2) 如果將其中一層循環(huán)的n改成m，那它的時(shí)間復(fù)雜度就變成了 O(m * n)
平均時(shí)間復(fù)雜度與最壞時(shí)間復(fù)雜度
- 平均時(shí)間復(fù)雜度是指所有可能的輸入實(shí)例均以等概率出現(xiàn)的情況下，該算法的運(yùn)行時(shí)間。
- 最壞情況下的時(shí)間復(fù)雜度稱最壞時(shí)間復(fù)雜度。一般討論的時(shí)間復(fù)雜度均是最壞情況下的時(shí)間復(fù)雜度。 這樣做的原因是：最壞情況下的時(shí)間復(fù)雜度是算法在任何輸入實(shí)例上運(yùn)行時(shí)間的界限，這就保證了算法的運(yùn)行時(shí)間不會比最壞情況更長。
- 平均時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度是否一致，和算法有關(guān)(如圖:)。
算法的空間復(fù)雜度
- 類似于時(shí)間復(fù)雜度的討論，一個(gè)算法的空間復(fù)雜度(Space Complexity)定義為該算法所耗費(fèi)的存儲空間，它也是問題規(guī)模n的函數(shù)。
- 空間復(fù)雜度(Space Complexity)是對一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲空間大小的量度。有的算法需要占用的臨時(shí)工作單元數(shù)與解決問題的規(guī)模n有關(guān)，它隨著n的增大而增大，當(dāng)n較大時(shí)，將占用較多的存儲單元，例如快速排序和歸并排序算法就屬于這種情況
- 在做算法分析時(shí)，主要討論的是時(shí)間復(fù)雜度。從用戶使用體驗(yàn)上看，更看重的程序執(zhí)行的速度。一些緩存產(chǎn)品(redis, memcache)和算法(基數(shù)排序)本質(zhì)就是用空間換時(shí)間.
二、多種排序方法
2.1冒泡排序和選擇排序
-
冒泡排序（Bubble Sorting）的基本思想是：通過對待排序序列從前向后（從下標(biāo)較小的元素開始）,依次比較相鄰元素的值，若發(fā)現(xiàn)逆序則交換，使值較大的元素逐漸從前移向后部，就象水底下的氣泡一樣逐漸向上冒。
代碼實(shí)現(xiàn)：public static void bubbleSort(int arr[]) { for(int i =0 ; i<arr.length-1 ; i++) { for(int j=0 ; j<arr.length-1-i ; j++) { if(arr[j]>arr[j+1]) { int temp = arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } } } -
選擇排序（Select Sorting）也屬于內(nèi)部排序法，是從欲排序的數(shù)據(jù)中，按指定的規(guī)則選出某一元素，再依規(guī)定交換位置后達(dá)到排序的目的。
代碼實(shí)現(xiàn)：public static void sort(Comparable[] data){ //數(shù)組長度 int len=data.length; for(int i=0; i<len; i++){ //記錄當(dāng)前位置 int position = i; //找出最小的數(shù)，并用position指向最小數(shù)的位置 for(int j=i+1; j<len; j++){ if( data[position].compareTo(data[j]) > 0 ) { position=j; }//endif }//endfor //交換最小數(shù)data[position]和第i位數(shù)的位置 Comparable temp=data[i]; data[i]=data[position]; data[position]=temp; }//endfor }
這兩個(gè)相信大家大學(xué)應(yīng)該都學(xué)過，這里就不過多贅述了。
2.2插入排序
- 插入排序（Insertion Sorting）的基本思想是：把n個(gè)待排序的元素看成為一個(gè)有序表和一個(gè)無序表，開始時(shí)有序表中只包含一個(gè)元素，無序表中包含有n-1個(gè)元素，排序過程中每次從無序表中取出第一個(gè)元素，把它的排序碼依次與有序表元素的排序碼進(jìn)行比較，將它插入到有序表中的適當(dāng)位置，使之成為新的有序表。
代碼：
public static void main(String[] args) {
int[] arr = {5,6,3,9,1,4};
for(int i = 1;i<arr.length;i++) {
int value = arr[i];
int index = i-1;
while(index>=0 && value < arr[index]) {
arr[index+1] = arr[index];
index--;
}
arr[index+1] = value;
}
for(int i = 0;i<arr.length;i++) {
System.out.println(arr[i]);
}
}
2.3希爾排序
我們看簡單的插入排序可能存在的問題.
數(shù)組 arr = {2,3,4,5,6,1} 這時(shí)需要插入的數(shù) 1(最小), 這樣的過程是：
{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ù)明顯增多，對效率有影響，所以我們引入了希爾排序，是插入排序的優(yōu)化版本。希爾排序是希爾（Donald Shell）于1959年提出的一種排序算法。希爾排序也是一種插入排序，它是簡單插入排序經(jīng)過改進(jìn)之后的一個(gè)更高效的版本，也稱為縮小增量排序。
希爾排序是把記錄按下標(biāo)的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰被分成一組，算法便終止
- 交換式代碼（非插入式改進(jìn)，性能低下）：
public static void main(String[] args) {
int[] arr = {8,9,1,7,2,3,5,4,6,0};
int temp = 0;
for(int gap = arr.length/2;gap>0;gap = gap/2) {
for(int i = gap;i<arr.length;i++) {
for(int j = i-gap;j>=0;j -= gap) {
if(arr[j]>arr[j+gap]) {
temp = arr[j];
arr[j] = arr[j+gap];
arr[j+gap] = temp;
}
}
}
System.out.println(Arrays.toString(arr));
}
}
- 移位式代碼（性能比交換式好，是插入式的優(yōu)化版本）：
public static void main(String[] args) {
int[] arr = {8,9,1,7,2,3,5,4,6,0};
//下面的代碼和插入法相似
for(int gap = arr.length/2;gap>0;gap = gap/2) {
for(int i = gap;i<arr.length;i++) {
int index = i - gap;
int temp = arr[i];
while(index>=0 && temp < arr[index]) {
arr[index+gap] = arr[index];
index -= gap;
}
arr[index+gap] = temp;
}
System.out.println(Arrays.toString(arr));
}
}
2.4快速排序法
- 快速排序（Quicksort）是對冒泡排序的一種改進(jìn)。基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列
基本思路：
(1)首先設(shè)定一個(gè)分界值，通過該分界值將數(shù)組分成左右兩部分。
(2)將大于或等于分界值的數(shù)據(jù)集中到數(shù)組右邊，小于分界值的數(shù)據(jù)集中到數(shù)組的左邊。此時(shí)，左邊部分中各元素都小于或等于分界值，而右邊部分中各元素都大于或等于分界值。 [2]
(3)然后，左邊和右邊的數(shù)據(jù)可以獨(dú)立排序。對于左側(cè)的數(shù)組數(shù)據(jù)，又可以取一個(gè)分界值，將該部分?jǐn)?shù)據(jù)分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側(cè)的數(shù)組數(shù)據(jù)也可以做類似處理。 [2]
(4)重復(fù)上述過程，可以看出，這是一個(gè)遞歸定義。通過遞歸將左側(cè)部分排好序后，再遞歸排好右側(cè)部分的順序。當(dāng)左、右兩個(gè)部分各數(shù)據(jù)排序完成后，整個(gè)數(shù)組的排序也就完成了。
-
代碼實(shí)現(xiàn)：
public static int[] qsort(int arr[],int left,int right) { int pivot = arr[left]; int l = left; int r = right; while (l<r) { while ((l<r)&&(arr[r]>pivot)) { r--; } while ((l<r)&&(arr[l]<pivot)) { l++; } if ((arr[l]==arr[r])&&(l<r)) { l++; } else { int temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; System.out.println(Arrays.toString(arr)); } } if (l-1>left) arr=qsort(arr,left,l-1); if (r+1<right) arr=qsort(arr,r+1,right); return (arr); } public static void main(String[] args) { int[] arr = {5,1,2,6,9,3,4,8,7}; int len = arr.length-1; arr=qsort(arr,0,len); System.out.println(Arrays.toString(arr)); }
2.5歸并排序法
- 歸并排序（MERGE-SORT）是利用歸并的思想實(shí)現(xiàn)的排序方法，該算法采用經(jīng)典的分治（divide-and-conquer）策略（分治法將問題分(divide)成一些小的問題然后遞歸求解，而治(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]，來看下實(shí)現(xiàn)步驟：
- 代碼實(shí)現(xiàn)：
public static void mergeSort(int[] arr, int left, int right,int[] temp) {
if(left < right) {
int mid = (left + right)/2;
mergeSort(arr,left,mid,temp);
mergeSort(arr,mid+1,right,temp);
merge(arr,left,mid,right,temp);
}
}
public static void merge(int arr[],int left,int mid,int right,int[] temp) {
int l = left;
int m = mid + 1;
int t = 0;
while(l <= mid && m <= right) {
if(arr[l] <= arr[m]) {
temp[t] = arr[l];
l++;
t++;
}else {
temp[t] = arr[m];
m++;
t++;
}
}
while(l <= mid) {
temp[t] = arr[l];
l++;
t++;
}
while(m <= right) {
temp[t] = arr[m];
m++;
t++;
}
t = 0;
int tempLeft = left;
while(tempLeft <= right) {
arr[tempLeft] = temp[t];
tempLeft++;
t++;
}
}
public static void main(String[] args) {
int[] arr = new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 10 };
int[] temp = new int[arr.length];
mergeSort(arr, 0, arr.length - 1,temp);
System.out.println(Arrays.toString(arr));
}
2.6基數(shù)排序法
- 基數(shù)排序是1887年赫爾曼·何樂禮發(fā)明的。它是這樣實(shí)現(xiàn)的：將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個(gè)位數(shù)分別比較。
- 基數(shù)排序（radix sort）屬于“分配式排序”（distribution sort），又稱“桶子法”（bucket sort）或bin sort，顧名思義，它是通過鍵值的各個(gè)位的值，將要排序的元素分配至某些“桶”中，達(dá)到排序的作用。
- 基數(shù)排序法是屬于穩(wěn)定性的排序，基數(shù)排序法的是效率高的穩(wěn)定性排序法，基數(shù)排序(Radix Sort)是桶排序的擴(kuò)展。
- 有負(fù)數(shù)的數(shù)組，我們不用基數(shù)排序來進(jìn)行排序, 如果要支持負(fù)數(shù)，參考: https://code.i-harness.com/zh-CN/q/e98fa9
-
代碼實(shí)現(xiàn)：
public static void main(String[] args) { int[] arr = {8,3,6,9,2,19,45500,5,7}; sort(arr); System.out.println(Arrays.toString(arr)); } public static void sort(int[] arr) { int max = arr[0]; for(int i = 1;i < arr.length;i++) { if(arr[i] > max) { max = arr[i]; } } int len = (max + " ").length(); int l = 1; int[][] temp = new int[10][arr.length]; int[] tempNum = new int[10]; int a = 1; while(l <= len) { for(int i = 0;i < arr.length;i++) { int n = arr[i]/a%10; temp[n][tempNum[n]] = arr[i]; tempNum[n]++; } l++; a = a * 10; int index = 0; for(int i = 0;i < tempNum.length;i++) { if(tempNum[i] != 0) { for(int j = 0;j < tempNum[i];j++) { arr[index++] = temp[i][j]; } tempNum[i] = 0; } } } }
三、各排序方法的比較
- 穩(wěn)定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
- 不穩(wěn)定：如果a原本在b的前面，而a=b，排序之后a可能會出現(xiàn)在b的后面；
- 內(nèi)排序：所有排序操作都在內(nèi)存中完成；
- 外排序：由于數(shù)據(jù)太大，因此把數(shù)據(jù)放在磁盤中，而排序通過磁盤和內(nèi)存的數(shù)據(jù)傳輸才能進(jìn)行；
- 時(shí)間復(fù)雜度： 一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間。
- 空間復(fù)雜度：運(yùn)行完一個(gè)程序所需內(nèi)存的大小。
- n: 數(shù)據(jù)規(guī)模
- k: “桶”的個(gè)數(shù)
- In-place: 不占用額外內(nèi)存
- Out-place: 占用額外內(nèi)存
