微信公眾號：一起學習大數(shù)據(jù)呀
關(guān)注可學習更多奇怪的知識！
前言
本文收集整理常見的十大排序算法，配套 Java 代碼和視頻短視頻教程。幫助小伙伴們更快的理解和掌握。
不管你是為了應(yīng)付考試，還是面試用，本文都可以幫到你，降低學習門檻，作者水平有限，難免遺漏錯誤，歡迎讀者們留言指正。
算法目錄
- 冒泡排序
- 選擇排序
- 插入排序
- 快速排序
- 希爾排序
- 歸并排序
- 堆排序
- 計數(shù)排序
- 桶排序
- 基數(shù)排序
1、冒泡排序
基本思想
每次比較兩個相鄰的元素，若順序（從小到大或從大到?。板e誤”就交換位置。
視頻講解
代碼實現(xiàn)
public static void bubbleSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
// 設(shè)定一個標記，若為true，則表示此次循環(huán)沒有進行交換，也就是待排序列已經(jīng)有序，排序已經(jīng)完成。
boolean flag = true;
for (int j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j + 1]) { //前面的數(shù)字大于后面的數(shù)字就交換
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flag = false;
}
}
if (flag) { //沒有數(shù)據(jù)交換，數(shù)組已經(jīng)有序，退出排序
break;
}
}
}
image.gif
2、選擇排序
基本思想
每一趟從待排序的記錄中選出最大（?。┑脑?，順序放在已排好序的序列最后，直到全部記錄排序完畢。
視頻講解
代碼實現(xiàn)
//1 找到數(shù)組最大的數(shù)字,并且返回下標
public static int findMaxPos(int[] arr , int n){
int max = arr[0];
int pos = 0;
for (int i = 0; i < n; i++){
if (max < arr[i]){
max = arr[i];
pos = i;
}
}
return pos;
}
//2 讓最大值與最后一個元素交換
public static void selectionSort(int[] arr, int n){
while(n > 1) { // 3 不斷循環(huán) 1 和 2 步驟
int pos = findMaxPos(arr, n);
int temp = 0;
temp = arr[n - 1];
arr[n - 1] = arr[pos];
arr[pos] = temp;
n-- ;
}
}
image.gif
3、插入排序
基本思想
將數(shù)組分為“已排序區(qū)間”和“未排序區(qū)間”。核心思想是提取“未排序區(qū)間”中的元素，在已排序區(qū)間中找到合適的插入位置將其插入，并保證已排序區(qū)間數(shù)據(jù)一直有序。重復(fù)該過程，直到排序區(qū)間中元素為空。
視頻講解
代碼實現(xiàn)
//1 選擇已排序區(qū)間的后一個元宵插入
public void insert(int[] arr, int n){
int key = arr[n];
int i = n;
while (arr[i - 1] > key){ //若前面的元素 > 后面元素
arr[i] = arr[i -1]; // 前面元素抄寫到后面元素位置
i--;
if (i == 0){//防止數(shù)組越界
break;
}
}
arr[i] = key; // 把要插入的元素歸位
}
// 2 多趟插入
public void insertSort(int[] arr, int n){
if (n <= 1){
return ;
}
for (int i = 1; i < n; i++){ // 從第二個元素開始，第一個看成有序區(qū)域就好
insert(arr, i);
}
}
image.gif
4、快速排序
基本思想
基本思想:在數(shù)組中找到一個基準數(shù),一般來說選第一個,然后加兩個哨兵, i 和 j ,一個頭一個尾.
i 從左到右掃描遇到大于 基準數(shù) 的數(shù)字停下, j 從右到左掃描,遇到小于 基準數(shù) 的停下.
然后 i 坐標的數(shù)與 j 坐標的數(shù)交換.
視頻講解
代碼實現(xiàn)
static void qucikSort(int left, int right) {
if (left > right){
return;
}
int i = left;
int j = right;
int povit = arr[left]; // 基準數(shù)
int temp;
while (i != j) {
while (arr[j] >= povit && i < j) {
j--;
}
while (arr[i] <= povit && i < j) {
i++;
}
if (i < j) {
temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
//基準數(shù)歸位
arr[left] = arr[i];
arr[i] = povit;
//遞歸
qucikSort(left, i - 1);
qucikSort(i + 1, right);
return;
}
image.gif
- 基準數(shù)優(yōu)化
隨機取基準數(shù)
三位數(shù)取中: 選取數(shù)組開頭，中間和結(jié)尾的元素，通過比較，選擇中間的值作為快排的基準。 - 序列長度達到一定大小時，使用插入排序
- 尾遞歸優(yōu)化
- 聚集元素
5、希爾排序
基本思想
希爾排序是插入排序的一種改進版，通過比較相距一定距離（增量）的元素工作（交換；各趟比較所用的距離隨著算法減小而減小，當增量減至1時，整個文件恰被分成一組，算法便終止。
視頻講解
代碼實現(xiàn)
public class ShellSort {
public static void main(String[] args) {
int[] arr = {1, 3, 7, 2, 8, 6, 4, 9};
shellSort(arr);
System.out.println(Arrays.toString(arr));
}
/**
* 希爾排序 針對有序序列在插入時采用移動法。
*
* @param arr
*/
static void shellSort(int[] arr) {
//增量 gap，并逐步縮小增量
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
//從第 gap 個元素，逐個對其所在組進行直接插入排序操作
for (int i = gap; i < arr.length; i++) {
int j = i;
int temp = arr[j];
//j - gap 同組相隔的元素沒數(shù)組越界；
//arr[j - gap] > temp 前面的元素 > 后面的元素
while (j - gap >= 0 && arr[j - gap] > temp) {
//把前面元素抄寫到后面的位置
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}
}
image.gif
6、歸并排序
基本思想
該算法采用經(jīng)典的分治（divide-and-conquer）策略，它將問題分(divide)成一些小的問題然后遞歸求解，而治(conquer)的階段則將分的階段得到的各答案"修補"在一起，即分而治之。
視頻講解
代碼實現(xiàn)
public class MergeSort {
public static void main(String[] args) {
int[] a = {6, 8, 10, 9, 4, 5, 2, 7};
int L = 0;
int R = a.length - 1;
mergSort(a, L, R);
System.out.println(Arrays.toString(a));
}
static void mergSort(int[] arr, int L, int R) {
// 遞歸出口
if (L == R) {
return;
} else {
int M = (L + R) / 2;
mergSort(arr, L, M);
mergSort(arr, M + 1, R);
merge(arr, L, M + 1, R);
}
}
static void merge(int[] arr, int L, int M, int R) {
int left_size = M - L;
int right_size = R - M + 1;
int[] L_arr = new int[left_size];
int[] R_arr = new int[right_size];
// 1 填充左邊的數(shù)組
for (int i = L; i < M; i++) {
L_arr[i - L] = arr[i];
}
// 2 右邊填充數(shù)組
for (int i = M; i <= R; i++) {
R_arr[i - M] = arr[i];
}
// 3 合并
int i = 0, j = 0, k = L;
while (i < left_size && j < right_size) {
if (L_arr[i] > R_arr[j]) {
arr[k] = R_arr[j];
k++;
j++;
} else {
arr[k] = L_arr[i];
i++;
k++;
}
}
// 4 若右邊數(shù)組已空,把剩余左邊數(shù)組補上
while (i < left_size) {
arr[k] = L_arr[i];
i++;
k++;
}
// 5 若左邊數(shù)組已空,同上
while (j < right_size) {
arr[k] = R_arr[j];
k++;
j++;
}
}
}
image.gif
7、堆排序
基本思想
1）將待排序序列構(gòu)造成一個大頂堆，此時，整個序列的最大值就是堆頂?shù)母?jié)點。
2）將其與末尾元素進行交換，此時末尾就為最大值。
3）將剩余n-1個元素重新構(gòu)造成一個堆，這樣會得到n個元素的次小值。如此反復(fù)執(zhí)行，便能得到一個有序序列了。
視頻講解
代碼實現(xiàn)
public class HeapSort {
public static void main(String[] args) {
int[] arr = {2,5,3,1,10,4};
heapSort(arr,arr.length);
for (int i : arr){
System.out.println(i + " ");
}
}
/***
* 交換函數(shù)
* @param arr
* @param i
* @param j
*/
static void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/***
* 構(gòu)建大頂堆 (父節(jié)點大于子節(jié)點)
* @param tree 數(shù)組(樹)
* @param n 數(shù)組長度
* @param i 父節(jié)點
*/
static void heapify(int tree[], int n, int i){
// 遞歸出口
if (i >= n){
return;
}
//左孩子節(jié)點
int c1 = 2*i + 1;
//右孩子節(jié)點
int c2 = 2*i + 2;
// 假設(shè) i 為最大值
int max = i;
// c1 < n 保證 c1 不出界
if (c1 < n && tree[c1] > tree[max]){
max = c1;
}
if (c2 < n && tree[c2] > tree[max]){
max = c2;
}
if (max != i){
swap(tree, max, i);
heapify(tree, n, max);
}
}
/***
* 自下而上構(gòu)建堆
* @param tree 數(shù)組
* @param n 數(shù)組長度
*/
static void buidHeap(int[] tree, int n){
// 最后一個葉子節(jié)點
int last_node = n - 1;
// 對應(yīng)的父節(jié)點
int parent = (last_node - 1)/2;
for (int i = parent; i >= 0 ; i--){
heapify(tree, n, i);
}
}
/***
* 堆排序
* @param tree
* @param n
*/
static void heapSort(int[] tree, int n){
// 1) 建一個堆
buidHeap(tree, n);
// 2) 從最后一個節(jié)點出發(fā)
for (int i = n - 1; i >= 0; i--){
// 3) 先交換一下根節(jié)點和最后一個節(jié)點
// i 表示最后一個節(jié)點
// 0 表示根節(jié)點
swap(tree, i, 0);
heapify(tree, i, 0);
}
}
}
image.gif
8、計數(shù)排序
基本思想
計數(shù)排序不是基于比較的排序算法，其核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲在額外開辟的數(shù)組空間中。 作為一種線性時間復(fù)雜度的排序，計數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。
注意：適合量大且范圍小的數(shù)據(jù)
視頻講解
代碼實現(xiàn)
public class CountSort {
public static void main(String[] args) {
int[] arr = {2 , 4, 2, 3, 7, 1, 1, 0, 0, 5, 6, 3, 7, 8, 9 };
System.out.println(Arrays.toString(countSort(arr)));
}
/***
* 計數(shù)排序
* @param arr
* @return
*/
static int[] countSort(int[] arr) {
//目標數(shù)組
int[] result = new int[arr.length];
//計數(shù)數(shù)組
int[] count = new int[10];
//對原數(shù)組記錄各元素出現(xiàn)的次數(shù)
for (int i = 0; i < arr.length; i++) {
count[arr[i]]++;
}
System.out.println(Arrays.toString(count));
//累加數(shù)組 看視頻吧，我解釋不了
for (int i = 1; i < count.length; i++) {
count[i] = count[i] + count[i - 1];
}
System.out.println(Arrays.toString(count));
//有點像眾神歸位
for (int i = arr.length - 1; i >= 0; i--) {
result[--count[arr[i]]] = arr[i];
}
return result;
}
}
image.gif
9、桶排序
基本思想
1）將要排序的數(shù)據(jù)分到幾個有序的桶里，每個桶里的數(shù)據(jù)再單獨進行快速排序。
2）桶內(nèi)排完序之后，再把每個桶里的數(shù)據(jù)按照順序依次取出，組成的序列就是有序的了。
視頻講解
代碼實現(xiàn)
static void bucketSort(int[] arr) {
//找到數(shù)組的最大值和最小值，用來計算映射函數(shù)
int min = arr[0];
int max = arr[0];
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
}
//計算出桶的數(shù)量
int bucketNum = (max - min) / arr.length + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
for (int i = 0; i < bucketNum; i++) {
bucketArr.add(new ArrayList<Integer>());
}
//將屬于同一個桶的元素放入對應(yīng)的桶
for (int i = 0; i < arr.length; i++) {
int num = (arr[i] - min) / (arr.length);
bucketArr.get(num).add(arr[i]);
}
//對每個桶進行排序
for (int i = 0; i < bucketArr.size(); i++) {
Collections.sort(bucketArr.get(i));
}
System.out.println(bucketArr.toString());
}
image.gif
10、基數(shù)排序
基本思想
桶思想的一種，非比較排序，多關(guān)鍵字排序。
對數(shù)據(jù)的每一位（個位，十位，百位）進行桶排序或計數(shù)排序，對每位排序后結(jié)果就是有序的。
視頻講解
**代碼實現(xiàn)
public class RadixSort {
public static void main(String[] args) {
int[] arr = {421, 240, 115, 532, 305, 430, 324};
//1 先求最高位數(shù)
int maxDigit = getMaxDigit(arr);
System.out.println(Arrays.toString(radixSort(arr, maxDigit)));
}
/**
* 獲取最高位數(shù)
*/
private static int getMaxDigit(int[] arr) {
int maxValue = getMaxValue(arr);
return getNumLenght(maxValue);
}
private static int getMaxValue(int[] arr) {
int maxValue = arr[0];
for (int value : arr) {
if (maxValue < value) {
maxValue = value;
}
}
return maxValue;
}
static int getNumLenght(long num) {
if (num == 0) {
return 1;
}
int lenght = 0;
for (long temp = num; temp != 0; temp /= 10) {
lenght++;
}
return lenght;
}
static int[] radixSort(int[] arr, int maxDigit) {
int[] result = new int[arr.length];
int[] count = new int[10];
// maxDigit 是數(shù)字中最大的位數(shù)
for (int i = 0; i < maxDigit; i++) {
//求余數(shù)，如個位，十位
int division = (int) Math.pow(10, i);
System.out.println(division);
for (int j = 0; j < arr.length; j++) {
int num = arr[j] / division % 10;
System.out.println(num + " ");
count[num]++;
}
//跟計數(shù)排序一樣，先做累加數(shù)組，再復(fù)制（我也有點懵）
for (int m = 1; m < count.length; m++) {
count[m] = count[m] + count[m - 1];
}
for (int n = arr.length - 1; n >= 0; n--) {
int num = arr[n] / division % 10;
result[--count[num]] = arr[n];
}
System.arraycopy(result, 0, arr, 0, arr.length);
Arrays.fill(count, 0);
}
return result;
}
}
image.gif
參考文獻
1: 十大經(jīng)典排序算法（動圖演示）
2: 圖解排序算法(四)之歸并排序
3:【干貨】史上最好的排序和數(shù)據(jù)結(jié)構(gòu)入門
