Java中常用的排序算法有哪些？都有什么特性？

一：排序的概念
1.排序：所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。
2.穩(wěn)定性：假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經(jīng)過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。
3.內部排序：數(shù)據(jù)元素全部放在內存中的排序。
4.外部排序：數(shù)據(jù)元素太多不能同時放在內存中，根據(jù)排序過程的要求不能在內外存之間移動數(shù)據(jù)的排序。

二：常見的排序方法：

三：各種排序算法的實現(xiàn)原理：`

（1）插入排序的基本思想：
直接插入排序是一種簡單的插入排序法，其基本思想是：把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列 。
**
當插入第i(i>=1)個元素時，前面的array[0],array[1],…,array[i-1]已經(jīng)排好序，此時用array[i]的排序碼與array[i-1],array[i-2],…的排序碼順序進行比較，找到插入位置即將array[i]插入，原來位置上的元素順序后移。

直接插入排序的特性總結：

1. 元素集合越接近有序，直接插入排序算法的時間效率越高
2. 時間復雜度：O(N^2)
3. 空間復雜度：O(1)，它是一種穩(wěn)定的排序算法
4. 穩(wěn)定性：穩(wěn)定

（2）希爾排序( 縮小增量排序 )
希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個整數(shù)，把待排序文件中所有記錄分成個組，所有距離為的記錄分在同一組內，并對每一組內的記錄進行排序。然后，取，重復上述分組和排序的工作。當?shù)竭_=1時，所有記錄在統(tǒng)一組內排好序。

希爾排序的特性總結：

1. 希爾排序是對直接插入排序的優(yōu)化。
2. 當gap > 1時都是預排序，目的是讓數(shù)組更接近于有序。當gap == 1時，數(shù)組已經(jīng)接近有序的了，這樣就
   會很快。這樣整體而言，可以達到優(yōu)化的效果。我們實現(xiàn)后可以進行性能測試的對比。
3. 希爾排序的時間復雜度不好計算，需要進行推導，推導出來平均時間復雜度： O(N^1.3—N^2）
4. 穩(wěn)定性：不穩(wěn)定

（3） 選擇排序
基本思想：
每一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的
數(shù)據(jù)元素排完 。
直接選擇排序:
在元素集合array[i]--array[n-1]中選擇關鍵碼最大(小)的數(shù)據(jù)元素
若它不是這組元素中的最后一個(第一個)元素，則將它與這組元素中的最后一個（第一個）元素交換
在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重復上述步驟，直到集合剩余1個元素

直接選擇排序的特性總結：

1. 直接選擇排序思考非常好理解，但是效率不是很好。實際中很少使用
2. 時間復雜度：O(N^2)
3. 空間復雜度：O(1)
4. 穩(wěn)定性：不穩(wěn)定

（4）堆排序
堆排序(Heapsort)是指利用堆積樹（堆）這種數(shù)據(jù)結構所設計的一種排序算法，它是選擇排序的一種。它是通過堆來進行選擇數(shù)據(jù)。需要注意的是排升序要建大堆，排降序建小堆。

堆排序使用堆來選數(shù)，效率就高了很多。

1. 時間復雜度：O(N*logN)
2. 空間復雜度：O(1)
3. 穩(wěn)定性：不穩(wěn)定

（5）冒泡排序
基本思想：所謂交換，就是根據(jù)序列中兩個記錄鍵值的比較結果來對換這兩個記錄在序列中的位置，交換排序的特點是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動。

冒泡排序的特性總結：

1. 冒泡排序是一種非常容易理解的排序
2. 時間復雜度：O(N^2)
3. 空間復雜度：O(1)
4. 穩(wěn)定性：穩(wěn)定

（6）快速排序
快速排序是Hoare于1962年提出的一種二叉樹結構的交換排序方法，其基本思想為：任取待排序元素序列中的某元素作為基準值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后最左右子序列重復該過程，直到所有元素都排列在相應位置上為止。


快速排序的特性總結：

1. 快速排序整體的綜合性能和使用場景都是比較好的，所以才敢叫快速排序
2. 時間復雜度：O(N*logN)
3. 空間復雜度：O(logN)
4. 穩(wěn)定性：不穩(wěn)定

（7）歸并排序
基本思想：
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide andConquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。

歸并排序的特性總結：

1. 歸并的缺點在于需要O(N)的空間復雜度，歸并排序的思考更多的是解決在磁盤中的外排序問題。
2. 時間復雜度：O(N*logN)
3. 空間復雜度：O(N)
4. 穩(wěn)定性：穩(wěn)定

四：各種排序算法的時間復雜度，空間復雜度以及穩(wěn)定性的比較。