腳本之家服務(wù)器常用軟件

快捷導(dǎo)航

詳細總結(jié)各種排序算法(Java實現(xiàn))

更新時間：2017年09月12日 08:48:17 作者：LWJJJ

下面小編就為大家?guī)硪黄敿毧偨Y(jié)各種排序算法(Java實現(xiàn))。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧

一、插入類排序

1.直接插入排序

思想：將第i個插入到前i-1個中的適當(dāng)位置

時間復(fù)雜度：T(n) = O(n²)。

空間復(fù)雜度：S(n) = O(1)。

穩(wěn)定性：穩(wěn)定排序。

如果碰見一個和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。

所以，相等元素的前后順序沒有改變，從原無序序列出去的順序就是排好序后的順序，所以插入排序是穩(wěn)定

哨兵有兩個作用：

① 進人查找(插入位置)循環(huán)之前，它保存了R[i]的副本，使不致于因記錄后移而丟失R[i]的內(nèi)容；

② 它的主要作用是：在查找循環(huán)中"監(jiān)視"下標(biāo)變量j是否越界。一旦越界(即j=0)，因為R[0].可以和自己比較，循環(huán)判定條件不成立使得查找循環(huán)結(jié)束，從而避免了在該循環(huán)內(nèi)的每一次均要檢測j是否越界(即省略了循環(huán)判定條件"j>=1")

public void insertSort(int[] array){
  for(int i=1;i<array.length;i++)//第0位獨自作為有序數(shù)列，從第1位開始向后遍歷
  {
   if(array[i]<array[i-1])//0~i-1位為有序，若第i位小于i-1位，繼續(xù)尋位并插入，否則認為0~i位也是有序的，忽略此次循環(huán)，相當(dāng)于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.折半插入排序

思想：將數(shù)據(jù)插入到已經(jīng)排好序的序列中，通過不斷與中間點比較大小來確定位置

時間復(fù)雜度：比較時的時間減為O(n㏒n)，但是移動元素的時間耗費未變，所以總是得時間復(fù)雜度還是O(n²)。

空間復(fù)雜度：S(n) = O(1)。

穩(wěn)定性：穩(wěn)定排序。

3.希爾排序

思想：又稱縮小增量排序法。把待排序序列分成若干較小的子序列，然后逐個使用直接插入排序法排序，最后再對一個較為有序的序列進行一次排序，主要是為了減少移動的次數(shù)，提高效率。原理應(yīng)該就是從無序到漸漸有序，要比直接從無序到有序移動的次數(shù)會少一些。

時間復(fù)雜度：O(n的1.5次方)

空間復(fù)雜度：O(1)

穩(wěn)定性：不穩(wěn)定排序。{2,4,1,2}，2和1一組4和2一組，進行希爾排序，第一個2和最后一個2會發(fā)生位置上的變化。

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.冒泡排序

時間復(fù)雜度：T(n) = O(n²)。

空間復(fù)雜度：S(n) = O(1)。

穩(wěn)定性：穩(wěn)定排序。

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.快速排序

思想：對冒泡排序的改進，通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。

時間復(fù)雜度：平均T(n) = O(n㏒n)，最壞O(n²)。

空間復(fù)雜度：S(n) = O(㏒n)。

穩(wěn)定性：不穩(wěn)定排序

首先把數(shù)組的第一個數(shù)拿出來做為一個key，在前后分別設(shè)置一個i,j做為標(biāo)識，然后拿這個key對這個數(shù)組從后面往前遍歷，及j--，直到找到第一個小于這個key的那個數(shù)，然后交換這兩個值，交換完成后，我們拿著這個key要從i往后遍歷了，及i++;一直循環(huán)到i=j結(jié)束，當(dāng)這里結(jié)束后，我們會發(fā)現(xiàn)大于這個key的值都會跑到這個key的后面

三、選擇類排序

1.簡單選擇排序

時間復(fù)雜度：T(n) = O(n²)。

空間復(fù)雜度：S(n) = O(1)。

穩(wěn)定性：不穩(wěn)定排序

思路：

1）從待排序的序列中，找到關(guān)鍵字最小的元素

2）如果最小的元素不在第一位，就和第一個元素互換位置

3）從余下的N-1個元素中，找到關(guān)鍵字最小的元素，重復(fù) 1）、2）步

public class SelectionSort {
 public void selectionSort(int[] list) {
  // 需要遍歷獲得最小值的次數(shù)
  // 要注意一點，當(dāng)要排序 N 個數(shù)，已經(jīng)經(jīng)過 N-1 次遍歷后，已經(jīng)是有序數(shù)列
  for (int i = 0; i < list.length - 1; i++) {
   int temp = 0;
   int index = i; // 用來保存最小值得索引
   // 尋找第i個小的數(shù)值
   for (int j = i + 1; j < list.length; j++) {
    if (list[index] > list[j]) {
     index = j;
    }
   }
   // 將找到的第i個小的數(shù)值放在第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);
  }
  // 調(diào)用排序方法
  SelectionSort selection = new SelectionSort();
  System.out.print("排序前:\t");
  selection.printAll(array);
  selection.selectionSort(array);
  System.out.print("排序后:\t");
  selection.printAll(array);
 }
}

2.樹形選擇排序

思想：為了減少比較次數(shù)，兩兩進行比較，得出的較小的值再兩兩比較，直至得出最小的輸出，然后在原來位置上置為∞，再進行比較。直至所有都輸出。

時間復(fù)雜度：T(n) = O(n㏒n)。

空間復(fù)雜度：較簡單選擇排序，增加了n-1個額外的存儲空間存放中間比較結(jié)果，就是樹形結(jié)構(gòu)的所有根節(jié)點。S(n) = O(n)。

穩(wěn)定性：穩(wěn)定排序。

3.堆排序

【待】

四.、歸并排序

歸并排序：

思想：假設(shè)初始序列有n個記錄，首先將這n個記錄看成n個有序的子序列，每個子序列的長度為1，然后兩兩歸并，得到n/2向上取整個長度為2（n為奇數(shù)時，最后一個序列的長度為1）的有序子序列

在此基礎(chǔ)上，在對長度為2的有序子序列進行兩兩歸并，得到若干個長度為4的有序子序列　　

如此重復(fù)，直至得到一個長度為n的有序序列為止。

時間復(fù)雜度：T(n) = O(n㏒n)

空間復(fù)雜度：S(n) = O(n)

穩(wěn)定性：穩(wě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;
  // 把較小的數(shù)先移到新數(shù)組中
  while (i <= mid && j <= high) {
   if (a[i] < a[j]) {
    temp[k++] = a[i++];
   } else {
    temp[k++] = a[j++];
   }
  }
  // 把左邊剩余的數(shù)移入數(shù)組
  while (i <= mid) {
   temp[k++] = a[i++];
  }
  // 把右邊邊剩余的數(shù)移入數(shù)組
  while (j <= high) {
   temp[k++] = a[j++];
  }
  // 把新數(shù)組中的數(shù)覆蓋nums數(shù)組
  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("排序結(jié)果：" + Arrays.toString(a));
 }
}

五、分配類排序

1.多關(guān)鍵字排序：

【待】

2.鏈式基數(shù)排序：

思想：先分配，再收集，就是先按照一個次關(guān)鍵字收集一下，然后進行收集（第一個排序），然后再換一個關(guān)鍵字把新序列分配一下，然后再收集起來，又完成一次排序，這樣所有關(guān)鍵字分配收集完后，就完成了排序。

時間復(fù)雜度：T(n) = O( d ( n + rd ) )

空間復(fù)雜度：S(n) = O(rd)

穩(wěn)定性：穩(wěn)定排序

以上這篇詳細總結(jié)各種排序算法(Java實現(xiàn))就是小編分享給大家的全部內(nèi)容了，希望能給大家一個參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: