溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇內容介紹了“Java十大排序算法怎么實現”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！
假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，如果排序以后，保證這些記錄的相對次序保持不變，即在原序列中，a[i]=a[j]，且 a[i] 在 a[j] 之前，排序后保證 a[i] 仍在 a[j] 之前，則稱這種排序算法是穩定的；否則稱為不穩定的。
每次從待排序的元素中選擇最小的元素，依次和第1、2、3...位置的元素進行交換。這樣在數組前面的部分形成有序區域。每進行一次交換，有序區域長度加一。
public static void selectionSort(int[] arr){
//細節一：這里可以是arr.length也可以是arr.length-1
for (int i = 0; i < arr.length-1 ; i++) {
int mini = i;
for (int j = i+1; j < arr.length; j++) {
//切換條件，決定升序還是降序
if(arr[mini]>arr[j]) mini =j;
}
swap(arr,mini,i);
}
}依次比較相鄰的兩個數，如果順序錯誤就把他們交換過來，這樣的話，每一輪比較下來都可以把最大的數放到它應該在的位置。（就像是把最大的氣泡冒到最上層一樣）
這里解釋一下順序錯誤的含義。我們按照按升序排序，后面的值應該大于等于前面的值，如果不滿足的話，就交換。
public static void bubbleSort(int[] arr){
for (int i = 0; i < arr.length-1; i++) {
//記錄本次有沒有進行交換的操作
boolean flag = false;
//保存在頭就動頭，保存在尾就動尾
for(int j =0 ; j < arr.length-1-i ; j++){
//升序降序選擇地
if(arr[j] > arr[j+1])
{
swap(arr,j,j+1);
flag = true;
}
}
//如果本次沒有進行交換操作，表示數據已經有序
if(!flag){break;} //程序結束
}
}插入排序其實可以理解為我們玩撲克時摸牌的過程，我們在摸牌的時候手里的牌總是有序的，每摸一張牌，就把這張牌插到它應該在的位置。等所有的牌都摸完了以后，全部的牌就都有序了。
思考：數組前面形成了有序區域，那我查找當前數字應該插入位置的時候，用二分進行，是不是就可以把插入排序的復雜度優化到O(nlogn)了呀？
二分倒是可以log的復雜度找到位置。 關鍵是如果用數組存儲的話，插入的時候數據后移還是O(n)的復雜度。如果用鏈表的話，找到位置插入是O(1)的了，但是鏈表也沒辦法二分呀。
public static void insertSort(int[] arr){
//從第二個數開始，把每個數依次插入到指定的位置
for(int i = 1 ; i < arr.length ; i++)
{
int key = arr[i];
int j = i-1;
//大的后移操作
while(j >= 0 && arr[j] > key)
{
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}希爾排序是Donald Shell于1959年提出的一種排序算法，是對直接插入排序的改進之后的高效版本。 希爾排序需要準備一組數據作為增量序列。
這組數據需要滿足以下三個條件：
1. 數據遞減排列
2. 數據中的最大值小于待排序數組的長度
3. 數據中的最小值是1。
只要滿足上述要求的數組都可以作為增量序列，但是不同的增量序列會影響到排序的效率。這里我們用{5,3,1}作為增量序列來進行講解
實現優化的原因：減少數據量，使O(n)和O(n^2)的差距并不大
public static void shellSort(int[] arr){
//分塊處理
int gap = arr.length/2; //增量
while(1<=gap)
{
//插入排序：只不過是與增量位交換
for(int i = gap ; i < arr.length ; i++)
{
int key = arr[i];
int j = i-gap;
while(j >= 0 && arr[j] > key)
{
arr[j+gap] = arr[j];
j-=gap;
}
arr[j+gap] = key;
}
gap = gap/2;
}
}是一棵完全二叉樹，分為大根堆、小根堆兩種
可以O(1)取最大/小值，可以O(logn)刪除最大/小值，可以O(logn)插入元素
MIN-HEAPIFY（i）操作：
我們假設完全二叉樹中某節點 i 的左子樹和右子樹都滿足小根堆的性質，假設 i 節點的左孩子是 left_i，i 節點的右孩子是 rig?t_i。那如果 a[i] 大于 a[left_i] 或 a[rig?t_i] 的話，那以 i 節點為根節點的整棵子樹就不滿足小根堆的性質了，我們現在要進行一個操作：把以 i 為根節點的這棵子樹調整成小根堆。
//堆排序
public static void heapSort(int[] arr){
//開始調整的位置為最后一個葉子節點
int start = (arr.length - 1)/2;
//從最后一個葉子節點開始遍歷，調整二叉樹
for (int i = start; i >= 0 ; i--){
maxHeap(arr, arr.length, i);
}
for (int i = arr.length - 1; i > 0; i--){
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
maxHeap(arr, i, 0);
}
}
//將二叉樹調整為大頂堆
public static void maxHeap(int[] arr, int size, int index){
//建立左子節點
int leftNode = 2 * index + 1;
//建立右子節點
int rightNode = 2 * index + 2;
int maxNode = index;
//左子節點的值大于根節點時調整
if (leftNode < size && arr[leftNode] > arr[maxNode]){
maxNode = leftNode;
}
//右子節點的值大于根節點時調整
if (rightNode < size && arr[rightNode] > arr[maxNode]){
maxNode = rightNode;
}
if (maxNode != index){
int temp = arr[maxNode];
arr[maxNode] = arr[index];
arr[index] = temp;
//交換之后可能會破壞原來的結構，需要再次調整
//遞歸調用進行調整
maxHeap(arr, size, maxNode);
}
}我使用的是大根堆，排序的過程歸根下來就是：先左底根后右底根（看自己怎么寫）->每個根向上在向下。（左右上下）
歸并排序是分治法的典型應用，先來介紹一下分治法，分治法是把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題規模很小可以直接求解，再將子問題的解進行合并來得到原問題的解。
歸并排序分解子問題的過程就是每一次把數組分成2份，直到數組的長度為1（因為只有一個數字的數組是有序的）。然后再將相鄰的有序數組合并成一個有序數組。直到全部合到一起，整個數組就排序完畢了。 現在要解決的問題就是如何把兩個有序的數組合并成一個有序的數組。其實就是每次比較兩個數組當前最小的兩個元素，哪個小就選哪個
數組a | 數組b | 說明 | 答案數組 |
2,5,7 | 1,3,4 | 1<2，取1，數組b的指針后移 | 1 |
2,5,7 | 1,3,4 | 2<3，取2，數組a的指針后移 | 1,2 |
2,5,7 | 1,3,4 | 3<5，取3，數組b的指針后移 | 1,2,3 |
2,5,7 | 1,3,4 | 4<5，取4，數組b的指針后移 | 1,2,3,4 |
2,5,7 | 1,3,4 | 數組b中沒有元素了，取5 | 1,2,3,4,5 |
2,5,7 | 1,3,4 | 數組b中沒有元素了，取7 | 1,2,3,4,5,7 |
public static void mergeSort(int[] arr, int low, int high){
int middle = (high + low)/2;
if (low < high){
//遞歸排序左邊
mergeSort(arr, low, middle);
//遞歸排序右邊
mergeSort(arr, middle +1, high);
//將遞歸排序好的左右兩邊合并
merge(arr, low, middle, high);
}
}
public static void merge(int[] arr, int low, int middle, int high){
//存儲歸并后的臨時數組
int[] temp = new int[high - low + 1];
int i = low;
int j = middle + 1;
//記錄臨時數組中存放數字的下標
int index = 0;
while (i <= middle && j <= high){
if (arr[i] < arr[j]){
temp[index] = arr[i];
i++;
} else {
temp[index] = arr[j];
j++;
}
index++;
}
//處理剩下的數據
while (j <= high){
temp[index] = arr[j];
j++;
index++;
}
while (i <= middle){
temp[index] = arr[i];
i++;
index++;
}
//將臨時數組中的數據放回原來的數組
for (int k = 0; k < temp.length; ++k){
arr[k + low] = temp[k];
}
}快速排序的工作原理是：從待排序數組中隨便挑選一個數字作為基準數，把所有比它小的數字放在它的左邊，所有比它大的數字放在它的右邊。然后再對它左邊的數組和右邊的數組遞歸進行這樣的操作。
全部操作完以后整個數組就是有序的了。 把所有比基準數小的數字放在它的左邊，所有比基準數大的數字放在它的右邊。這個操作，我們稱為“劃分”(Partition)。
//快速排序
public static void QuickSort1(int[] arr, int start, int end){
int low = start, high = end;
int temp;
if(start < end){
int guard = arr[start];
while(low != high){
while(high > low && arr[high] >= guard) high--;
while(low < high && arr[low] <= guard) low++;
if(low < high){
temp = arr[low];
arr[low] = arr[high];
arr[high] = temp;
}
}
arr[start] = arr[low];
arr[low] = guard;
QuickSort1(arr, start, low-1);
QuickSort1(arr, low+1, end);
}
}
//快速排序改進版(填坑法)
public static void QuickSort2(int[] arr, int start, int end){
int low = start, high = end;
if(start < end){
while(low != high){
int guard = arr[start];//哨兵元素
while(high > low && arr[high] >= guard) high--;
arr[low] = arr[high];
while(low < high && arr[low] <= guard) low++;
arr[high] = arr[low];
}
arr[low] = guard;
QuickSort2(arr, start, low-1);
QuickSort2(arr, low+1, end);
}
}計算一下每一個數出現了多少次。舉一個例子，比如待排序的數據中1出現了2次，2出現了0次，3出現了3次，4出現了1次，那么排好序的結果就是{1.1.3.3.3.4}。
//鴿巢排序
public static void PigeonholeSort(int[] arr){
//獲取最大值
int k = 0;
for (int i = 0; i < arr.length; i++) {
k = Math.max(k,arr[i]);
}
//創建計數數組并且初始化為0
int[] cnt = new int[k+10];
for(int i = 0 ; i <= k ; i++) { cnt[i]=0; }
for(int i = 0 ; i < arr.length ;i++) { cnt[arr[i]]++; }
int j = 0;
for(int i = 0 ; i <=k ; i++)
{
while(cnt[i]!=0)
{
arr[j]=i;
j++;
cnt[i]--;
}
}
}鴿巢排序其實算不上是真正意義上的排序算法，它的局限性很大。只能對純整數數組進行排序，舉個例子，如果我們需要按學生的成績進行排序。是一個學生+分數的結構那就不能排序了。
先考慮這樣一個事情：如果對于待排序數據中的任意一個元素 a[i]，我們知道有 m 個元素比它小，那么我們是不是就可以知道排好序以后這個元素應該在哪個位置了呢？（這里先假設數據中沒有相等的元素）。計數排序主要就是依賴這個原理來實現的。
比如待排序數據是{2,4,0,2,4} 先和鴿巢一樣做一個cnt數組{1,0,2,0,2} 0,1,2,3,4
此時cnt[i]表示數據i出現了多少次，
然后對cnt數組做一個前綴和{1,1,3,3,5} ：0,1,2,3,4
此時cnt[i]表示數據中小于等于i的數字有多少個
待排序數組 | 計數數組 | 說明 | 答案數組ans |
2,4,0,2,4 | 1,1,3,3,5 | 初始狀態 | null,null,null,null,null, |
2,4,0,2,4 | 1,1,3,3,5 | cnt[4]=5，ans第5位賦值，cnt[4]-=1 | null,null,null,null,4 |
2,4,0,2,4 | 1,1,3,3,4 | cnt[2]=3，ans第3位賦值，cnt[2]-=1 | null,null,2 null,4 |
2,4,0,2,4 | 1,1,2,3,4 | cnt[0]=1，ans第1位賦值，cnt[0]-=1 | 0,null,2,null,4 |
2,4,0,2,4 | 0,1,2,3,4 | cnt[4]=4，ans第4位賦值，cnt[4]-=1 | 0,null,2,4,4 |
2,4,0,2,4 | 0,1,2,3,3 | cnt[2]=2，ans第2位賦值，cnt[2]-=1 | 0,2,2,4,4 |
基數排序是通過不停的收集和分配來對數據進行排序的。
因為是10進制數，所以我們準備十個桶來存分配的數。
最大的數據是3位數，所以我們只需要進行3次收集和分配。
需要先從低位開始收集和分配（不可從高位開始排，如果從高位開始排的話，高位排好的順序會在排低位的時候被打亂，有興趣的話自己手寫模擬一下試試就可以了）
在收集和分配的過程中，不要打亂已經排好的相對位置
比如按十位分配的時候，152和155這兩個數的10位都是5，并且分配之前152在155的前面，那么收集的時候152還是要放在155之前的。
//基數排序
public static void radixSort(int[] array) {
//基數排序
//首先確定排序的趟數;
int max = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > max) {
max = array[i];
}
}
int time = 0;
//判斷位數;
while (max > 0) {
max /= 10;
time++;
}
//建立10個隊列;
List<ArrayList> queue = new ArrayList<ArrayList>();
for (int i = 0; i < 10; i++) {
ArrayList<Integer> queue1 = new ArrayList<Integer>();
queue.add(queue1);
}
//進行time次分配和收集;
for (int i = 0; i < time; i++) {
//分配數組元素;
for (int j = 0; j < array.length; j++) {
//得到數字的第time+1位數;
int x = array[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
ArrayList<Integer> queue2 = queue.get(x);
queue2.add(array[j]);
queue.set(x, queue2);
}
int count = 0;//元素計數器;
//收集隊列元素;
for (int k = 0; k < 10; k++) {
while (queue.get(k).size() > 0) {
ArrayList<Integer> queue3 = queue.get(k);
array[count] = queue3.get(0);
queue3.remove(0);
count++;
}
}
}
}“Java十大排序算法怎么實現”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
