溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這里詳細講解了十大經典算法的分類，例如交換排序、插入排序、選擇排序等比較類排序，以及計數排序、桶排序和基數排序的非比較類排序，分析了各種排序算法的復雜度和穩定性，還有JAVA代碼的詳細實現。對冒泡排序、插入排序、選擇排序和堆排序等十種算法進行了詳細的思想總結。
十種常見排序算法可以分為兩大類：
（1）比較類排序：通過比較來決定元素間的相對次序，由于其時間復雜度不能突破O(nlogn)因此也稱為非線性時間比較類排序。
（2）非比較類排序：不通過比較元素間的相對次序，它可以突破基于比較排序的時間下界，以線性時間運行，因此也稱為線性時間非比較類排序。
如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
如果a原本在b的前面，而a=b，排序之后 a 可能會出現在 b 的后面。
對排序數據的總的操作次數。反映當n變化時，操作次數呈現什么規律。
是指算法在計算機內執行時所需存儲空間的度量，它也是數據規模n的函數。
冒泡排序是一種簡單的排序算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。
（1）比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；
（2）對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對，這樣在最后的元素應該會是最大的數；
（3）針對所有的元素重復以上的步驟，除了最后一個；
（4）重復步驟1~3，直到排序完成。
// 一般的冒泡排序
public static void BubbleSort(int[] arr){
int temp; //臨時變量
for (int i = arr.length-1;i > 0 ; i--){ // 表示趟數，一共arr.length-1次
for (int j = 0;j < i; j++){ // 表示比較次數,從后往前，每趟比較把最大的冒到最后面
System.out.println("第"+(arr.length-i)+"趟"+ "第"+(j+1)+"次比較"+Arrays.toString(arr));
if(arr[j] > arr[j+1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}針對問題：數據的順序排好之后，冒泡算法仍然會繼續進行下一輪的比較，直到arr.length-1次，后面的比較沒有意義的。
改進方案：設置標志位flag，如果發生了交換flag設置為true；如果沒有交換就設置為false。這樣當一輪比較結束后如果flag仍為false，即：這一輪沒有發生交換，說明數據的順序已經排好，沒有必要繼續進行下去。
public static void BubbleSort(int[] arr){
int temp; //臨時變量
boolean flag; //是否交換的標記
for (int i = arr.length-1;i > 0 ; i--){ // 表示趟數，一共arr.length-1次
flag = false; //設置起始標志位為false
for (int j = 0;j < i; j++){ // 表示比較次數,從后往前，每趟比較把最大的冒到最后面
System.out.println("第"+(arr.length-i)+"趟"+ "第"+(j+1)+"次比較"+Arrays.toString(arr));
if(arr[j] > arr[j+1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
flag = true;
}
}
if (!flag) break;
}
}改進的冒泡排序，雞尾酒冒泡排序，也叫定向冒泡排序，它的改進在于同時的冒泡兩邊，從低到高，然后從高到低，相當于順便把最小的數也冒泡到最前面。
public static void cocktailSort(int[] arr){
int left = 0,right = arr.length -1,temp;
while (left < right){
for (int i = left;i < right;i++){ //將最大值冒到數組末尾
if (arr[i] > arr[i+1]){
temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
right--;
for (int i = right;i > left;i--){ //將較小值冒到數組前面
if (arr[i] < arr[i-1]){
temp = arr[i];
arr[i] = arr[i-1];
arr[i-1] = temp;
}
}
left++;
}
}選擇排序(Selection-sort)是一種簡單直觀的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
n個記錄的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。具體算法描述如下：
（1）初始狀態：無序區為R[1..n]，有序區為空；
（2）第i趟排序(i=1,2,3…n-1)開始時，當前有序區和無序區分別為R[1..i-1]和R(i..n）。該趟排序從當前無序區中-選出關鍵字最小的記錄 R[k]，將它與無序區的第1個記錄R交換，使R[1..i]和R[i+1..n)分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區；
（3）n-1趟結束，數組有序化了。
public static void selectSort(int[] arr){
//從無序的數組中選出最小值，替換到數組最前面
for(int i = 0;i < arr.length - 1;i++){
int minIndex = i;
for(int j = i + 1;j < arr.length;j++){
if (arr[minIndex] > arr[j]){
minIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
System.out.println("第"+(i+1)+"次選擇"+Arrays.toString(arr));
}
}表現最穩定的排序算法之一，因為無論什么數據進去都是O(n2)的時間復雜度，所以用到它的時候，數據規模越小越好。唯一的好處可能就是不占用額外的內存空間了吧。理論上講，選擇排序可能也是平時排序一般人想到的最多的排序方法了吧。
插入排序（Insertion-Sort）的算法描述是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。
一般來說，插入排序都采用in-place在數組上實現。具體算法描述如下：
（1）從第一個元素開始，該元素可以認為已經被排序；
（2）取出下一個元素，在已經排序的元素序列中從后向前掃描；
（3）如果該元素（已排序）大于新元素，將該元素移到下一位置；
（4）重復步驟3，直到找到已排序的元素小于或者等于新元素的位置；
（5）將新元素插入到該位置后；
（6）重復步驟2~5。
public static void insetSort(int[] arr){
for (int i = 0;i < arr.length;i++){
for (int j = i;j > 0;j--){
//配合交換的實現
if (arr[j] < arr[j-1]){
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}else {
break;
}
}
System.out.println("第"+(i+1)+"次插入"+Arrays.toString(arr));
}
}
插入排序在實現上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。
第一個突破O(n2)的排序算法，是簡單插入排序的改進版。它與插入排序的不同之處在于，它會優先比較距離較遠的元素。希爾排序又叫縮小增量排序。
先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，具體算法描述：
（1）選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1；
（2）按增量序列個數k，對序列進行k 趟排序；
（3）每趟排序，根據對應的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。
public static void ShellSort(int[] arr){
//定義增量序列，數組長度的每次折半
int incre = arr.length;
int n = 0;
while (true){
n += 1;
incre = incre / 2;
System.out.println("第"+n+"遍排序，增量序列為："+incre+Arrays.toString(arr));
// 根據增量拆分成不同的數組序列，拆分為incre組
for (int k = 0;k < incre; k++){ //對拆分的序列用插入排序
for (int i = k;i < arr.length;i += incre){
for (int j = i;j>k;j-=incre){
if (arr[j] < arr[j-incre]){
int temp = arr[j];
arr[j] = arr[j-incre];
arr[j-incre] = temp;
}else {
break;
}
}
}
}
if (incre == 1){
break;
}
}
}希爾排序的核心在于間隔序列的設定。既可以提前設定好間隔序列，也可以動態的定義間隔序列。動態定義間隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。
歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為2-路歸并。
（1）把長度為n的輸入序列分成兩個長度為n/2的子序列；
（2）對這兩個子序列分別采用歸并排序；
（3）將兩個排序好的子序列合并成一個最終的排序序列。
public static int[] MergeSort(int[] arr){
if (arr.length < 2) return arr;
int mid = arr.length / 2;
int[] left = Arrays.copyOfRange(arr,0,mid);
int[] right = Arrays.copyOfRange(arr,mid,arr.length);
return merge_sort(MergeSort(left),MergeSort(right));
}
public static int[] merge_sort(int[] left,int[] right){
int[] newarr = new int[left.length + right.length];
for (int index = 0,i = 0,j = 0;index < newarr.length;index++){
if (i >= left.length){
newarr[index] = right[j++];
}else if (j >= right.length){
newarr[index] = left[i++];
}else if (left[i] > right[j]){
newarr[index] = right[j++];
}else {
newarr[index] = left[i++];
}
}
return newarr;
}歸并排序是一種穩定的排序方法。和選擇排序一樣，歸并排序的性能不受輸入數據的影響，但表現比選擇排序好的多，因為始終都是O(nlogn）的時間復雜度。代價是需要額外的內存空間。
快速排序的基本思想：通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。
快速排序使用分治法來把一個串（list）分為兩個子串（sub-lists）。具體算法描述如下：
（1）從數列中挑出一個元素，稱為 “基準”（pivot）；
（2）重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個分區退出之后，該基準就處于數列的中間位置。這個稱為分區（partition）操作；
（3）遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。
public static void QuickSort(int[] arr,int left,int right){
if (left >= right){
return;
}
//選擇第一個數為key
int l = left,r = right;
int key = arr[left];
while (l < r){
//先從右邊找到第一個小于key的數
while (l < r && key <= arr[r]){
r--;
}
if (l < r){
arr[l] = arr[r];
l++;
}
//再從左邊起找到第一個大于key的值
while (l < r && key > arr[l]){
l++;
}
if (l<r){
arr[r] = arr[l];
r--;
}
arr[l] = key;
QuickSort(arr,left,l-1);
QuickSort(arr,l+1,right);
}
}
public static void QuickSortFunc(int[] arr){
int left = 0;
int right = arr.length-1;
QuickSort(arr,left,right);
}堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。
（1）將初始待排序關鍵字序列(R1,R2….Rn)構建成大頂堆，此堆為初始的無序區；
（2）將堆頂元素R[1]與最后一個元素R[n]交換，此時得到新的無序區(R1,R2,……Rn-1)和新的有序區(Rn),且滿足R[1,2…n-1]<=R[n]；
（3）由于交換后新的堆頂R[1]可能違反堆的性質，因此需要對當前無序區(R1,R2,……Rn-1)調整為新堆，然后再次將R[1]與無序區最后一個元素交換，得到新的無序區(R1,R2….Rn-2)和新的有序區(Rn-1,Rn)。不斷重復此過程直到有序區的元素個數為n-1，則整個排序過程完成。
public static void HeapSort(int[] arr){
//1、構建大項堆
for (int i = arr.length/2 - 1;i>=0;i--){
//從第一個非葉子節點從下至上，從右至左調整結構
adjustHeap(arr,i,arr.length);
}
//2、調整堆結構+交換堆頂元素與末尾元素
for(int j = arr.length-1;j>0;j--){
int temp = arr[0];
arr[0] = arr[j];
arr[j] = temp; //將堆頂元素與末尾元素進行交換
adjustHeap(arr,0,j); //重新進行堆調整
}
}
//調整堆
public static void adjustHeap(int[] arr,int i,int length){
//先取出當前元素i
int temp = arr[i];
//從i結點的左子結點開始，也就是2i+1處開始
for (int k = i*2 + 1;k<length;k=k*2+1){
//如果左子節點小于右子節點，k指向右子節點
if(k+1<length && arr[k] < arr[k+1]){
k++;
}
if (arr[k] > temp){//如果子節點大于父節點，將子節點值付給父節點（不用進行交換）
arr[i] = arr[k];
i = k;
}else {
break;
}
}
arr[i] = temp; //將temp值放到最終的位置
}計數排序不是基于比較的排序算法，其核心在于將輸入的數據值轉化為鍵存儲在額外開辟的數組空間中。 作為一種線性時間復雜度的排序，計數排序要求輸入的數據必須是有確定范圍的整數。
它的優勢在于在對于較小范圍內的整數排序。它的復雜度為Ο(n+k)（其中k是待排序數的范圍），快于任何比較排序算法，缺點就是非常消耗空間。很明顯，如果而且當O(k)>O(n*log(n))的時候其效率反而不如基于比較的排序，比如堆排序和歸并排序和快速排序。
要求：待排序數中最大數值不能太大。
（1）找出待排序的數組中最大和最小的元素；
（2）統計數組中每個值為i的元素出現的次數，存入數組C的第i項；
（3）對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）；
（4）反向填充目標數組：將每個元素i放在新數組的第C(i)項，每放一個元素就將C(i)減去1。
public static int[] CountSort(int[] arr){
//1、找出數組arr中的最大值
int k = arr[0];
for (int i = 1;i < arr.length;i++){
if (k < arr[i]){
k = arr[i];
}
}
//2、構造C數組，將A中每個元素對應C中的元素大小+1
int[] C = new int[k+1];
int sum = 0;
for (int i = 0;i < arr.length;i++){
C[arr[i]] +=1; //統計A中各元素個數，對應到C數組
}
//3、將C中每個i位置的元素大小改成C數組前i項和
for (int i=0;i<k+1; i++){
sum += C[i];
C[i] = sum;
}
//4、構造B數組，初始化一個和A同樣大小的數組B用于存儲排序后數組，然后倒序遍歷A中元素（后面會提到為何要倒序遍歷），通過查找C數組，將該元素放置到B中相應的位置，同時將C中對應的元素大小-1（表明已經放置了一個這樣大小的元素，下次再放同樣大小的元素，就要往前擠一個位置）
int[] B = new int[arr.length];
for (int i = arr.length-1;i>=0;i--){ //倒序遍歷A數組，構造B數組
B[C[arr[i]]-1] = arr[i]; //將A中該元素放到排序后數組B中指定的位置
C[arr[i]]--; //將C中該元素-1，方便存放下一個同樣大小的元素
}
//5、將排序好的數組B返回，完成排序
return B;
} 計數排序是一個穩定的排序算法。當輸入的元素是 n 個 0到 k 之間的整數時，時間復雜度是O(n+k)，空間復雜度也是O(n+k)，其排序速度快于任何比較排序算法。當k不是很大并且序列比較集中時，計數排序是一個很有效的排序算法。桶排序是計數排序的升級版。它利用了函數的映射關系，高效與否的關鍵就在于這個映射函數的確定。桶排序 (Bucket sort)的工作的原理：假設輸入數據服從均勻分布，將數據分到有限數量的桶里，每個桶再分別排序（有可能再使用別的排序算法或是以遞歸方式繼續使用桶排序進行排）。
要求：待排序數長度一致。
（1）設置一個定量的數組當作空桶；
（2）遍歷輸入數據，并且把數據一個一個放到對應的桶里去；
（3）對每個不是空的桶進行排序；
（4）從不是空的桶里把排好序的數據拼接起來。
算法實現邏輯
（1）找出待排序數組中的最大值max、最小值min
（2）我們使用 動態數組ArrayList 作為桶，桶里放的元素也用 ArrayList 存儲。桶的數量為(max-min)/arr.length+1
（3）遍歷數組 arr，計算每個元素 arr[i] 放的桶
（4）每個桶各自排序
（5）遍歷桶數組，把排序好的元素放進輸出數組
public static void BucketSort(int[] arr){
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int i = 0;i < arr.length;i++){
max = Math.max(max,arr[i]);
min = Math.min(min,arr[i]);
}
//計算桶數
int bucketNum = (max - min) / arr.length + 1;
ArrayList<ArrayList<Integer>> bunketArr = new ArrayList<>(bucketNum);
for (int i = 0;i < bucketNum;i++){
bunketArr.add(new ArrayList<Integer>());
}
for (int i = 0;i<arr.length;i++){
int num = (arr[i] - min) / (arr.length);
bunketArr.get(num).add(arr[i]);
}
//對每個桶進行排序
for (int i = 0;i < bunketArr.size();i++){
Collections.sort(bunketArr.get(i));
}
//將桶中排好序的數據依次復制回原數組
int index = 0;
for (int i = 0;i < bucketNum;i++){
for (int j = 0;j < bunketArr.get(i).size();j++){
arr[index++] = bunketArr.get(i).get(j);
}
}
}桶排序最好情況下使用線性時間O(n)，桶排序的時間復雜度，取決與對各個桶之間數據進行排序的時間復雜度，因為其它部分的時間復雜度都為O(n)。很顯然，桶劃分的越小，各個桶之間的數據越少，排序所用的時間也會越少。但相應的空間消耗就會增大。
基數排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位。有時候有些屬性是有優先級順序的，先按低優先級排序，再按高優先級排序。最后的次序就是高優先級高的在前，高優先級相同的低優先級高的在前。
基數排序屬于“分配式排序”（distribution sort），是非比較類線性時間排序的一種，又稱“桶子法”（bucket sort），顧名思義，它是透過鍵值的部分信息，將要排序的元素分配至某些“桶”中，藉以達到排序的作用。
基數排序（以×××為例），將×××10進制按每位拆分，然后從低位到高位依次比較各個位。主要分為兩個過程：
（1）分配，先從個位開始，根據位值(0-9)分別放到0~9號桶中（比如６4，個位為４，則放入４號桶中）；
（2）收集，再將放置在0~9號桶中的數據按順序放到數組中；
（3）重復（1）（2）過程，從個位到最高位（比如32位無符號整型最大數4294967296，最高位為第10位）。基數排序的方式可以采用LSD（Least Significant Digital）或MSD（Most Significant Digital），LSD的排序方式由鍵值的最右邊開始，而MSD則相反，由鍵值的最左邊開始。
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;
}基數排序基于分別排序，分別收集，所以是穩定的。但基數排序的性能比桶排序要略差，每一次關鍵字的桶分配都需要O(n)的時間復雜度，而且分配之后得到新的關鍵字序列又需要O(n)的時間復雜度。假如待排數據可以分為d個關鍵字，則基數排序的時間復雜度將是O(d*2n) ，當然d要遠遠小于n，因此基本上還是線性級別的。
基數排序的空間復雜度為O(n+k)，其中k為桶的數量。一般來說n>>k，因此額外空間需要大概n個左右。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
