一、概述
不論是在面試中還是日常開發(fā)中胜臊，排序算法都是經(jīng)常會(huì)用/考到的勺卢。常用的排序算法共8種，可分為5類:插入排序象对、選擇排序黑忱、交換排序，歸并排序和基數(shù)排序勒魔。
常用排序算法
二甫煞、插入排序
插入排序中比較常見的是直接插入排序和希爾排序：
-
直接插入排序
- 基本思想：
在要排序的一組數(shù)中，假設(shè)前面(n-1) [n>=2] 個(gè)數(shù)已經(jīng)是排好順序的冠绢，現(xiàn)在要把第n個(gè)數(shù)插到前面的有序數(shù)中抚吠，使得這n個(gè)數(shù)也是排好順序的。如此反復(fù)循環(huán)弟胀，直到全部排好順序楷力。 - 性能/穩(wěn)定性
平均時(shí)間復(fù)雜度 空間復(fù)雜度 穩(wěn)定性 O(n*2) O(1) 穩(wěn)定 - 示例代碼：
public static void straightInsertionSort(int[] arr) { int length = arr.length; //單獨(dú)把數(shù)組長度拿出來 提高效率 int insertNum; //要插入的數(shù) for (int i = 1; i < length; i++) { //第一個(gè)數(shù)不用排序，所以下標(biāo)從1開始 insertNum = arr[i]; //取出要排序的這個(gè)數(shù)（后面移動(dòng)時(shí)會(huì)丟失這個(gè)數(shù)） int j = i - 1; //序列元素個(gè)數(shù)（已排好序的元素個(gè)數(shù)） while (j >= 0 && arr[j] > insertNum) { //從后往前循環(huán)孵户，將大于insertNum的數(shù)向后移動(dòng) arr[j + 1] = arr[j]; //元素向后移動(dòng) j--; } arr[j + 1] = insertNum; //找到位置萧朝，插入當(dāng)前元素。 } } - 基本思想：
-
希爾排序
針對(duì)直接插入排序的低效率問題夏哭，有人對(duì)其進(jìn)行了改進(jìn)與升級(jí)检柬，這就是現(xiàn)在的希爾排序。希爾排序竖配，也稱遞減增量排序算法何址，是插入排序的一種更高效的改進(jìn)版本里逆。希爾排序是非穩(wěn)定排序算法。- 基本思想
將數(shù)的個(gè)數(shù)設(shè)為n头朱，取奇數(shù)k=n/2运悲，將下標(biāo)差值為k的數(shù)分為一組，構(gòu)成有序序列项钮。再取k=k/2 班眯，將下標(biāo)差值為k的數(shù)分為一組，構(gòu)成有序序列烁巫。如此重復(fù)署隘，直到k=1執(zhí)行簡單插入排序。 - 性能/穩(wěn)定性
平均時(shí)間復(fù)雜度 空間復(fù)雜度 穩(wěn)定性 O(n*1.3) O(1) 不穩(wěn)定 - 示例代碼：
public static void shellSort(int[] arr) { int length = arr.length; while (length != 0) { length = length / 2; for (int i = 0; i < length; i++) { //分組 for (int j = i + length; j < arr.length; j += length) {//元素從第二個(gè)開始 int k = j - length; //k為有序序列最后一位的位數(shù) int temp = arr[j]; //要插入的元素 while (k >= 0 && arr[k] > temp) { //從后往前遍歷 arr[k + length] = arr[k]; k -= length; //向后移動(dòng)len位 } arr[k + length] = temp; } } } } - 基本思想
三亚隙、選擇排序
-
直接選擇排序
- 基本思想：
遍歷整個(gè)序列磁餐，將最小的數(shù)放在最前面。遍歷剩下的序列阿弃，將最小的數(shù)放在最前面诊霹。重復(fù)第二步，直到只剩下一個(gè)數(shù)渣淳。 - 性能/穩(wěn)定性
平均時(shí)間復(fù)雜度 空間復(fù)雜度 穩(wěn)定性 O(n*2) O(1) 不穩(wěn)定 - 示例代碼：
public static void simpleSelectSort(int[] arr) { int length = arr.length; for (int i = 0; i < length; i++) { //循環(huán)次數(shù) int value = arr[i]; //用于存儲(chǔ)最小值 int position = i; //用于存儲(chǔ)最小值下標(biāo) for (int j = i + 1; j < length; j++) { //找到最小值的位置 if (arr[j] < value) { value = arr[j]; position = j; } } arr[position] = arr[i]; //交換 arr[i] = value; } } - 基本思想：
-
堆排序
- 基本思想
利用大頂堆設(shè)計(jì)出的一種算法脾还，是對(duì)簡單選擇排序的優(yōu)化。 - 性能/穩(wěn)定性
平均時(shí)間復(fù)雜度 空間復(fù)雜度 穩(wěn)定性 O(nlog2n) O(1) 不穩(wěn)定 - 示例代碼：
public static void heapSort(int[] arr) { int length = arr.length; //循環(huán)建堆 for (int i = 0; i < length - 1; i++) { //建堆 buildMaxHeap(arr, length - 1 - i); //交換頂堆和最后一個(gè)元素 swap(arr, 0, length - 1 - i); } } //交換元素 private static void swap(int[] arr, int i, int j) { arr[i] = arr[i] + arr[j]; arr[j] = arr[i] - arr[j]; arr[i] -= arr[j]; } /** * 對(duì)arr數(shù)組從0到lastIndex建大頂堆 * <p> * 首先獲取lastIndex的父節(jié)點(diǎn)(k)并從其開始循環(huán) * 判斷k是否有子節(jié)點(diǎn) -> 取子節(jié)點(diǎn)較大值下標(biāo) -> 交換父子節(jié)點(diǎn) -> 循環(huán) * * @param arr arr * @param lastIndex 最后一個(gè)節(jié)點(diǎn) */ private static void buildMaxHeap(int[] arr, int lastIndex) { //從lastIndex處節(jié)點(diǎn)（最后一個(gè)節(jié)點(diǎn)）的父節(jié)點(diǎn)開始 //認(rèn)為存儲(chǔ)方式是按層次存儲(chǔ)的入愧，先左后右 for (int i = (lastIndex - 1) / 2; i >= 0; i--) { //k保存正在判斷的節(jié)點(diǎn) int k = i; //如果當(dāng)前k節(jié)點(diǎn)的子節(jié)點(diǎn)存在 while (k * 2 + 1 <= lastIndex) { //k節(jié)點(diǎn)的左子節(jié)點(diǎn)索引 int biggerIndex = 2 * k + 1; //如果biggerIndex小于lastIndex鄙漏，即biggerIndex+1代表的k節(jié)點(diǎn)的右子節(jié)點(diǎn)存在 if (biggerIndex < lastIndex) { //如果右子節(jié)點(diǎn)的值較大 if (arr[biggerIndex] < arr[biggerIndex + 1]) { //biggerIndex總是記錄較大子節(jié)點(diǎn)的索引 biggerIndex++; } } //如果k節(jié)點(diǎn)的值小于其較大的子節(jié)點(diǎn)的值 if (arr[k] < arr[biggerIndex]) { //交換他們 swap(arr, k, biggerIndex); //將biggerIndex賦予k，開始while循環(huán)的下一次循環(huán)棺蛛，重新保證k節(jié)點(diǎn)的值大于其左右子節(jié)點(diǎn)的值 k = biggerIndex; } else { break; } } } } - 基本思想
四怔蚌、交換排序
-
冒泡排序
- 基本思想
依次比較相鄰的兩個(gè)數(shù)，將小數(shù)放在前面旁赊，大數(shù)放在后面桦踊。即在第一趟：首先比較第1個(gè)和第2個(gè)數(shù)，將小數(shù)放前彤恶，大數(shù)放后钞钙。然后比較第2個(gè)數(shù)和第3個(gè)數(shù)，將小數(shù)放前声离，大數(shù)放后芒炼，如此繼續(xù)，直至比較最后兩個(gè)數(shù)术徊，將小數(shù)放前本刽，大數(shù)放后。重復(fù)第一趟步驟，直至全部排序完成子寓。 - 性能/穩(wěn)定性
平均時(shí)間復(fù)雜度 空間復(fù)雜度 穩(wěn)定性 O(n*2) O(1) 穩(wěn)定 - 示例代碼：
public static void bubbleSort(int[] arr) { int length = arr.length; for (int i = 0; i < length; i++) { //設(shè)置循環(huán)次數(shù) for (int j = 0; j < length - i - 1; j++) { if (arr[j] > arr[j + 1]) { //交換位置 arr[j] += arr[j + 1]; arr[j + 1] = arr[j] - arr[j + 1]; arr[j] -= arr[j + 1]; } } } } - 基本思想
-
快速排序
- 基本思想
通過一趟排序將要排序的數(shù)據(jù)分割成獨(dú)立的兩部分暗挑，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序斜友，整個(gè)排序過程可以遞歸整個(gè)數(shù)據(jù)變成有序序列炸裆。 - 性能/穩(wěn)定性
平均時(shí)間復(fù)雜度 空間復(fù)雜度 穩(wěn)定性 O(nlog2n) O(nlog2n) 不穩(wěn)定 - 示例代碼：
public static void quickSort(int[] arr, int start, int end) { if (start < end) { int baseNum = arr[start]; //選基準(zhǔn)值 int midNum; //記錄中間值 int i = start; int j = end; do { //從前往后找到大于baseNum的第一個(gè)數(shù)的索引（下標(biāo)） while (arr[i] < baseNum && i < end) { i++; } //從后往前找到小于baseNum的第一個(gè)數(shù)的索引（下標(biāo)） while (arr[j] > baseNum && j > start) { j--; } if (i <= j) { midNum = arr[i]; arr[i] = arr[j]; arr[j] = midNum; i++; j--; } } while (i <= j); //到這里時(shí)j < i了 if (start < j) { quickSort(arr, start, j); } if (i < end) { quickSort(arr, i, end); } } } - 基本思想
五、歸并排序
-
基本思想
建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用鲜屏。將已有序的子序列合并烹看，得到完全有序的序列；即先使每個(gè)子序列有序洛史，再使子序列段間有序惯殊。- 性能/穩(wěn)定性
平均時(shí)間復(fù)雜度 空間復(fù)雜度 穩(wěn)定性 O(nlog2n) O(1) 穩(wěn)定 示例代碼：
public static void mergeSort(int[] arr, int start, int end) {
int mid = (start + end) / 2;
if (start < end) {
mergeSort(arr, start, mid);
mergeSort(arr, mid + 1, end);
//左右歸并
merge(arr, start, mid, end);
}
}
//進(jìn)行歸并操作
private static void merge(int[] arr, int start, int mid, int end) {
//開辟新空間用于存儲(chǔ)
int[] temp = new int[end - start + 1];
int i = start;
int j = mid + 1;
int k = 0;
//把較小的數(shù)先移到新數(shù)組中
while (i <= mid && j <= end) {
if (arr[i] < arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
//把左邊剩余的數(shù)移入數(shù)組
while (i <= mid) {
temp[k++] = arr[i++];
}
//把右邊剩余的數(shù)移入數(shù)組
while (j <= end) {
temp[k++] = arr[j++];
}
//把新數(shù)組中的數(shù)覆蓋到arr數(shù)組
if (temp.length >= 0) System.arraycopy(temp, 0, arr, start, temp.length);
}
六、基數(shù)排序（桶子法）
基本思想
將整數(shù)按位數(shù)切割成不同的數(shù)字也殖，然后按每個(gè)位數(shù)分別比較土思。-
性能/穩(wěn)定性
平均時(shí)間復(fù)雜度 空間復(fù)雜度 穩(wěn)定性 O(d(r+n)) O(rd+n) 穩(wěn)定 示例代碼
public static void radixSort(int[] arr) {
int max = findMax(arr, 0, arr.length - 1);
//需要遍歷的次數(shù)由數(shù)組最大值的位數(shù)來決定
for (int i = 1; max / i > 0; i = i * 10) {
int[][] buckets = new int[arr.length][10];
//獲取每一位數(shù)字（個(gè)、十忆嗜、百己儒、千位...分配到桶子里）
for (int j = 0; j < arr.length; j++) {
int num = (arr[j] / i) % 10;
//放入桶子里
buckets[j][num] = arr[j];
}
//回收桶子里的元素
int k = 0;
//有10個(gè)桶子
for (int j = 0; j < 10; j++) {
//對(duì)每個(gè)桶子里的元素進(jìn)行回收
for (int l = 0; l < arr.length; l++) {
//如果桶子里面有元素就回收（數(shù)據(jù)初始化會(huì)為0）
if (buckets[l][j] != 0) {
arr[k++] = buckets[l][j];
}
}
}
}
}
//找到數(shù)組中最大值
private static int findMax(int[] arrays, int start, int end) {
//如果該數(shù)組只有一個(gè)數(shù)，那么最大的就是該數(shù)組第一個(gè)值了
if (start == end) {
return arrays[start];
} else {
int a = arrays[start];
int b = findMax(arrays, start + 1, end);//找出整體的最大值
if (a > b) {
return a;
} else {
return b;
}
}
}
七捆毫、總結(jié)
