溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
一、插入類排序
1.直接插入排序
思想：將第i個插入到前i-1個中的適當位置
時間復雜度：T(n) = O(n²)。
空間復雜度：S(n) = O(1)。
穩定性：穩定排序。
如果碰見一個和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。
所以，相等元素的前后順序沒有改變，從原無序序列出去的順序就是排好序后的順序，所以插入排序是穩定
哨兵有兩個作用：
① 進人查找(插入位置)循環之前，它保存了R[i]的副本，使不致于因記錄后移而丟失R[i]的內容；
② 它的主要作用是：在查找循環中"監視"下標變量j是否越界。一旦越界(即j=0)，因為R[0].可以和自己比較，循環判定條件不成立使得查找循環結束，從而避免了在該循環內的每一次均要檢測j是否越界(即省略了循環判定條件"j>=1")
public void insertSort(int[] array){
for(int i=1;i<array.length;i++)//第0位獨自作為有序數列，從第1位開始向后遍歷
{
if(array[i]<array[i-1])//0~i-1位為有序，若第i位小于i-1位，繼續尋位并插入，否則認為0~i位也是有序的，忽略此次循環，相當于continue
{
int temp=array[i];//保存第i位的值
int k = i - 1;
for(int j=k;j>=0 && temp<array[j];j--)//從第i-1位向前遍歷并移位，直至找到小于第i位值停止
{
array[j+1]=array[j];
k--;
}
array[k+1]=temp;//插入第i位的值
}
}
}
2.折半插入排序
思想：將數據插入到已經排好序的序列中，通過不斷與中間點比較大小來確定位置
時間復雜度：比較時的時間減為O(n㏒n)，但是移動元素的時間耗費未變，所以總是得時間復雜度還是O(n²)。
空間復雜度：S(n) = O(1)。
穩定性：穩定排序。
3.希爾排序
思想：又稱縮小增量排序法。把待排序序列分成若干較小的子序列，然后逐個使用直接插入排序法排序，最后再對一個較為有序的序列進行一次排序，主要是為了減少移動的次數，提高效率。原理應該就是從無序到漸漸有序，要比直接從無序到有序移動的次數會少一些。
時間復雜度：O(n的1.5次方)
空間復雜度：O(1)
穩定性：不穩定排序。{2,4,1,2}，2和1一組4和2一組，進行希爾排序，第一個2和最后一個2會發生位置上的變化。
public static void main(String [] args)
{
int[]a={49,38,65,97,76,13,27,49,78,34,12,64,1};
System.out.println("排序之前：");
for(int i=0;i<a.length;i++)
{
System.out.print(a[i]+" ");
}
//希爾排序
int d=a.length;
while(true)
{
d=d/2;
for(int x=0;x<d;x++)
{
for(int i=x+d;i<a.length;i=i+d)
{
int temp=a[i];
int j;
for(j=i-d;j>=0&&a[j]>temp;j=j-d)
{
a[j+d]=a[j];
}
a[j+d]=temp;
}
}
if(d==1)
{
break;
}
}
System.out.println();
System.out.println("排序之后：");
for(int i=0;i<a.length;i++)
{
System.out.print(a[i]+" ");
}
}
}
二、交換類排序
1.冒泡排序
時間復雜度：T(n) = O(n²)。
空間復雜度：S(n) = O(1)。
穩定性：穩定排序。
public class BubbleSort
{
public void sort(int[] a)
{
int temp = 0;
for (int i = a.length - 1; i > 0; --i)
{
for (int j = 0; j < i; ++j)
{
if (a[j + 1] < a[j])
{
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
}
2.快速排序
思想：對冒泡排序的改進，通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
時間復雜度：平均T(n) = O(n㏒n)，最壞O(n²)。
空間復雜度：S(n) = O(㏒n)。
穩定性：不穩定排序
首先把數組的第一個數拿出來做為一個key，在前后分別設置一個i,j做為標識，然后拿這個key對這個數組從后面往前遍歷，及j--，直到找到第一個小于這個key的那個數，然后交換這兩個值，交換完成后，我們拿著這個key要從i往后遍歷了，及i++;一直循環到i=j結束，當這里結束后，我們會發現大于這個key的值都會跑到這個key的后面
三、選擇類排序
1.簡單選擇排序
時間復雜度：T(n) = O(n²)。
空間復雜度：S(n) = O(1)。
穩定性：不穩定排序
思路：
1）從待排序的序列中，找到關鍵字最小的元素
2）如果最小的元素不在第一位，就和第一個元素互換位置
3）從余下的N-1個元素中，找到關鍵字最小的元素，重復 1）、2）步
public class SelectionSort {
public void selectionSort(int[] list) {
// 需要遍歷獲得最小值的次數
// 要注意一點，當要排序 N 個數，已經經過 N-1 次遍歷后，已經是有序數列
for (int i = 0; i < list.length - 1; i++) {
int temp = 0;
int index = i; // 用來保存最小值得索引
// 尋找第i個小的數值
for (int j = i + 1; j < list.length; j++) {
if (list[index] > list[j]) {
index = j;
}
}
// 將找到的第i個小的數值放在第i個位置上
temp = list[index];
list[index] = list[i];
list[i] = temp;
System.out.format("第 %d 趟:\t", i + 1);
printAll(list);
}
}
// 打印完整序列
public void printAll(int[] list) {
for (int value : list) {
System.out.print(value + "\t");
}
System.out.println();
}
public static void main(String[] args) {
// 初始化一個隨機序列
final int MAX_SIZE = 10;
int[] array = new int[MAX_SIZE];
Random random = new Random();
for (int i = 0; i < MAX_SIZE; i++) {
array[i] = random.nextInt(MAX_SIZE);
}
// 調用排序方法
SelectionSort selection = new SelectionSort();
System.out.print("排序前:\t");
selection.printAll(array);
selection.selectionSort(array);
System.out.print("排序后:\t");
selection.printAll(array);
}
}
2.樹形選擇排序
思想：為了減少比較次數，兩兩進行比較，得出的較小的值再兩兩比較，直至得出最小的輸出，然后在原來位置上置為∞，再進行比較。直至所有都輸出。
時間復雜度：T(n) = O(n㏒n)。
空間復雜度：較簡單選擇排序，增加了n-1個額外的存儲空間存放中間比較結果，就是樹形結構的所有根節點。S(n) = O(n)。
穩定性：穩定排序。
3.堆排序
【待】
四.、歸并排序
歸并排序：
思想：假設初始序列有n個記錄，首先將這n個記錄看成n個有序的子序列，每個子序列的長度為1，然后兩兩歸并，得到n/2向上取整個長度為2（n為奇數時，最后一個序列的長度為1）的有序子序列
在此基礎上，在對長度為2的有序子序列進行兩兩歸并，得到若干個長度為4的有序子序列
如此重復，直至得到一個長度為n的有序序列為止。
時間復雜度：T(n) = O(n㏒n)
空間復雜度：S(n) = O(n)
穩定性：穩定排序
public class MergeSort {
public static void merge(int[] a, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
int i = low;// 左指針
int j = mid + 1;// 右指針
int k = 0;
// 把較小的數先移到新數組中
while (i <= mid && j <= high) {
if (a[i] < a[j]) {
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
}
}
// 把左邊剩余的數移入數組
while (i <= mid) {
temp[k++] = a[i++];
}
// 把右邊邊剩余的數移入數組
while (j <= high) {
temp[k++] = a[j++];
}
// 把新數組中的數覆蓋nums數組
for (int k2 = 0; k2 < temp.length; k2++) {
a[k2 + low] = temp[k2];
}
}
public static void mergeSort(int[] a, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
// 左邊
mergeSort(a, low, mid);
// 右邊
mergeSort(a, mid + 1, high);
// 左右歸并
merge(a, low, mid, high);
System.out.println(Arrays.toString(a));
}
}
public static void main(String[] args) {
int a[] = { 51, 46, 20, 18, 65, 97, 82, 30, 77, 50 };
mergeSort(a, 0, a.length - 1);
System.out.println("排序結果：" + Arrays.toString(a));
}
}
五、分配類排序
1.多關鍵字排序：
【待】
2.鏈式基數排序：
思想：先分配，再收集，就是先按照一個次關鍵字收集一下，然后進行收集（第一個排序），然后再換一個關鍵字把新序列分配一下，然后再收集起來，又完成一次排序，這樣所有關鍵字分配收集完后，就完成了排序。
時間復雜度：T(n) = O( d ( n + rd ) )
空間復雜度：S(n) = O(rd)
穩定性：穩定排序
以上這篇詳細總結各種排序算法(Java實現)就是小編分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
