各種排序演算法實現原理和程式碼及適用範圍總結
排序演算法可以分為內部排序和外部排序，內部排序又可以分為插入類、交換類、選擇類、歸併類排序，歸併排序通常也應用於外部排序，但採用的是多路歸併排序。
內部排序有：
插入類排序：直接插入、折半插入、希爾排序；
交換類排序：冒泡排序、快速排序；
選擇類排序：簡單（直接）選擇排序、堆排序；
歸併類排序：歸併排序；
外部排序：需要在內外存之間多次交換數據才能進行；
1、直接插入排序
基本思路：L(i)為待排序表中一個元素，前一子序列 L[1…i-1]為有序子序列，後一子序列 L[i+1…n]為無序子序列，為了實現將元素 L(i)插入到已有序的子序列 L[1…i-1]中，需進行以下操作：
1）查找出 L(i)在 L[1…i-1]中的插入位置 k；
2）將 L[k…i-1]中所有元素全部後移一個位置；
3）將 L(i)複製到 L(k)。
過程：就是將後面無序子序列中的每一個元素依次往前面有序子序列中插入到相應的位置，初始時將待排序列的第一個元素作為有序子序列的一個元素。
Java 程式碼實現：
import java.util.Scanner;
//用 Java 實現直接插入排序
public class DirectInsertSort {
public static void InsertSort(int A[],int n){
int k,j;
for(int i=1;i<n;i++){
if(A[i]<A[i-1]){
k = A[i];
for(j=i-1;j>=0 && k<A[j];j–){
A[j+1]=A[j];
}
A[j+1]=k;
}
}
}
public static void main(String [] args){
int A[] = new int[10];
System.out.println(“請輸入數值插入到已聲明的數組中：”);
Scanner reader = new Scanner(System.in);
for(int i = 0;i<A.length;i++)
{
//System.out.println(“請輸入第”+(i+1)+”個數字：”);
int In = reader.nextInt();
A[i] = In;
}
InsertSort(A,A.length);
System.out.println(“排序後的數組元素序列為：”);
for(int i = 0;i<A.length;i++){
System.out.print(A[i]+” “);
}
}
}
時間複雜度：最好情況下 O(n),表中元素基本有序，每插入一個元素，都只需比較一次而不用移動元素，最壞情況和平均情況下都是 O(n^2),最壞情況是表中元素基本逆序，平均情況下指待排序表中元素是隨機的。
空間的複雜度：O(1)
直接插入排序是一個穩定的排序方法。
2、折半插入排序
基本思路：上面的直接插入排序演算法在每趟插入的過程中都進行了兩項工作：1）從前面的字表中 查找出待插入元素應該被插入的位置；2)給插入位置騰出空間，將待插入元素複製到表中的插入位置；邊比較邊移動元素。而折半插入排序是將比較和移動操作分離開來，先折半查找出元素的待插入位置，在統一移動待插入位置之後的所有元素，當採用順序存貯的線性表且數據量較小時可以採用折半插入排序演算法，另一方面查找有序子表時採用折半查找來實現。
Java 程式碼實現：
import java.util.Scanner;
public class ZheBanInsertSort {
public static void ZheBan_InsertSort(int A[],int n){
int i,j,k,low,high,mid;
for(i=1;i<n;i++){
k = A[i];
low = 0;high = i-1;
while(low<=high){//折半查找，確定查找位置
mid = (low+high)/2;
if(k<=A[mid])
high = mid-1;
else
low = mid+1;
}
for(j=i-1;j>=high+1;j–){
A[j+1] = A[j];//統一後移元素，空出插入位置
}
A[high+1] = k;
}
}
public static void main(String [] args){
int A[] = new int[10];
System.out.println(“請輸入數值插入到已聲明的數組中：”);
Scanner reader = new Scanner(System.in);
for(int i = 0;i<A.length;i++)
{
//System.out.println(“請輸入第”+(i+1)+”個數字：”);
int In = reader.nextInt();
A[i] = In;
}
ZheBan_InsertSort(A,A.length);
System.out.println(“排序後的數組元素序列為：”);
for(int i = 0;i<A.length;i++){
System.out.print(A[i]+” “);
}
}
}
時間複雜度：折半插入排序僅僅是減少了比較元素的次數，約為 O(nlogn),與待排序表的初始狀態無關，僅取決於表中的元素個數 n，而元素的移動次數沒有改變，仍為 O(n^2)，因此時間複雜度為 O(nlogn)+O(n^2)=O(n^2)。
空間複雜度：O(1)
折半插入排序是一個穩定的排序方法。
3、希爾排序
直接插入排序演算法適用於基本有序的排序表和數據量不大的排序表，基於這兩點提出希爾排序，或稱為縮小增量排序。
基本思路：先將待排序表分割成若干個形如 L[i,i+d,i+2d,…i+kd]的「特殊」子表，分別進行直接插入排序，當整個表中元素局部基本有序時再對全體記錄進行一次直接插入排序（最後一趟）。先取一個小於 n 的步長 d1,把表中全部記錄分成 d1 個組，所有距離為 d1 的倍數的記錄放在同一個組中，在各組中進行直接插入排序；然後取第二個步長 d2<d1，重複上述過程，直到所取到的 dt=1，即所有記錄已放在同一組中，在進行直接插入排序，此時已經具有較好的局部有序性，因此可以很快得到排序結果。
Java 程式碼如下：
import java.util.Scanner;
public class SellSort {
public static void ShellSort1(int A[],int n){
int i,j,k,dk=n/2;
while(dk>0){
for(i = dk+1;i<n;i++){
k = A[i];
j = i-dk;
while(j>=0&&k<A[j]){
A[j+dk] = A[j];
j = j-dk;
}
A[j+dk] = k;
}
dk = dk/2;
}
}
public static void ShellSort2(int A[],int n){
int i,j,k,dk;
for(dk=n/2;dk>=1;dk=dk/2){
for(i=dk+1;i<n;i++){
if(A[i]<A[i-dk]){
k = A[i];
for(j=i-dk;j>=0&&k<A[j];j=j-dk)
A[j+dk] = A[j];
A[j+dk] = k;
}
}
}
}
public static void main(String [] args){
int A[] = new int[10];
System.out.println(“請輸入數值插入到已聲明的數組中：”);
Scanner reader = new Scanner(System.in);
for(int i = 0;i<A.length;i++)
{
//System.out.println(“請輸入第”+(i+1)+”個數字：”);
int In = reader.nextInt();
A[i] = In;
}
ShellSort1(A,A.length);
//ShellSort2(A,A.length);
System.out.println(“排序後的數組元素序列為：”);
for(int i = 0;i<A.length;i++){
System.out.print(A[i]+” “);
}
}
}
時間複雜度：最好情況下為 O(n^1.3)，最壞情況下為 O(n^2)，平均情況下為 O(nlogn)~O(n^2)
空間複雜度：O(1)
希爾排序是一個不穩定的排序演算法，僅適用於線性表為順序存儲的情況
4、冒泡排序
基本思路：假設待排序表長為 n，從前往後或從後往前兩兩比較相鄰元素值，若為逆序，則交換兩者的順序，直到序列比較完，稱為一趟冒泡排序，共進行 n-1 趟冒泡過程。
這裡例舉三個冒泡排序過程，他們移動和交換元素的次數都不相同：
//第一種冒泡排序演算法,性能最差的一種
public static void BubbleSort1(int a[],int n){
int i,j;
for(i=0;i<n;i++){//表示 n 次排序過程
for(j=1;j<n;j++){//一趟冒泡過程
if(a[j-1]>a[j]){//前面的數據大於後面的數據就交換
int temp;
temp = a[j-1];
a[j-1] = a[j];
a[j] = temp;
}
}
}
}
//第二種冒泡排序演算法，減少了比較數據的次數
public static void BubbleSort2(int a[],int n){
int i,j;
for(i=0;i<n;i++){//表示 n 次排序過程
for(j=1;j<n-i;j++){//一趟冒泡過程
if(a[j-1]>a[j]){//前面的數據大於後面的數據就交換
int temp;
temp = a[j-1];
a[j-1] = a[j];
a[j] = temp;
}
}
}
}
//第三種冒泡排序演算法
public static void BubbleSort3(int a[],int n){
Boolean exchange = true;
int k = n-1;
while(exchange){
exchange = false;
for(int i=0;i<k;i++){
if(a[i]>a[i+1]){
int temp;
temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
exchange = true;//交換後就置為 true
}
}
k = k-1;//最大值交換到最終位置，相應減 1，減少了比較和交換次數
}
}
數據驗證程式碼：
public static void main(String args[]){
Scanner in = new Scanner(System.in);
System.out.println(“請從控制台輸入數據：”);
//int a[]={10,56,32,98,75,12,3,59,87,16},i=0;
String str[] = in.nextLine().split(” “);//字元串以空格分隔，得到的是字元串
int num[] = new int[str.length];//創建並初始化數組，用於存儲整形數據的數組，將字元串轉為整型數據後存入 num 數組中
for(int i=0;i<str.length;i++){
num[i] = Integer.parseInt(String.valueOf(str[i]));
}
//while(in.hasNextInt()){
// a[i++]=in.nextInt();
//BubbleSort1(a,a.length);
//}
System.out.println(“排序前轉為數組中的整型數據為：”);
for(int i=0;i<num.length;i++){
System.out.print(num[i]+” “);
}
System.out.println(“\n 使用三種冒泡排序演算法排序後的結果為”);
int[] num_Bubble1 = num;
int[] num_Bubble2 = num;
BubbleSort1(num_Bubble1,num_Bubble1.length);//使用冒泡排序演算法 1 對數據進行排序
System.out.println(“排序後的數組中的數據為：”);
for(int i=0;i<num_Bubble1.length;i++){
System.out.print(num_Bubble1[i]+” “);
}
BubbleSort2(num_Bubble2,num_Bubble2.length);//使用冒泡排序演算法 2 對數據進行排序
System.out.println(“\n 排序後的數組中的數據為：”);
for(int i=0;i<num_Bubble2.length;i++){
System.out.print(num_Bubble2[i]+” “);
}
BubbleSort3(num_Bubble2,num_Bubble2.length);//使用冒泡排序演算法 2 對數據進行排序
System.out.println(“\n 排序後的數組中的數據為：”);
for(int i=0;i<num.length;i++){
System.out.print(num[i]+” “);
}
}
時間複雜度：最好情況下（初始序列基本有序時）O(n)，平均情況下和最壞情況下都為 O(n^2)
空間複雜度：O(1)
冒泡排序是一個穩定的排序演算法
5、快速排序
基本思路：快速排序是對冒泡排序的一種改進，基本思想是基於分治法的：在待排序表 L[1…n]中任取一個元素（一般是待排序表的第一個元素）作為基準，通過一趟排序將待排序表劃分為獨立的兩部分 L[1…k-1]和 L[k+1…n]，使得 L[1…k-1]中的所有元素小於基準元素，L[k+1…n]中的所有元素大於或等於基準元素，基準元素放在了最終位置 L[k]上，這個過程稱為一趟快速排序，後分別遞歸地對兩個子表重複上述過程，直至每部分內只有一個元素或空為止，此時所有元素放在了其最終位置上。
Java 程式碼如下：
import java.util.Scanner;
public class QuickSort {
//基準劃分操作過程
public static int Partition(int a[],int low,int high){
int pivot = a[low];//將當前表中第一個元素設為基準值，對錶進行劃分
while(low<high){
while(low<high && a[high]>=pivot)
high–;
if(low<high){
a[low] = a[high];
low++;
}
while(low<high && a[low]<pivot)
low++;
if(low<high){
a[high] = a[low];
high–;
}
}
a[low] = pivot;
return low;
}
//快速排序演算法的遞歸過程
public static void QuickSort_recurrence(int a[],int low,int high){
if(low<high){//遞歸跳出條件
//Partition（）屬於劃分操作，將表 a[]劃分為滿足小於基準值的所有數據在左邊大於基準值的所有數據在右邊的兩個子表
int pivotPosition = Partition(a,low,high);//基於基準值劃分兩部分
QuickSort_recurrence(a,low,pivotPosition-1);//依次對兩個子表遞歸排序
QuickSort_recurrence(a,pivotPosition+1,high);
}
}
public static void main(String args[]){
System.out.println(“請輸入待排序的數據到數組中：”);
Scanner sc = new Scanner(System.in);
String str[] = sc.nextLine().split(” “);//以空格相隔輸入各個數據
int num[] = new int[str.length];//數組創建及初始化
for(int i=0;i<str.length;i++){
num[i] = Integer.parseInt(String.valueOf(str[i]));
}
QuickSort_recurrence(num,0,num.length-1);//調用快速排序演算法進行排序
System.out.println(“排序後的結果為：”);
for(int i=0;i<num.length;i++){
System.out.print(num[i]+” “);
}
}
}
時間複雜度：最好情況下和平均情況下（數據元素隨機分布）為 O(nlogn),最壞情況下（待排序表基本有序或基本逆序時）為 O(n^2)
空間複雜度：平均情況下為 O(logn)，最壞情況下為 O(n)
快速排序是所有內部排序演算法中平均性能最優的排序演算法，適用於元素隨機分布的情況，是一個不穩定的排序演算法。
6、簡單（直接）選擇排序
基本思路：第 i 趟在後面 n-i+1（i=1,2,3,…n-1）個待排序元素中選取關鍵字最小的元素，作為前面有序子序列的第 i 個元素，直到第 n-1 趟做完，待排序元素只剩下一個，就不用再選了，假設待排序表為 L[1…n]，第 i 趟排序即從 L[i…n]中選擇關鍵字最小的元素與 L(i)交換，每一趟排序可以確定一個元素的最終位置，進行 n-1 趟就使排序表有序。
Java 程式碼如下：
import java.util.Scanner;
//簡單（直接）選擇排序
public class Direct_EasySelectSort {
public static void Direct_Easy_SelectSort(int a[],int n){
//對錶 a 做簡單選擇排序，從 0 存儲位置開始排序
for(int i=0;i<n-1;i++){//進行 n-1 趟
int min = i;
for(int j=i+1;j<n;j++){//在 a[i+1…n]數組中選擇關鍵字最小的元素
if(a[j]<a[min])
min = j;//找出關鍵字最小的元素，記錄它的數組下標
}
if(min!=i){//選擇最小元素值與 a[i]元素交換位置
int temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
}
public static void main(String args[]){
System.out.println(“請輸入待排序的數據到數組中：”);
Scanner sc = new Scanner(System.in);
String str[] = sc.nextLine().split(” “);
int num[] = new int[str.length];
for(int i=0;i<num.length;i++){
num[i] = Integer.parseInt(String.valueOf(str[i]));
}
Direct_Easy_SelectSort(num,num.length);//調用簡單選擇排序演算法對數組中的數據進行排序
System.out.println(“排序後的數組元素為：”);
for(int i=0;i<num.length;i++){
System.out.print(num[i]+” “);
}
}
}
時間複雜度：由於元素間比較的次數與序列的初始狀態無關，始終有 n(n-1)/2,因此平均情況、最好情況、最壞情況都是 O(n^2)
空間複雜度：O(1)
簡單選擇排序是一個不穩定的排序演算法
7、堆排序
堆排序也是選擇排序中的一種，是一種樹形選擇排序方法，特點是：在排序過程中，將 L[1…n]看成是一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親節點和孩子節點之間的內在關係，在當前無序區中選擇關鍵字最大或最小的元素。
堆的定義如下：
1）L(i)<=L(2i)且 L(i)<=L(2i+1)【小根堆】或 L(i)>=L(2i)且 L(i)>=L(2i+1)【大根堆】
以大根堆為例，最大元素存放在根節點中，且對其任意非根節點，它的值小於或等於其雙親節點值；在小根堆中正好相反，根節點是最小元素。
堆排序分為兩個步驟：1）創建初始堆；2）將堆頂元素與堆底元素交換位置，破壞堆的定義，重新調整堆，再重複這樣的操作
細節：由於在堆排序中需要依靠數組下標來方便得到雙親節點與其子節點的關係，因此在調整堆的過程中這裡數組 a[0]的作用只用來暫存元素，不存儲實際元素的位置，犧牲一個數組元素空間位置，輸出排序後的結果時從 1 到 n 輸出，實際只有 n 個元素，但須創建 n+1 個元素的數組。
Java 程式碼如下：
import java.util.Scanner;
public class BigRootHeapSort {
public static void AdjustDown(int a[],int k,int length){
//函數 AdjustDown 將元素 k 向下進行調整成大根堆
a[0] = a[k];//a[0]暫存元素,僅作為替代值
for(int i=k2;i<=length;i=i2){
if(i<length && a[i]<a[i+1]){
i++;//取左右子節點中關鍵字較大的子節點的下標
}
if(a[0]>a[i])//被篩選節點小於雙親節點，篩選結束
break;
else{
a[k] = a[i];//將 a[i]調整到雙親節點上
k=i;//修改 k 值，以便繼續向下篩選
}
}
a[k] = a[0];//被篩選節點值放入最終位置
}
//插入元素時，重新整理成大根堆，使用向上調整堆的演算法
public static void AdjustUp(int a[],int k){
//參數 k 為向上調整的節點，也是堆的元素個數
a[0] =a[k];
int i = k/2;//若節點值大於雙親節點，則將雙親節點向下調，並繼續向上比較
while(i>0 && a[i]<a[0]){//循環跳出條件
a[k] = a[i];//雙親節點往下調
k=i;
i = k/2;//繼續向上比較
}
a[k] = a[0];//複製到最終位置
}
public static void BuildMaxHeap(int a[],int length){
//初始創建大根堆
for(int i=length/2;i>0;i–){//從 i=n/2 到 1 反覆調整堆
AdjustDown(a,i,length);
}
}
public static void HeapSort(int a[],int length){
//進行堆排序
BuildMaxHeap(a,length);//初始創建大根堆
for(int i=length;i>1;i–){//n-1 趟的交換和建堆過程
int temp = a[i];//堆頂元素和堆底元素交換位置，刪除元素時也是用同樣的交換方法先將最大元素放在堆底，再取出堆底元素進行刪除
a[i] = a[1];
a[1] = temp;
AdjustDown(a,1,i-1);//整理，把剩餘的 i-1 個元素重新調整成堆
}
}
public static void main(String args[]){
//這裡將 a[0]元素置為 0，便於大根堆的調整與交換，實際上存入了 n 個數但只會用到 n-1 個數
System.out.println(“請輸入待排序的數據到數組中：”);
Scanner sc = new Scanner(System.in);
String str[] = sc.nextLine().split(” “);
int num[] = new int[str.length];
for(int i=0;i<num.length;i++){
num[i] = Integer.parseInt(String.valueOf(str[i]));
}
System.out.println(“形成大根堆後元素排列順序為：”);
BuildMaxHeap(num,num.length-1);//調用大根堆創建過程演算法排列數組元素
for(int i=1;i<num.length;i++)
System.out.print(num[i]+” “);
System.out.println(“\n 堆排序後的數組元素為：”);
HeapSort(num,num.length-1);//調用堆排序演算法對數組元素排序
for(int i=1;i<num.length;i++)
System.out.print(num[i]+” “);
}
}
時間複雜度：在最好、最壞、平均情況下堆排序都為 O(nlogn)
空間複雜度：O(1)
堆排序是一個不穩定的排序演算法
8、歸併排序
歸併排序有多路歸併和 2-路歸併，在內部排序中一般使用 2-路歸併排序，在外部排序中使用多路歸併排序
基本思路：歸併排序與基於交換、選擇等排序思想不一樣，歸併是將兩個或兩個以上的有序表組合成一個新的有序表。假定待排序表含有 n 個記錄，可以看成是 n 個有序的子表，每個子表長度為 1，然後兩兩歸併，得到 n/2（向上取整）個長度為 2 或 1 的有序表；在兩兩歸併，如此反覆，直到合併成一個長度為 n 的有序表為止。
遞歸形式的 2-路歸併排序演算法是基於分治的，其過程為：
分解：將含有 n 個元素的待排序表分成各含 n/2 個元素的子表，採用 2-路歸併排序演算法對兩個子表遞歸地進行排序；
合併：合併兩個已排好序的子表得到排序結果；
Java 程式碼如下：
import java.util.Scanner;
public class MergeIntoSort {
public static void Merge(int a[],int low,int mid,int high){
//表 a 的兩段 a[low…mid]和 a[mid+1…high]各自有序，將它們合併成一個有序表
//設立鋪助數組 b[]
int b[] = new int[a.length];
for(int i=low;i<=high;i++){
b[i]=a[i];//將 a 中所有元素複製到 b 數組中
}
int i,j,k;
for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
if(b[i]<=b[j])//比較 b 數組左右兩段中的元素
a[k] = b[i++];//小的數複製到 a 數組中
else//不能改為 if(b[i]>b[j])
a[k] = b[j++];
}
while(i<=mid)
a[k++] = b[i++];//若前段未複製完，直接複製
while(j<=high)
a[k++] = b[j++];//若後段未複製完，直接複製
}
//使用遞歸形式的分治法進行歸併排序
public static void MergeSort(int a[],int low,int high){
if(low<high){
int mid = (low+high)/2;//從中間劃分兩個子序列
MergeSort(a,low,mid);//對左側子序列進行遞歸排序
MergeSort(a,mid+1,high);//對右側子序列進行遞歸排序
Merge(a,low,mid,high);//劃分之後歸併
}
}
public static void main(String args[]){
System.out.println(“請輸入待排序的數據到數組中：”);
Scanner sc = new Scanner(System.in);
String str[] = sc.nextLine().split(” “);
int num[] = new int[str.length];
for(int i=0;i<num.length;i++){
num[i] = Integer.parseInt(String.valueOf(str[i]));
}
//調用歸併排序演算法進行排序
MergeSort(num,0,num.length-1);
System.out.println(“排序後的結果為：”);
for(int i=0;i<num.length;i++){
System.out.print(num[i]+” “);
}
}
}
時間複雜度：平均、最好、最壞情況下都為 O(nlogn)
空間複雜度：需要 n 個單元的鋪助空間，因此為 O(n)
2-路歸併排序演算法是一個穩定的排序演算法；
註：一般而言，對於 N 個元素進行 k-路歸併排序時，排序的趟數 m 滿足 k^m=N,可得 m=logk(N)，又考慮到 m 為整數，所以 m=|logk(N)|(向上取整)
9、基數排序
基本思路：
基數排序不是基於比較進行排序的，而是採用多關鍵字排序思想（即基於關鍵字各位的大小進行排序），藉助「分配」和「收集」兩種操作對單邏輯關鍵字進行排序。基數排序又分為最高位優先排序（MSD）和最低位優先排序(LSD)。
以三位數的元素為例，可將元素看作為（K^3,K^2,K^1）組合，K^3 是百位上的數字，K^2 是十位上的數字，K^1 是個位上的數字，使用最高位優先排序方法，在排序過程中，首先根據百位上的數字（K^3）進行排序，按各元素在百位上的取值，分配到各個子序列（稱為桶）中，然後然後再按桶的編號，逐桶進行遞歸地基數排序，在每個桶中，子序列的規模已經大大減少，同時桶中所有元素在百位上的數字取值相同，這時，按各元素的十位上的數字（K^2）取值繼續進行桶式分配，之後還對各個子桶中的元素按個位（K^1）進行分配，從而使得待排序序列所有元素排好序。
程式碼如下：
各個排序演算法比較及其適用範圍說明：
各種排序演算法的使用範圍總結：
(1)當數據規模較小的時候，可以使用簡單的排序演算法如直接插入排序或直接選擇排序。
(2)當待排序表的初始狀態已經基本有序時，可以使用直接插入排序（希爾排序）或冒泡排序。
當數據規模較大時，應採用時間複雜度為 O(nlogn)的排序方法：快速排序、堆排序、歸併排序。
(3)當數據規模較大時，應用速度快的排序演算法。可以考慮快速排序。當記錄隨機分布的時候，快排的平均時間最短，但可能出現最壞的情況，這時候的時間複雜度是O(n^2)，且遞歸深度為n，所需的棧空間為O(n)。
(4)堆排序不會出現快排那樣的最壞情況，且堆排序所需的輔助空間比快排要少。但這兩種演算法都不是穩定的，若要求排序時穩定，可以考慮用歸併排序。
(5)歸併排序可以用於內部排序，也可以用於外部排序。在外部排序時，通常採用多路歸併，並且通過解決長順串的合併，產生長的初始串，提高主機與外設並行能力等措施，以減少訪問外存次數，提高外排序的效率。
（6）當數據規模很大，記錄的關鍵字位數較少且可以分解時，採用基數排序較好。
