目錄
- 排序演算法
- 排序演算法概念
- 時間復雜度
- 空間復雜度
- 排序演算法種類
- 冒泡排序
- 代碼實作
- 選擇排序
- 代碼實作
- 插入排序
- 代碼實作
- 希爾排序
- 代碼實作
- 快速排序
- 代碼實作
- 歸并排序
- 代碼實作
- 基數排序(桶排序)
- 代碼實作
- 堆排序
- 代碼實作
- 冒泡排序
- 排序演算法總結
- 排序演算法概念
排序演算法
排序演算法概念
# 1.排序演算法
- 參考檔案:https://baike.baidu.com/item/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/5399605?fr=aladdin
- 排序演算法，就是如何使得記錄按照要求排列的方法，
# 2.排序演算法分類
- 內部排序:指將需要處理的所有資料都加載到內部存盤器中進行排序，
- 外部排序:資料量過大，無法全部加載到記憶體中，需要借助外部存盤進行排序，
# 3.常用排序演算法
時間復雜度
# 4.時間復雜度
- 參考檔案:https://baike.baidu.com/item/%E7%AE%97%E6%B3%95%E5%A4%8D%E6%9D%82%E5%BA%A6/210801?fr=aladdin
- 即從序列的初始狀態到經過排序演算法的變換移位等操作變到最終排序好的結果狀態的程序所花費的時間度量，
- 時間頻度:一個演算法中的陳述句執行次數稱為陳述句頻度或時間頻度，記為T(n)，
- 時間復雜度分類:
(1).事后統計:事后統計方法更多的依賴于計算機的硬體、軟體等環境因素，有時容易掩蓋演算法本身的優劣，因此人們常常采用事前分析估算的方法，
(2).事前估算:在計算機程式編制前，依據統計方法對演算法進行估算，
# 5.常見時間復雜度
- 常數階O(1)
- 對數階O(log2n)
- 線性階O(n)
- 線性對數階O(nlog2n)
- 平方階O(n^2)
- 立方階O(n^3)
- k次方階O(n^k)
- 指數階O(2^n)
- 演算法時間復雜度由小到大依次為：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜ Ο(nk) ＜Ο(2n) ，隨著問題規模n的不斷增大，上述時間復雜度不斷增大，演算法的執行效率越低，
# 6.平均時間復雜度
- 平均時間復雜度是指所有可能的輸入實體均以等概率出現的情況下，該演算法的運行時間，
# 7.最壞時間復雜度
- 最壞情況下的時間復雜度稱最壞時間復雜度，一般討論的時間復雜度均是最壞情況下的時間復雜度， 這樣做的原因是：最壞情況下的時間復雜度是演算法在任何輸入實體上運行時間的界限，這就保證了演算法的運行時間不會比最壞情況更長，
# 8.平均時間復雜度與最壞時間復雜度
- 平均時間復雜度和最壞時間復雜度是否一致，和演算法有關，
空間復雜度
# 1.空間復雜度
- 一個演算法的空間復雜度(Space Complexity)定義為該演算法所耗費的存盤空間，它也是問題規模n的函式，
- 空間復雜度(Space Complexity)是對一個演算法在運行程序中臨時占用存盤空間大小的量度，有的演算法需要占用的臨時作業單元數與解決問題的規模n有關，它隨著n的增大而增大，當n較大時，將占用較多的存盤單元，
- 用空間換時間;或者用時間換空間，需要在特定的情況下區分，如單片機則空間記憶體不大,則用時間換空間，而WEB服務器一般記憶體較大,故使用空間換時間，
排序演算法種類
冒泡排序
# 1.冒泡排序
- 冒泡排序（Bubble Sorting）的基本思想是：通過對待排序序列從前向后（從下標較小的元素開始）,依次比較相鄰元素的值，若發現逆序則交換，使值較大的元素逐漸從前移向后部，就象水底下的氣泡一樣逐漸向上冒，
代碼實作
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class BubbleSort {
public static void main(String[] args) {
// int[] arr = {3, -9, -1, 10, -2};
// System.out.println("排序前");
// System.out.println(Arrays.toString(arr));
// bubbleSort(arr);
// System.out.println("排序后");
// System.out.println(Arrays.toString(arr));
/**
* 測驗冒泡排序的速度O(n^2) 設定80000個資料
* 創建80000個隨機陣列
*/
int[] arr = new int[80000];
for (int i = 0; i < 80000; i++) {
arr[i] = (int) (Math.random() * 800000);//生成[0,800000)之間的數
}
Date startStr = new Date();
SimpleDateFormat dateFormatStartStr = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String dateStartStr = dateFormatStartStr.format(startStr);
System.out.println("排序前的時間: " + dateStartStr);
bubbleSort(arr);
Date endStr = new Date();
String dateEndStr = dateFormatStartStr.format(endStr);
System.out.println("排序后的時間: " + dateEndStr);
// for (int i = 0; i < arr.length; i++) {
// for (int j = 0; j < arr.length; j++) {
// if (arr[i] < arr[j]) {
// int temp = arr[i];
// arr[i] = arr[j];
// arr[j] = temp;
// }
// }
// }
}
//冒泡排序封裝
public static void bubbleSort(int[] arr) {
//冒泡排序 時間復雜度(n^2)
//標識變數 標識是否進行過交換
boolean flag = false;
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]) {
flag = true;
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
// System.out.println("第" + (i + 1) + "趟排序后的陣列");
// System.out.println(Arrays.toString(arr));
if (!flag) { //在一趟排序中 一次交換都沒有發生
break;
} else {
//充值flag 進行下次判斷
flag = false;
}
}
}
}
選擇排序
# 1.選擇排序
- 選擇排序演算法的基本思路是為每一個位置選擇當前最小的元素，
- 選擇排序的基本思想是，基于直接選擇排序和堆排序這兩種基本的簡單排序方法，
- 選擇排序不是穩定的排序演算法，它在計算程序中會破壞穩定性，
# 2.選擇排序的思路
(1).首先從第1個位置開始對全部元素進行選擇，選出全部元素中最小的給該位置，
(2).再對第2個位置進行選擇，在剩余元素中選擇最小的給該位置即可；
(3).以此類推，重復進行“最小元素”的選擇，直至完成第(n-1)個位置的元素選擇，則第n個位置就只剩唯一的最大元素，此時不需再進行選擇，使用這種排序時，要注意其中一個不同于冒泡法的細節，
代碼實作
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class SelectSort {
public static void main(String[] args) {
// int[] arr = {101,34,119,1,-1,90,123};
// System.out.println("排序前:"+ Arrays.toString(arr));
// selectSort(arr);
// System.out.println("排序后:"+ Arrays.toString(arr));
/**
* 測驗選擇排序的速度O(n^2) 設定80000個資料
* 創建80000個隨機陣列
*/
int[] arr = new int[80000];
for (int i = 0; i < 80000; i++) {
arr[i] = (int) (Math.random() * 800000);//生成[0,800000)之間的數
}
Date startStr = new Date();
SimpleDateFormat dateFormatStartStr = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String dateStartStr = dateFormatStartStr.format(startStr);
System.out.println("排序前的時間: " + dateStartStr);
selectSort(arr);
Date endStr = new Date();
String dateEndStr = dateFormatStartStr.format(endStr);
System.out.println("排序后的時間: " + dateEndStr);
}
//選擇排序
public static void selectSort(int[] arr) {
/**
* 第一輪:101 34 119 1
* 第一輪排序: 1,34,119,101
* 第二輪排序: 1,34,119,101
* 第三輪排序: 1,34,101,119
* 時間復雜度:O(n^2)
*/
//使用逐步推導解釋選擇排序思路
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]; //重置min
minIndex = j; //重置minIndex
}
}
//將最小值 放在arr[0] 即交換
if (minIndex != i) {
arr[minIndex] = arr[i];
arr[i] = min;
}
// System.out.println("第" + (i + 1) + "輪后");
// System.out.println(Arrays.toString(arr));
}
}
}
插入排序
# 1.插入排序
- 插入式排序屬于內部排序法，是對于欲排序的元素以插入的方式找尋該元素的適當位置，以達到排序的目的，
# 2.插入排序思想
- 插入排序（Insertion Sorting）的基本思想是：把n個待排序的元素看成為一個有序表和一個無序表，開始時有序表中只包含一個元素，無序表中包含有n-1個元素，排序程序中每次從無序表中取出第一個元素，把它的排序碼依次與有序表元素的排序碼進行比較，將它插入到有序表中的適當位置，使之成為新的有序表，
- 每步將一個待排序的物件, 插入到前面已經排好序的有序表的適當位置上, 直到物件全部插入為止，
代碼實作
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class InsertSort {
public static void main(String[] args) {
// int[] arr = {101, 34, 119, 1, 21, 25, 12, 16, 8};
// insertSort(arr);
/**
* 測驗選擇排序的速度O(n^2) 設定80000個資料
* 創建80000個隨機陣列
*/
int[] arr = new int[800000];
for (int i = 0; i < 800000; i++) {
arr[i] = (int) (Math.random() * 800000);//生成[0,800000)之間的數
}
Date startStr = new Date();
SimpleDateFormat dateFormatStartStr = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String dateStartStr = dateFormatStartStr.format(startStr);
System.out.println("排序前的時間: " + dateStartStr);
insertSort(arr);
Date endStr = new Date();
String dateEndStr = dateFormatStartStr.format(endStr);
System.out.println("排序后的時間: " + dateEndStr);
}
/**
* 插入排序
*
* @param arr
*/
public static void insertSort(int[] arr) {
//使用逐步推導方式講解
//第一輪 {101,34,119,1} => {34,101,119,1}
int insertVal = 0;
int insertIndex = 0; //即arr[i] 前面一個數下標
//定義待插入的數
for (int i = 1; i < arr.length; i++) {
insertVal = arr[i];
insertIndex = i - 1; //即arr[i] 前面一個數下標
/**
* 1. insertIndex >= 0 保證在給InsertVal 找到插入位置 不產生越界ArrayOut
* 2.insertVal < arr[insertIndex] 待插入的數 沒有找到插入位置
* 3.將arr[insertIndex] 后移
*/
//給insertVal 找到插入的位置
// 若需要從大到小排序 只需要將 insertVal `<` arr[insertIndex] 修改為 => insertVal `>` arr[insertIndex]
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--;
}
//當退出while回圈時 說明插入位置找到 insertIndex + 1
//TODO 若無法理解 debug即可
//判斷是否需要賦值
if (insertIndex + 1 != i) {
arr[insertIndex + 1] = insertVal;
}
// System.out.println("第"+i+"輪:" + Arrays.toString(arr));
}
}
}
希爾排序
# 1.希爾排序
- 希爾排序也是一種插入排序，它是簡單插入排序經過改進之后的一個更高效的版本，也稱為縮小增量排序，
# 2.希爾排序思想
- 希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個檔案恰被分成一組，演算法便終止，
代碼實作
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class ShellSort {
public static void main(String[] args) {
int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
shellSortImprove(arr);
System.out.println(Arrays.toString(arr));
/**
* 測驗選擇排序的速度O(n^2) 設定80000個資料
* 創建80000個隨機陣列
*/
// int[] arr = new int[80000];
// for (int i = 0; i < 80000; i++) {
// arr[i] = (int) (Math.random() * 800000);//生成[0,800000)之間的數
// }
//
// Date startStr = new Date();
// SimpleDateFormat dateFormatStartStr = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
// String dateStartStr = dateFormatStartStr.format(startStr);
// System.out.println("排序前的時間: " + dateStartStr);
// shellSortImprove(arr);
// Date endStr = new Date();
// String dateEndStr = dateFormatStartStr.format(endStr);
// System.out.println("排序后的時間: " + dateEndStr);
}
/**
* 希爾排序
* 對有序序列在插入時采用·交換法·, 并測驗排序速度
*
* @param arr
*/
public static void shellSort(int[] arr) {
int temp = 0;
int count = 0;
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < arr.length; i++) {
//遍歷個組中所有的元素(共gap組 每組有gap個元素) 步長為5
for (int j = i - gap; j >= 0; j -= 5) {
//如果當前元素大于arr[j] > arr[j+5] 則交換元素
if (arr[j] > arr[j + gap]) {
temp = arr[j];
arr[j] = arr[j + gap];
arr[j + gap] = temp;
}
}
}
// System.out.println("第" + (++count) + "輪:" + Arrays.toString(arr));
}
}
public static void shellSortImprove(int[] arr) {
int count = 0;
//增量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];
if (arr[j] < arr[j - gap]) {
while (j - gap >= 0 && temp < arr[j - gap]) {
//移動
arr[j] = arr[j - gap];
j -= gap;
}
//當 退出while后 就給temp找到插入的位置
arr[j] = temp;
}
System.out.println("第" + (++count) + "輪:" + Arrays.toString(arr));
}
}
}
}
快速排序
# 1.快速排序
- 快速排序（Quicksort）是對冒泡排序的一種改進，
# 2.快速排序基本思想
- 取待排序記錄序列中的某個記錄(例如取第一個記錄)作為基準(樞軸),按照該記錄的關鍵字大小,將整個記錄序列劃分為左右兩個子序列： 左側子序列中所有記錄的關鍵字都小于或等于基準記錄的關鍵字；右側子序列中所有記錄的關鍵字都大于基準記錄的關鍵字，
代碼實作
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class QuickSort {
public static void main(String[] args) {
// int[] arr = {-9, 78, 0, 23, -567, 70, 5, 8, 1, 3, 9, 6, 2, 7};
// quickSort(arr, 0, arr.length - 1);
// System.out.println(Arrays.toString(arr));
/**
* 測驗選擇排序的速度O(n^2) 設定80000個資料
* 創建80000個隨機陣列
*/
int[] arr = new int[80000000];
for (int i = 0; i < 80000000; i++) {
arr[i] = (int) (Math.random() * 800000000);//生成[0,800000)之間的數
}
Date startStr = new Date();
SimpleDateFormat dateFormatStartStr = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String dateStartStr = dateFormatStartStr.format(startStr);
System.out.println("排序前的時間: " + dateStartStr);
quickSort(arr,0,arr.length-1);
Date endStr = new Date();
String dateEndStr = dateFormatStartStr.format(endStr);
System.out.println("排序后的時間: " + dateEndStr);
}
/**
* @param arr
* @param left
* @param right
*/
public static void quickSort(int[] arr, int left, int right) {
/**
* eft:左下標
* ght:右下標
* pivot:中軸值
* temp:臨時變數 作為交換時使用
*/
int eft = left;
int ght = right;
int pivot = arr[(left + right) / 2];
int temp = 0;
/**
* while回圈目的: 比pivot小的值放在左邊 比pivot大的值放在右邊
*/
while (eft < ght) {
//在pivot左邊 找到大于等于pivot值
while (arr[eft] < pivot) {
eft = eft + 1;
}
while (arr[ght] > pivot) {
ght = ght - 1;
}
//若eft > ght 說明pivot的左右兩的值 已經按照左邊全部是小于等于(>=)pivot值 右邊全部是大于等于(<=)pivot值
if (eft >= ght) {
break;
}
//交換
temp = arr[eft];
arr[eft] = arr[ght];
arr[ght] = temp;
//交換完成后 發現arr[eft] == pivot 值 讓eft--; 前移
if (arr[eft] == pivot) {
ght = ght - 1;
}
//交換完成后 發現arr[ght] == pivot 值 讓ght++; 后移
if (arr[ght] == pivot) {
eft = eft + 1;
}
}
//若eft == ght 必須 eft++ ght-- 否則出現堆疊溢位
if (eft == ght) {
eft = eft + 1;
ght = ght - 1;
}
//向左遞回
if (left < ght) {
quickSort(arr, left, ght);
}
//向右遞回
if (right > eft) {
quickSort(arr, eft, right);
}
}
}
歸并排序
# 1.歸并排序
- 參考檔案:https://baike.baidu.com/item/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F/1639015?fr=aladdin
- 歸并排序（MERGE-SORT）是利用歸并的思想實作的排序方法，該演算法采用經典的分治（divide-and-conquer）策略（分治法將問題分(divide)成一些小的問題然后遞回求解，而治(conquer)的階段則將分的階段得到的各答案"修補"在一起，即分而治之)，
- 歸并是將兩個或兩個以上的有序表合并成一個新的有序表，
# 2.歸并排序思路
-
代碼實作
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class MergetSort {
public static void main(String[] args) {
/**
* 歸并排序需要額外的空間
*/
// int arr[] = {8, 4, 5, 7, 1, 3, 6, 2};
// int temp[] = new int[arr.length];
// mergeSort(arr, 0, arr.length - 1, temp);
// System.out.println(Arrays.toString(arr));
/**
* 測驗選擇排序的速度O(n^2) 設定80000個資料
* 創建80000個隨機陣列
*/
int[] arr = new int[8000000];
for (int i = 0; i < 8000000; i++) {
arr[i] = (int) (Math.random() * 800000000);//生成[0,800000)之間的數
}
int[] temp = new int[arr.length];
Date startStr = new Date();
SimpleDateFormat dateFormatStartStr = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String dateStartStr = dateFormatStartStr.format(startStr);
System.out.println("排序前的時間: " + dateStartStr);
mergeSort(arr,0,arr.length-1,temp);
Date endStr = new Date();
String dateEndStr = dateFormatStartStr.format(endStr);
System.out.println("排序后的時間: " + dateEndStr);
}
/**
* 歸并排序-分、合并方法
*
* @param arr
* @param left
* @param right
* @param temp
*/
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);
}
}
/**
* 歸并排序-合并方法
*
* @param arr 排序的原始陣列
* @param left 左邊有序序列的初始索引
* @param mid 中間索引
* @param right 右邊索引
* @param temp 臨時陣列
*/
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
/**
* i:初始化i,左邊有序序列的初始索引
* j:初始化j,右邊有序序列的初始索引
* cur:指向temp陣列當前索引
*/
int i = left;
int j = mid + 1;
int cur = 0;
//1. 先把左右(有序)的資料按照規則填充到temp陣列,直到左右兩邊的有序序列 有一邊處理完畢
while (i <= mid && j <= right) {
//如果左邊的有序序列的當前元素 小于等于(<=) 右邊有序序列的當前元素
//即將左邊的當前元素 拷貝到temp陣列
//然后cur++ i++
if (arr[i] <= arr[j]) {
temp[cur] = arr[i];
cur = cur + 1;
i = i + 1;
} else {
//如果左邊的有序序列的當前元素 大于等于(>=) 右邊有序序列的當前元素
//即將右邊的當前元素 拷貝到temp陣列
temp[cur] = arr[j];
cur = cur + 1;
j = j + 1;
}
}
//2.有剩余資料的一邊 將資料一次全部移到temp陣列
while (i <= mid) { //左邊的有序序列還有剩余的元素 將剩余的元素全部拷貝到temp
temp[cur] = arr[i];
cur = cur + 1;
i = i + 1;
}
while (j <= right) { //右邊的有序序列還有剩余的元素 將剩余的元素全部拷貝到temp
temp[cur] = arr[j];
cur = cur + 1;
j = j + 1;
}
//3.將temp陣列的元素拷貝到arr
//TODO 不是每次都拷貝所有
cur = 0;
int tempLeft = left;
// System.out.println("tempLeft: "+tempLeft+" right: "+right);
while (tempLeft <= right) {
arr[tempLeft] = temp[cur];
cur = cur + 1;
tempLeft = tempLeft + 1;
}
}
}
基數排序(桶排序)
# 1.基數排序
- 基數排序（radix sort）屬于“分配式排序”（distribution sort），又稱“桶子法”（bucket sort）或bin sort，顧名思義，它是通過鍵值的各個位的值，將要排序的元素分配至某些"桶"中,達到排序的作用，
- 基數排序法是屬于穩定性的排序,基數排序法的是效率高的穩定性排序法，
- 基數排序(Radix Sort)是桶排序的擴展，
- 基數排序是1887年赫爾曼·何樂禮發明的，它是這樣實作的：將整數按位數切割成不同的數字，然后按每個位數分別比較，
# 2.基數排序
- 將所有待比較數值統一為同樣的數位長度，數位較短的數前面補零，然后，從最低位開始，依次進行一次排序，這樣從最低位排序一直到最高位排序完成以后, 數列就變成一個有序序列，
- 基數排序是對傳統桶排序的擴展，速度很快，
- 數排序是經典的空間換時間的方式，占用記憶體很大, 當對海量資料排序時，容易造成 OutOfMemoryError ，
- 基數排序時穩定的，[注:假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序演算法是穩定的；否則稱為不穩定的]
- 有負數的陣列，我們不用基數排序來進行排序, 如果要支持負數，參考: https://code.i-harness.com/zh-CN/q/e98fa9
代碼實作
import java.util.Arrays;
public class RaidxSort {
public static void main(String[] args) {
int arr[] = {53, 3, 542, 748, 14, 214};
radixSort(arr);
}
/**
* 基數排序
*
* @param arr
*/
public static void radixSort(int[] arr) {
//基數排序代碼
//1.得到陣列中最大的數的位數
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
//得到最大數的位數
int maxLength = (max + "").length();
//定義一個二維陣列 表示10個桶 每個桶都是一個一維陣列
int[][] bucket = new int[10][arr.length];
//為了記錄每個桶中 實際存放了多少個陣列 定義一個一維陣列來記錄各個桶每次放入的資料個數
//如 bucketElementCounts[0] 記錄的資料為 bucket[0] 桶放入資料個數
int[] bucketElementCounts = new int[10];
//使用回圈將代碼處理
for (int i = 0, n = 1; i < maxLength; i++, n = n * 10) {
//針對每個元素的位數的 個位數、十位數、百位數等進行排序處理
for (int j = 0; j < arr.length; j++) {
//取出每個元素的個位的數
int digitOfElement = arr[j] / n % 10;
//放入到對應的桶中
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
bucketElementCounts[digitOfElement]++;
}
//按照桶的順序(一維陣列的下標依次取出資料 放入原來陣列)
int index = 0;
//遍歷每一個桶 并將桶中的資料 放入到原陣列
for (int k = 0; k < bucketElementCounts.length; k++) {
//如果桶中 有資料 才放入到原陣列
if (bucketElementCounts[k] != 0) {
//回圈該桶即第K個桶(即第k個一維陣列)
for (int l = 0; l < bucketElementCounts[k]; l++) {
//取出陣列放入到arr
arr[index++] = bucket[k][l];
}
}
//TODO 第n輪處理過后 需要將每個bucketElementCounts[k] = 0 不處理會出現 java.lang.ArrayIndexOutOfBoundsException: 6 錯誤
bucketElementCounts[k] = 0;
}
System.out.println("第" + (i + 1) + "輪,個位的數排序處理 arr= " + Arrays.toString(arr));
}
}
}
堆排序
# 1.堆排序
- 參考檔案:https://baike.baidu.com/item/%E5%A0%86%E6%8E%92%E5%BA%8F/2840151?fr=aladdin
- 堆排序是利用堆這種資料結構而設計的一種排序演算法,堆排序是一種選擇排序,它的最壞、最好、平均時間復雜度均為O(nlogn),它也是不穩定排序，
- 堆是具有以下性質的完全二叉樹：每個結點的值都大于或等于其左右孩子結點的值，稱為大頂堆, 注意 : 沒有要求結點的左孩子的值和右孩子的值的大小關系，
- 每個結點的值都小于或等于其左右孩子結點的值，稱為小頂堆，
- 大頂堆特點：arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+2]，i從0開始編號，
- 小頂堆特點：arr[i] <= arr[2*i+1] && arr[i] <= arr[2*i+2]，i從0開始編號，
- 一般升序采用大頂堆，降序采用小頂堆，
# 2.堆排序基本思想
- 將待排序序列構造成一個大頂堆，
- 整個序列的最大值就是堆頂的根節點，
- 將其與末尾元素進行交換，此時末尾就為最大值，
- 然后將剩余n-1個元素重新構造成一個堆，這樣會得到n-1個元素的次小值，如此反復執行，便能得到一個有序序列了，
代碼實作
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class HeapSort {
public static void main(String[] args) {
// int[] arr = {4, 6, 8, 5, 9};
// heapSort(arr);
/**
* 測驗選擇排序的速度O(n^2) 設定80000000個資料
* 創建80000個隨機陣列
*/
int[] arr = new int[80000000];
for (int i = 0; i < 80000000; i++) {
arr[i] = (int) (Math.random() * 800000000);//生成[0,800000000)之間的數
}
Date startStr = new Date();
SimpleDateFormat dateFormatStartStr = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String dateStartStr = dateFormatStartStr.format(startStr);
System.out.println("排序前的時間: " + dateStartStr);
heapSort(arr);
Date endStr = new Date();
String dateEndStr = dateFormatStartStr.format(endStr);
System.out.println("排序后的時間: " + dateEndStr);
}
/**
* 堆排序方法
*
* @param arr
*/
public static void heapSort(int[] arr) {
int temp = 0;
System.out.println("堆排序");
/**
* 分步操作
*/
// adjustHeap(arr,1,arr.length);
// System.out.println("第一次:" + Arrays.toString(arr));//49856
// adjustHeap(arr,0,arr.length);
// System.out.println("第一次:" + Arrays.toString(arr));//96854
/**
* 1.將無序序列構建成一個堆 根據升序降序需要選擇大頂堆或小頂堆
*/
for (int i = arr.length / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, arr.length);
}
// System.out.println(Arrays.toString(arr));//96854
/**
* 2.將堆頂元素與末尾元素交換，將最大元素"沉"到陣列末端;
* 3.重新調整結構，使其滿足堆定義，然后繼續交換堆頂元素與當前末尾元素，反復執行調整+交換步驟，直到整個序列有序，
*/
for (int j = arr.length - 1; j > 0; j--) {
//交換
temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
adjustHeap(arr,0,j);
}
// System.out.println(Arrays.toString(arr));//96854
}
/**
* 將陣列(二叉樹) 調整成一個大頂堆
* 功能:完成將以i 對應的非葉子節點的樹調整成大頂堆
* int[] arr = {4, 6, 8, 5, 9} => i = 1 => adjustHeap -> {4,9,8,5,6} => i = 0 => jdjustHeap => {9,6,8,5,4}
*
* @param arr 待調整的陣列
* @param i 表示非葉子節點在陣列中的索引
* @param length 表示對多少個元素進行調整 length是在逐漸減少
*/
public static void adjustHeap(int[] arr, int i, int length) {
int temp = arr[i];//先取出當前元素的值 保存在臨時變數
/**
* 開始調整
* 說明:
* 1.k = i * 2 + 1 k是i節點的左子節點
*
*/
for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
if (k + 1 < length && arr[k] < arr[k + 1]) {//左子節點值小于右子節點的值
k++;//k指向右子節點
}
if (arr[k] > temp) {//若子節點大于父節點
arr[i] = arr[k];//把較大的值賦給當前節點
i = k; //i 指向 k 繼續回圈比較
} else {
break; //重要!!!
}
}
//當for回圈結束后 已將以i為父節點的樹最大值 放在了頂部(區域)
arr[i] = temp; //將temp值放到調整后的位置
}
}
排序演算法總結
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/271138.html
標籤：其他
上一篇：編程能力突飛猛進是一種什么樣的體驗？快來看大牛的提升方法！
下一篇：1. 兩數之和(難度：簡單)