溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇內容主要講解“Java排序算法怎么快速上手”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“Java排序算法怎么快速上手”吧!
插入排序的基本思想：每步將一個待排序元素，按其排序碼大小插入到前面已經排好序的一組元素中，直到元素全部插入為止。在這里，我們介紹三種具體的插入排序算法：直接插入排序，希爾排序與折半插入排序。
1、直接插入排序
**直接插入排序的思想：**當插入第i(i>=1)個元素時，前面的V[0],…,V[i-1]等i-1個 元素已經有序。這時，將第i個元素與前i-1個元素V[i-1]，…，V[0]依次比較，找到插入位置即將V[i]插入，同時原來位置上的元素向后順移。在這里，插入位置的查找是順序查找。直接插入排序是一種穩定的排序算法，其實現如下：
/**
* Title: 插入排序中的直接插入排序，依賴于初始序列
* Description: 在有序序列中不斷插入新的記錄以達到擴大有序區到整個數組的目的
* 時間復雜度：最好情形O(n)，平均情形O(n^2)，最差情形O(n^2)
* 空間復雜度：O(1)
* 穩 定 性：穩定
* 內部排序(在排序過程中數據元素完全在內存)
* @author rico
* @created 2017年5月20日 上午10:40:00
*/
public class StraightInsertionSort {
public static int[] insertSort(int[] target){
if(target != null && target.length != 1){ // 待排序數組不為空且長度大于1
for (int i = 1; i for (int j = i; j > 0; j--) { // 向有序序列中插入新的元素
if(target[j] return target;
}
}2、希爾排序
**希爾排序的思想：**設待排序序列共n個元素，首先取一個整數gap
/**
* Title: 插入排序中的希爾排序，依賴于初始序列
* Description: 分別對間隔為gap的gap個子序列進行直接插入排序，不斷縮小gap,直至為 1
*
* 剛開始時，gap較大，每個子序列元素較少，排序速度較快；
* 待到排序后期，gap變小，每個子序列元素較多，但大部分元素基本有序，所以排序速度仍較快。
*
* 時間復雜度：O(n) ~ O(n^2)
* 空間復雜度：O(1)
* 穩 定 性：不穩定
* 內部排序(在排序過程中數據元素完全在內存)
* @author rico
* @created 2017年5月20日 上午10:40:00
*/
public class ShellSort {
public static int[] shellSort(int[] target){
if(target != null && target.length != 1){
int gap = target.length; // gap個大小為gap的子序列
do{
gap = gap/3 + 1; // 不斷縮小gap直至為1
for (int i = 0 + gap; i if(target[i] do{
target[j + gap] = target[j]; // 后移元素
j = j - gap; // 再比較前一個元素
}while(j >= 0 && target[j] > temp); // 向前比較的終止條件
target[j + gap] = temp; // 將待插入值插入合適的位置
}
}
}while(gap > 1);
}
return target;
}
}3、折半插入排序
**折半插入排序的思想：**當插入第i(i>=1)個元素時，前面的V[0],…,V[i-1]等i-1個 元素已經有序。這時，折半搜索第i個元素在前i-1個元素V[i-1]，…，V[0]中的插入位置，然后直接將V[i]插入，同時原來位置上的元素向后順移。與直接插入排序不同的是，折半插入排序比直接插入排序明顯減少了關鍵字之間的比較次數，但是移動次數是沒有改變。所以，折半插入排序和插入排序的時間復雜度相同都是O（N^2），但其減少了比較次數，所以該算法仍然比直接插入排序好。折半插入排序是一種穩定的排序算法，其實現如下：
/**
* Title: 插入排序中的折半插入排序，依賴于初始序列
* Description: 折半搜索出插入位置，并直接插入;與直接插入搜索的區別是，后者的搜索要快于順序搜索
* 時間復雜度：折半插入排序比直接插入排序明顯減少了關鍵字之間的比較次數，但是移動次數是沒有改變。所以，
* 折半插入排序和插入排序的時間復雜度相同都是O（N^2），在減少了比較次數方面它確實相當優秀，所以該算法仍然比直接插入排序好。
* 空間復雜度：O(1)
* 穩 定 性：穩定
* 內部排序(在排序過程中數據元素完全在內存)
* @author rico
* @created 2017年5月25日 下午12:03:23
*/
public class BinaryInsertSort {
public static int[] binaryInsertSort(int[] target) {
if (target != null && target.length > 1) {
for (int i = 1; i if(temp while(left if(target[mid] else if(target[mid] > temp){
right = mid - 1; // 縮小插入區間
}else{ // 待插入值與有序序列中的target[mid]相等，保證穩定性的處理
left = left + 1;
}
}
// left及其后面的數據順序向后移動，并在left位置插入
for (int j = i; j > left; j--) {
target[j] = target[j-1];
}
target[left] = temp;
}
}
}
return target;
}
}**選擇排序的基本思想：**每一趟 (例如第i趟，i = 0,1,…)在后面第n-i個待排序元素中選出最小元素作為有序序列的第i個元素，直到第n-1趟結束后，所有元素有序。在這里，我們介紹兩種具體的選擇排序算法：直接選擇排序與堆排序。
1、直接選擇排序
**直接選擇排序的思想：**第一次從R[0]~R[n-1]中選取最小值，與R[0]交換，第二次從R1~R[n-1]中選取最小值，與R1交換，….，第i次從R[i-1]~R[n-1]中選取最小值，與R[i-1]交換，…..，第n-1次從R[n-2]~R[n-1]中選取最小值，與R[n-2]交換，總共通過n-1次，得到一個按排序碼從小到大排列的有序序列。直接選擇排序是一種不穩定的排序算法，其實現如下：
/**
* Title: 選擇排序中的直接選擇排序，依賴于初始序列
* Description: 每一趟 (例如第i趟，i = 0,1,...)在后面第n-i個待排序元素中選出最小元素作為有序序列的第i個元素
* 時間復雜度：最好情形O(n^2)，平均情形O(n^2)，最差情形O(n^2)
* 空間復雜度：O(1)
* 穩 定 性：不穩定
* 內部排序(在排序過程中數據元素完全在內存)
* @author rico
* @created 2017年5月20日 上午10:40:00
*/
public class StraightSelectSort {
public static int[] selectSort(int[] target){
if(target != null && target.length != 1){
for (int i = 0; i for (int j = i + 1; j if(target[min_index] > target[j]){
min_index = j;
}
}
if(target[min_index] != target[i]){ // 導致不穩定的因素：交換
int min = target[min_index];
target[min_index] = target[i];
target[i] = min;
}
}
}
return target;
}
}2、堆排序
**堆排序的核心是堆調整算法。**首先根據初始輸入數據，利用堆調整算法shiftDown()形成初始堆；然后，將堆頂元素與堆尾元素交換，縮小堆的范圍并重新調整為堆，如此往復。堆排序是一種不穩定的排序算法，其實現如下：
/**
* Title: 堆排序(選擇排序)，升序排序(最大堆)，依賴于初始序列
* Description: 現將給定序列調整為最大堆，然后每次將堆頂元素與堆尾元素交換并縮小堆的范圍，直到將堆縮小至1
* 時間復雜度：O(nlgn)
* 空間復雜度：O(1)
* 穩 定 性：不穩定
* 內部排序(在排序過程中數據元素完全在內存)
* @author rico
* @created 2017年5月25日 上午9:48:06
*/
public class HeapSort {
public static int[] heapSort(int[] target) {
if (target != null && target.length > 1) {
// 調整為最大堆
int pos = (target.length - 2) / 2;
while (pos >= 0) {
shiftDown(target, pos, target.length - 1);
pos--;
}
// 堆排序
for (int i = target.length-1; i > 0; i--) {
int temp = target[i];
target[i] = target[0];
target[0] = temp;
shiftDown(target, 0, i-1);
}
return target;
}
return target;
}
/**
* @description 自上而下調整為最大堆
* @author rico
* @created 2017年5月25日 上午9:45:40
* @param target
* @param start
* @param end
*/
private static void shiftDown(int[] target, int start, int end) {
int i = start;
int j = 2 * start + 1;
int temp = target[i];
while (j if (j target[j]) { //找出較大子女
j = j + 1;
}
if (target[j] break;
} else {
target[i] = target[j];
i = j;
j = 2 * j + 1;
}
}
target[i] = temp;
}
}**交換排序的基本思想：**根據序列中兩個元素的比較結果來對換這兩個記錄在序列中的位置，也就是說，將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動。
1、冒泡排序
**冒泡排序的思想：**根據序列中兩個元素的比較結果來對換這兩個記錄在序列中的位置，將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動。因此，每一趟都將較小的元素移到前面，較大的元素自然就逐漸沉到最后面了，也就是說，最大的元素最后才能確定，這就是冒泡。冒泡排序是一種穩定的排序算法，其實現如下：
/**
* Title: 交換排序中的冒泡排序 ，一般情形下指的是優化后的冒泡排序，最多進行n-1次比較，依賴于初始序列
* Description:因為越大的元素會經由交換慢慢"浮"到數列的頂端(最后位置)，最大的數最后才確定下來，所以稱為冒泡排序
* 時間復雜度：最好情形O(n)，平均情形O(n^2)，最差情形O(n^2)
* 空間復雜度：O(1)
* 穩 定 性：穩定
* 內部排序(在排序過程中數據元素完全在內存)
*
* @author rico
* @created 2017年5月20日 上午10:40:00
*/
public class BubbleSort {
/**
* @description 樸素冒泡排序(共進行n-1次比較)
* @author rico
*/
public static int[] bubbleSort(int[] target) {
int n = target.length;
if (target != null && n != 1) {
// 最多需要進行n-1躺，每一趟將比較小的元素移到前面，比較大的元素自然就逐漸沉到最后面了，這就是冒泡
for (int i = 0; i for (int j = n-1; j > i; j--) {
if(target[j] return target;
}
/**
* @description 優化冒泡排序
* @author rico
*/
public static int[] optimizeBubbleSort(int[] target) {
int n = target.length;
if (target != null && n != 1) {
// 最多需要進行n-1躺，每一趟將比較小的元素移到前面，比較大的元素自然就逐漸沉到最后面了，這就是冒泡
for (int i = 0; i false;
for (int j = n-1; j > i; j--) {
if(target[j] true;
}
}
System.out.println(Arrays.toString(target));
if (!exchange){ // 若 i 到 n-1 這部分元素已經有序，則直接返回
return target;
}
}
}
return target;
}
}2、快速排序
**快速排序的思想：**通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小(劃分過程)，然后再按此方法對這兩部分數據分別進行快速排序(快速排序過程)，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。快速排序是一種不穩定的排序算法。
/**
* Title: 交換排序中的快速排序，目前應用最為廣泛的排序算法，是一個遞歸算法，依賴于初始序列
* Description:快速排序包括兩個過程：劃分 和 快排
* "劃分"是指將原序列按基準元素劃分兩個子序列
* "快排"是指分別對子序列進行快排
*
* 就平均計算時間而言，快速排序是所有內部排序方法中最好的一個
*
* 對大規模數據排序時，快排是快的；對小規模數據排序時，快排是慢的，甚至慢于簡單選擇排序等簡單排序方法
*
* 快速排序依賴于原始序列，因此其時間復雜度從O(nlgn)到O(n^2)不等
* 時間復雜度：最好情形O(nlgn)，平均情形O(nlgn)，最差情形O(n^2)
*
* 遞歸所消耗的棧空間
* 空間復雜度：O(lgn)
*
* 可選任一元素作為基準元素
* 穩 定 性：不穩定
*
*
* 內部排序(在排序過程中數據元素完全在內存)
*
* @author rico
* @created 2017年5月20日 上午10:40:00
*/
public class QuickSort {
/**
* @description 快排算法(遞歸算法)：在遞去過程中就把問題解決了
* @author rico
* @created 2017年5月20日 下午5:12:06
* @param target
* @param left
* @param right
* @return
*/
public static int[] quickSort(int[] target, int left, int right) {
if(right > left){ // 遞歸終止條件
int base_index = partition(target,left, right); // 原序列劃分后基準元素的位置
quickSort(target, left, base_index-1); // 對第一個子序列快速排序，不包含基準元素！
quickSort(target, base_index+1, right); // 對第二個子序列快速排序，不包含基準元素！
return target;
}
return target;
}
/**
* @description 序列劃分，以第一個元素為基準元素
* @author rico
* @created 2017年5月20日 下午5:10:54
* @param target 序列
* @param left 序列左端
* @param right 序列右端
* @return
*/
public static int partition(int[] target, int left, int right){
int base = target[left]; // 基準元素的值
int base_index = left; // 基準元素最終應該在的位置
for (int i = left+1; i if(target[i] if(base_index != i){ // 相等情況意味著i之前的元素都小于base,只需要換一次即可，不需要次次都換
int temp = target[base_index];
target[base_index] = target[i];
target[i] = temp;
}
}
}
// 將基準元素就位
target[left] = target[base_index];
target[base_index] = base;
System.out.println(Arrays.toString(target));
return base_index; //返回劃分后基準元素的位置
}
}**歸并排序包含兩個過程：”歸”和”并”。**其中，”歸”是指將原序列分成半子序列，分別對子序列進行遞歸排序；”并”是指將排好序的各子序列合并成原序列。歸并排序算法是一個典型的遞歸算法，因此也是概念上最為簡單的排序算法。與快速排序算法相比，歸并排序算法不依賴于初始序列，并且是一種穩定的排序算法，但需要與原序列一樣大小的輔助存儲空間。
/**
* Title: 歸并排序 ，概念上最為簡單的排序算法，是一個遞歸算法，不依賴于初始序列
* Description:歸并排序包括兩個過程：歸 和 并
* "歸"是指將原序列分成半子序列，分別對子序列進行遞歸排序
* "并"是指將排好序的各子序列合并成原序列
*
* 歸并排序的主要問題是：需要一個與原待排序數組一樣大的輔助數組空間
*
* 歸并排序不依賴于原始序列，因此其最好情形、平均情形和最差情形時間復雜度都一樣
* 時間復雜度：最好情形O(n)，平均情形O(n^2)，最差情形O(n^2)
* 空間復雜度：O(n)
* 穩 定 性：穩定
* 內部排序(在排序過程中數據元素完全在內存)
*
* @author rico
* @created 2017年5月20日 上午10:40:00
*/
public class MergeSort {
/**
* @description 歸并排序算法(遞歸算法)：遞去分解，歸來合并
* @author rico
* @created 2017年5月20日 下午4:04:52
* @param target 待排序序列
* @param left 待排序序列起始位置
* @param right 待排序序列終止位置
* @return
*/
public static int[] mergeSort(int[] target, int left, int right) {
if(right > left){ // 遞歸終止條件
int mid = (left + right)/2;
mergeSort(target, left, mid); // 歸并排序第一個子序列
mergeSort(target, mid+1, right); // 歸并排序第二個子序列
return merge(target,left,mid,right); // 合并子序列成原序列
}
return target;
}
/**
* @description 兩路歸并算法
* @author rico
* @created 2017年5月20日 下午3:59:16
* @param target 用于存儲歸并結果
* @param left 第一個有序表的第一個元素所在位置
* @param mid 第一個有序表的最后一個元素所在位置
* @param right 第二個有序表的最后一個元素所在位置
* @return
*/
public static int[] merge(int[] target, int left, int mid, int right){
// 需要一個與原待排序數組一樣大的輔助數組空間
int[] temp = Arrays.copyOf(target, target.length);
// s1,s2是檢查指針，index 是存放指針
int s1 = left;
int s2 = mid + 1;
int index = left;
// 兩個表都未檢查完，兩兩比較
while(s1 if(temp[s1] else{
target[index++] = temp[s2++];
}
}
//若第一個表未檢查完，復制
while(s1 while(s2 return target;
}
}Ps : 歸并排序和快速排序都是典型的遞歸算法，因此它們比較容易理解和實現。關于遞歸思想和內涵深度剖析，請見博文《算法設計方法：遞歸的內涵與經典應用》。
分配排序的基本思想：用空間換時間。在整個排序過程中，無須比較關鍵字，而是通過用額外的空間來”分配”和”收集”來實現排序，它們的時間復雜度可達到線性階：O(n)。其中，基數排序包括兩個過程：首先，將目標序列各元素分配到各個桶中(分配過程)；然后，將各個桶中的元素按先進先出的順序再放回去(收集過程)，如此往復，一共需要進行d趟，d為元素的位數。
/**
* Title: 分配排序中的基數排序，不依賴于初始序列
* Description: 不是在對元素進行比較的基礎上進行排序，而是采用 "分配 + 收集" 的辦法
*
* 首先，將目標序列各元素分配到各個桶中；
* 其次，將各個桶中的元素按先進先出的順序再放回去
* 如此往復...
*
* 時間復雜度：O(d*(r+n))或者 O(dn),d 的大小一般會受到 n的影響
* 空間復雜度：O(rd + n)或者 O(n)
* 穩 定 性：穩定
* 內部排序(在排序過程中數據元素完全在內存)
* @author rico
* @created 2017年5月20日 上午10:40:00
*/
public class RadixSort {
/**
* @description 分配 + 收集
* @author rico
* @created 2017年5月21日 下午9:25:52
* @param target 待排序數組
* @param r 基數
* @param d 元素的位數
* @param n 待排序元素個數
* @return
*/
public static int[] radixSort(int[] target, int r, int d, int n){
if (target != null && target.length != 1 ) {
int[][] bucket = new int[r][n]; // 一共有基數r個桶，每個桶最多放n個元素
int digit; // 獲取元素對應位上的數字，即裝入那個桶
int divisor = 1; // 定義每一輪的除數，1, 10, 100, ...
int[] count = new int[r]; // 統計每個桶中實際存放元素的個數
for (int i = 0; i for (int ele : target) {
digit = (ele/divisor) % 10; // 獲取元素對應位上的數字(巧妙！！！)
bucket[digit][count[digit]++] = ele; // 將元素放入對應桶，桶中元素數目加1
}
// 收集
int index = 0; // 目標數組的下標
for (int j = 0; j while(k return target;
}
}
1、直接插入排序 Vs. 折半插入排序 Vs. 希爾排序
這三種排序方法都屬于插入排序的范疇。與直接插入排序的順序搜索插入位置相比，折半插入排序通過折半搜索的方法搜索插入位置，因此，在搜索插入位置方面，折半插入排序要快于直接插入排序。實際上，折半插入排序比直接插入排序只是減少了關鍵字之間的比較次數，但是移動次數是沒有改變。所以，折半插入排序和插入排序的時間復雜度相同都是O（n^2），但減少了比較次數，所以該算法要比直接插入排序好一點。希爾排序可以看作是對直接插入排序的一種優化，它將全部元素分為間隔為gap的gap個子序列并對每一個子序列進行直接插入排序，同時不斷縮小間隔gap，直至所有元素位于同一個序列。使用這種方式可以保證排序效率，因為剛開始時，gap較大，每個子序列元素較少，排序速度較快；待到排序后期，gap變小，每個子序列元素較多，但大部分元素基本有序，所以排序速度仍較快。因此，希爾排序比直接插入排序 、折半插入排序都要高效，但它不是穩定的。
2、直接選擇排序 Vs. 堆排序
這兩種排序方法都屬于插入選擇排序的范疇，它們的核心思想都是每一趟都選擇一個極值元素放在靠前/靠后位置，直到序列有序。與直接選擇排序不同的是，堆排序不是“蠻力選擇”，而是不斷進行堆調整以取得每趟中的極值。因此，堆排序比直接選擇排序要高效，不過它們都是不穩定的。
3、冒泡排序 Vs. 快速排序
這兩種排序方法都屬于選擇排序的范疇，它們的核心思想都是元素的交換，冒泡排序中每一趟相鄰元素互相比較，并將較小的交換到前面(較大的自然沉到后面)位置，快速排序則是以基準點為基礎，將比它小的元素和比它大的元素分別交換到它的兩邊。因此，快速排序比冒泡排序要高效，但它不是穩定的。
4、歸并排序 Vs. 快速排序
這兩種排序方法都屬于遞歸算法的范疇，因此，它們都比較容易讓人理解和實現。與快速排序相比，歸并排序不但是穩定的，還是與原始序列無關的(不依賴于原始序列的順序，時間復雜度總是O(nlgn))，但是需要與原始序列一樣大小的空間；而快速排序則一般情況下都要比其他高效排序算法（包括歸并排序）快，而且空間復雜度只為O(1)。另外，我們從算法實現中可以看出這兩種遞歸算法有以下區別和聯系：
5、小結
直接插入排序、直接選擇排序和冒泡排序是基本的排序方法，它們平均情況下的時間復雜度都是O(n^2)，實現也比較簡單，它們對規模較小的元素序列很有效。
快速排序、堆排序和歸并排序是高效的排序方法，它們平均情況下的時間復雜度都是O(nlgn)，其中快速排序是最通用的高效排序算法，但其是不穩定的；歸并排序是上述幾種排序算法中唯一與初始序列無關的，而且時間復雜度總是O(nlgn)，但其空間復雜度是O(n)，是一種穩定的排序算法；堆排序的時間復雜度總是O(nlgn)，空間復雜度是O(1)，也是不穩定的。它們對規模較大的元素序列很有效。
希爾排序的效率介于基本排序方法與高效排序方法之間，是一種不穩定的排序算法。它們各有所長，都擁有特定的使用場景。基數排序雖然具有線性增長的時間復雜度，但實際上開銷并不比快速排序小很多，應用相對不太廣泛。
因此，在實際應用中，我們必須根據實際任務的特點和各種排序算法的特性來做出最合適的選擇。
到此，相信大家對“Java排序算法怎么快速上手”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
