排序演算法大彙總-選擇、插入、希爾、歸併、快速、堆排
選擇排序
這是排序演算法是最簡單的一種，過程是這樣的：
首先找到陣列中最小的那個元素，其次將它和陣列的第一個元素交換位置（如果第一個元素就是最小元素那麼他就和自己交換）。再次，在剩下的元素中找到最小的元素，將它與陣列的第二個元素交換位置。如此往復，直到將整個陣列排序
這種方法叫做選擇排序，因為他在不斷選擇剩餘元素中的最小者。
對於長度為N的陣列，選擇排序大概需要N^2/2次比較和N次交換。
特點：
- 執行時間和輸入無關。
- 資料移動是最少的。
程式碼示例
package sort;
import java.util.Scanner;
public class Select {
public static void sort(Comparable[] a) {
int N=a.length;
for (int i = 0; i <N; i++) {
int min=i;
for (int j = i + 1; j < a.length; j++) {
if (less(a[j] ,a[min]))
{
System.out.println(less(a[j] ,a[min]));
min=j;
}
}
exch(a,i,min);
}
}
public static boolean less(Comparable v, Comparable w) {
return v.compareTo(w)<0;
}
public static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j]=t;
}
public static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}
public static boolean isSorted(Comparable[] a) {
for (int i = 1; i < a.length; i++)
if (less(a[i], a[i - 1]))
return false;
return true;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
StringBuffer stringBuffer = new StringBuffer();
String[] a;
stringBuffer.append(scanner.nextLine());
a = stringBuffer.toString().split(",");
show(a);
System.out.println("********************");
sort(a);
assert isSorted(a);
show(a);
}
}
注意事項
上述中Comparable介面的物件進行排序，上述程式碼是對String型別的物件進行的排序。因此如果輸入的是同樣的位數的整數，上述程式碼可是正確實現排序。
例如 輸入為：12，43，21，42，25
但是如果輸入的整數的位數是不一致的，則得不到正確的結果
例如 輸入為：12，43，211，42，25
出現上述問題的原因在於我們是對String型別進行的排序，String型別排序的依據是ASCii碼錶。
當然如果將上述的陣列換成了int型別，那麼在輸入數值的時候就能夠得到正確結果了
插入排序
我們在打撲克牌的時候用的插牌就可以看作是插入排序，將每一張摸到的牌插入到其他已經有序的牌中的適當位置。
計算機中為了給插入的元素騰出空間，需要將剩餘所有元素在插入之前都向右移動一位。
插入排序所需要的時間取決於輸入中元素的初始順序。平均情況下插入排序需要~N^ 2/4次比較和~N^ 2/4次交換。最壞情況下需要~N^ 2/2次比較和~N^2/2次交換，最好情況下需要N-1次比較和0次交換。
程式碼示例
package sort;
import java.util.Scanner;
public class Insert {
public static void sort(Integer[] a) {
int N=a.length;
for (int i = 1; i < N; i++) {
for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
exch(a,j,j-1);
}
}
}
public static boolean less(Integer v, Integer w) {
return v.compareTo(w)<0;
}
public static void exch(Integer[] a, int i, int j) {
Integer t = a[i];
a[i] = a[j];
a[j]=t;
}
public static void show(Integer[] a) {
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}
public static boolean isSorted(Integer[] a) {
for (int i = 1; i < a.length; i++)
if (less(a[i], a[i - 1]))
return false;
return true;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
StringBuffer stringBuffer = new StringBuffer();
String[] b;
stringBuffer.append(scanner.nextLine());
b = stringBuffer.toString().split(",");
Integer[] a=new Integer[b.length];
for (int i = 0; i < b.length; i++) {
a[i] = Integer.parseInt(b[i]);
}
show(a);
System.out.println("********************");
sort(a);
assert isSorted(a);
show(a);
}
}
注意
倒置：指的是陣列中的兩個順序顛倒的元素。
如果陣列中倒置的數量小於陣列大小的某個倍數，則稱這個陣列是部分有序的。
以下幾種典型的部分有序的陣列：
- 陣列中每個元素距離他的最終位置都不遠
- 一個有序的大陣列接一個小陣列
- 陣列中只有幾個元素的位置不正確
插入排序對上述有序陣列很有效
當倒置的數量很少時，插入排序很可能比本章中的其他任何演算法都要快。
插入排序需要的交換操作和陣列中倒置的數量相同，需要的比較次數大於等於倒置的數量，小於等於倒置的數量加上陣列的大小再減一。
希爾排序
希爾排序為了加快速度簡單的改進了插入排序，交換不相鄰的元素以對陣列的區域性進行排序，並最終用插入排序將區域性有序的陣列排序。
思想：
使陣列中任意間隔為h的元素都是有序的，這樣的陣列被稱為h有序陣列。換句話說，一個h有序陣列就是h個互相獨立的有序陣列編織在一起組成的一個數組。
image.png
可以藉助上圖幫助理解一下。
程式碼示例
package sort;
import java.util.Scanner;
public class Shell {
public static void sort(Integer[] a) {
int N=a.length;
int h=1;
while (h < N / 3) {
h = 3 * h + 1;
}
while (h >= 1) {
for (int i = h; i < N; i++) {
for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
exch(a,j,j-h);
}
}
h=h/3;
}
}
public static boolean less(Integer v, Integer w) {
return v.compareTo(w)<0;
}
public static void exch(Integer[] a, int i, int j) {
Integer t = a[i];
a[i] = a[j];
a[j]=t;
}
public static void show(Integer[] a) {
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}
public static boolean isSorted(Integer[] a) {
for (int i = 1; i < a.length; i++)
if (less(a[i], a[i - 1]))
return false;
return true;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
StringBuffer stringBuffer = new StringBuffer();
String[] b;
stringBuffer.append(scanner.nextLine());
b = stringBuffer.toString().split(",");
Integer[] a=new Integer[b.length];
for (int i = 0; i < b.length; i++) {
a[i] = Integer.parseInt(b[i]);
}
show(a);
System.out.println("********************");
sort(a);
assert isSorted(a);
show(a);
}
}
** 至今為止，世界上還沒能透徹理解希爾排序的效能**
對於希爾排序，應該看更多的東西來加深理解，現在理解的還不是特別透徹，只是知道了他是如何進行的排序。