Java中都有哪些排序算法

今天就跟大家聊聊有關Java中都有哪些排序算法，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結了以下內(nèi)容，希望大家根據(jù)這篇文章可以有所收獲。

排序

<p _hover-ignore="1" white-space:normal;background-color:#FFFFFF;"> 排序是計算機內(nèi)經(jīng)常進行的一種操作，其目的是將一組“無序”的記錄序列調(diào)整為“有序”的記錄序列。分內(nèi)部排序和外部排序，若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內(nèi)部排序。反之，若參加排序的記錄數(shù)量很大，整個序列的排序過程不可能在內(nèi)存中完成，則稱此類排序問題為外部排序。內(nèi)部排序的過程是一個逐步擴大記錄的有序序列長度的過程。

概念

將雜亂無章的數(shù)據(jù)元素，通過一定的方法按關鍵字順序排列的過程叫做排序。

常見排序算法

快速排序、希爾排序、堆排序、直接選擇排序不是穩(wěn)定的排序算法，而基數(shù)排序、冒泡排序、直接插入排序、折半插入排序、歸并排序是穩(wěn)定的排序算法。

分類

穩(wěn)定排序：假設在待排序的文件中，存在兩個或兩個以上的記錄具有相同的關鍵字，在 用某種排序法排序后，若這些相同關鍵字的元素的相對次序仍然不變，則這種排序方法 是穩(wěn)定的。其中冒泡，插入，基數(shù)，歸并屬于穩(wěn)定排序，選擇，快速，希爾，堆屬于不穩(wěn)定排序。

就地排序：若排序算法所需的輔助空間并不依賴于問題的規(guī)模n，即輔助空間為O(1)， 則稱為就地排序。

排序算法

冒泡排序

持續(xù)比較相鄰元素，大的挪到后面，因此大的會逐步往后挪，故稱之為冒泡。 復雜度分析：平均情況與最壞情況均為 O(n^2), 使用了 temp 作為臨時交換變量，空間復雜度為 O(1)

堆排序

堆排序的是集合了插入排序的單數(shù)組操作，又有歸并排序的時間復雜度，完美的結合了2者的優(yōu)點。

直接插入排序

直接插入排序是一種最簡單的排序方法，它的基本操作是將一個記錄插入到已排好的有序的表中，從而得到一個新的、記錄數(shù)增1的有序表。當前元素的前面元素均為有序，要插入時，從當前元素的左邊開始往前找(從后往前找)，比當前元素大的元素均往右移一個位置，最后把當前元素放在它應該呆的位置就行了。

歸并排序

歸并排序(Merge Sort)與快速排序思想類似：將待排序數(shù)據(jù)分成兩部分，繼續(xù)將兩個子部分進行遞歸的歸并排序;然后將已經(jīng)有序的兩個子部分進行合并，最終完成排序。

其時間復雜度與快速排序均為O(nlogn)，但是歸并排序除了遞歸調(diào)用間接使用了輔助空間棧，還需要額外的O(n)空間進行臨時存儲。從此角度歸并排序略遜于快速排序，但是歸并排序是一種穩(wěn)定的排序算法，快速排序則不然。

所謂穩(wěn)定排序，表示對于具有相同值的多個元素，其間的先后順序保持不變。對于基本數(shù)據(jù)類型而言，一個排序算法是否穩(wěn)定，影響很小，但是對于結構體數(shù)組，穩(wěn)定排序就十分重要。

快速排序

通過一趟排序將要排序的數(shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。

直接選擇排序

所謂選擇排序，就是每次找到未排序中最小的(最大的也行)元素的位置，找到后與該位置與未排序序列的第一個元素交換值，直到該序列成為有序序列。

初始狀態(tài)整個序列為無序序列，每次交換都使有序序列的長度加一，無序序列的起始位置后移一位。選擇排序的平均時間復雜度為O(n^2)，且選擇排序相對不穩(wěn)定。

希爾排序

Shellsort是最古老的排序算法之一，該算法以其發(fā)明者Donald L. Shell的名字命名。

在ShellSort排序算法之前的算法時間復雜度基本都是O(n2)O(n2)，該算法是突破這個時間復雜度的第一批算法之一。

看完上述內(nèi)容，你們對Java中都有哪些排序算法有進一步的了解嗎？如果還想了解更多知識或者相關內(nèi)容，請關注億速云行業(yè)資訊頻道，感謝大家的支持。