上篇博客介紹了五種排序演算法，分別為：冒泡排序，選擇排序，插入排序，希爾排序，歸并排序，博客地址如下：
影片詳解十大經典排序演算法【Java版實作】(上)
本篇博客針對剩下的五種排序演算法展開介紹：快速排序，堆排序，計數排序，桶排序，基數排序，
1. 快速排序
演算法介紹
通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄均比另一部分記錄小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序的效果，
影片演示
步驟描述
-
從數列中挑出一個元素，稱為 “基準”；
-
重新排序數列，比基準值小的元素放在前面，比基準值大的元素放在后面；
-
遞回地把小于基準值元素的子數列和大于基準值元素的子數列進行排序，直到不能遞回；
代碼實作
public void quickSort(int[] a, int start, int end) {
if (start < end) {
//選基準值
int baseNum = a[start];
//記錄中間值
int midNum;
int i = start;
int j = end;
do {
while ((a[i] < baseNum) && i < end) {
i++;
}
while ((a[j] > baseNum) && j > start) {
j--;
}
if (i <= j) {
midNum = a[i];
a[i] = a[j];
a[j] = midNum;
i++;
j--;
}
} while (i <= j);
if (start < j) {
quickSort(a, start, j);
}
if (i < end) {
quickSort(a, i, end);
}
}
}2. 堆排序
演算法介紹
堆排序是利用堆的資料結構進行排序的方法，可以將堆看做是一個完全二叉樹，
堆排序中有兩個概念需要明確：
大頂堆：每個結點的值都大于等于其左右孩子結點的值，稱為大頂堆；
小頂堆：每個結點的值都小于等于其左右孩子結點的值，稱為小頂堆；
影片演示
步驟描述
-
將待排序列構造成一個大頂堆(或小頂堆)；
-
整個序列的最大值(或最小值)就是堆頂的根結點，將根節點的值和堆陣列的末尾元素交換；
-
將剩余的 n-1 個序列重新構造成一個堆；
-
反復執行，最終得到一個有序序列；
代碼實作
/**
* 調整堆
*
* @param array
* @param index
* @param length
*/
public static void heapAdjust(int[] array, int index, int length) {
//保存當前結點的下標
int max = index;
//當前節點左子節點的下標
int lchild = 2 * index;
//當前節點右子節點的下標
int rchild = 2 * index + 1;
if (length > lchild && array[max] < array[lchild]) {
max = lchild;
}
if (length > rchild && array[max] < array[rchild]) {
max = rchild;
}
//若此節點比其左右孩子的值小，就將其和最大值交換，并調整堆
if (max != index) {
int temp = array[index];
array[index] = array[max];
array[max] = temp;
heapAdjust(array, max, length);
}
}
/**
* 堆排序
*
* @param array
* @return
*/
public static int[] heapSort(int[] array) {
int len = array.length;
//初始化堆，構造一個最大堆
for (int i = (len / 2 - 1); i >= 0; i--) {
heapAdjust(array, i, len);
}
//將堆頂的元素和最后一個元素交換，并重新調整堆
for (int i = len - 1; i > 0; i--) {
int temp = array[i];
array[i] = array[0];
array[0] = temp;
heapAdjust(array, 0, i);
}
return array;
}3. 計數排序
演算法介紹
計數排序是一種穩定的排序演算法，只能對整數進行排序，
它使用一個額外的陣列，其中第 i 個元素是待排序陣列 A 中值等于 i 的元素的個數，
影片演示
步驟描述
-
掃描整個序列 A，獲取最小值 min 和最大值 max；
-
開辟一塊新的空間創建新陣列 B，長度為 (max - min + 1)；
-
陣列 B 中 i 的元素記錄的值是 A 中某元素出現的次數；
-
遍歷陣列 B，輸出相應元素以及對應的個數；
代碼實作
/**
* 計數排序
*
* @param array
* @return
*/
public static int[] countingSort(int[] array) {
if (array.length == 0) {
return array;
}
int bias, min = array[0], max = array[0];
//找出最小值和最大值
for (int i = 0; i < array.length; i++) {
if (array[i] < min) {
min = array[i];
}
if (array[i] > max) {
max = array[i];
}
}
//偏差
bias = 0 - min;
//新開辟一個陣列
int[] bucket = new int[max - min + 1];
//資料初始化為0
Arrays.fill(bucket, 0);
for (int i = 0; i < array.length; i++) {
bucket[array[i] + bias] += 1;
}
int index = 0;
for (int i = 0; i < bucket.length; i++) {
int len = bucket[i];
while (len > 0) {
array[index++] = i - bias;
len--;
}
}
return array;
}4. 桶排序
演算法介紹
桶排序是計數排序的升級版，它利用函式的映射關系，假設輸入資料服從均勻分布，將資料分到有限數量的桶里，每個桶再分別進行排序，最后拼接為完整的排序資料，
影片演示
步驟描述
-
設定固定數量的空桶；
-
把資料放到對應的桶中；
-
對每個不為空的桶中資料進行排序；
-
拼接不為空的桶中資料，得到結果；
代碼實作
/**
* 桶排序
*
* @param array
* @param bucketSize 桶中可以放多少種元素
* @return
*/
public static ArrayList<Integer> BucketSort(ArrayList<Integer> array, int bucketSize){
if (array == null || array.size() < 2)
return array;
int max = array.get(0), min = array.get(0);
// 找到最大值最小值
for (int i = 0; i < array.size(); i++) {
if (array.get(i) > max)
max = array.get(i);
if (array.get(i) < min)
min = array.get(i);
}
int bucketCount = (max - min) / bucketSize + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);
ArrayList<Integer> resultArr = new ArrayList<>();
//構造桶
for (int i = 0; i < bucketCount; i++) {
bucketArr.add(new ArrayList<Integer>());
}
//往桶里塞元素
for (int i = 0; i < array.size(); i++) {
bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i));
}
for (int i = 0; i < bucketCount; i++) {
if (bucketSize == 1) {
for (int j = 0; j < bucketArr.get(i).size(); j++)
resultArr.add(bucketArr.get(i).get(j));
} else {
if (bucketCount == 1)
bucketSize--;
ArrayList<Integer> temp = BucketSort(bucketArr.get(i), bucketSize);
for (int j = 0; j < temp.size(); j++)
resultArr.add(temp.get(j));
}
}
return resultArr;
}5. 基數排序
演算法介紹
基數排序是非比較的排序演算法，對每一位進行排序，從最低位開始，
首先對低位排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位，
影片演示
步驟描述
-
將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零；
-
從最低位開始，依次進行排序；
-
一直到最高位排序完成，即可得到一個有序序列；
代碼實作
/**
* 基數排序
*
* @param array
* @return
*/
public static int[] RadixSort(int[] array) {
if (array == null || array.length < 2)
return array;
// 1.先算出最大數的位數；
int max = array[0];
for (int i = 1; i < array.length; i++) {
max = Math.max(max, array[i]);
}
int maxDigit = 0;
while (max != 0) {
max /= 10;
maxDigit++;
}
int mod = 10, div = 1;
ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < 10; i++) {
bucketList.add(new ArrayList<Integer>());
}
for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
for (int j = 0; j < array.length; j++) {
int num = (array[j] % mod) / div;
bucketList.get(num).add(array[j]);
}
int index = 0;
for (int j = 0; j < bucketList.size(); j++) {
for (int k = 0; k < bucketList.get(j).size(); k++) {
array[index++] = bucketList.get(j).get(k);
}
bucketList.get(j).clear();
}
}
return array;
}介紹完十種排序演算法，最后來總結下它們的特點：
本篇博客參考了以下內容，深表感謝：
十大經典排序演算法影片與決議，看我就夠了！（配代碼完全版） - 五分鐘學演算法 - 博客園
Java常用的八種排序演算法與代碼實作 - 我心自在 - 博客園
十大經典排序演算法總結（Java實作+影片）_meibenxiang的博客-CSDN博客
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/327993.html
標籤：其他