天天看點
傳回

7種常用排序算法總結

比較一覽
排序法 最優時間 平均複雜度 最差情形 穩定度 額外空間 備注 類型
選擇 O(n 2 ) O(n2)   O(n2) 不穩定 O(1) n小時較好 選擇排序
冒泡 0-O(n) O(n2) O(n2) 穩定 O(1) n小時較好 交換排序
插入 O( n ) O(n2) O(n2) 穩定 O(1) 大部分已排序時 插入排序
Shell O( n ) 依賴步長串行 O(ns) 1<s<2 不穩定 O(n) s是所選分組 插入排序
快速 O(nlogn) O(nlogn) O(n2)  不穩定 O(nlogn) n大時較好 交換排序
歸并 O( n ) O(nlogn) O(nlogn) 穩定 O(1)-O(n) n大時較好 歸并排序
堆 O(nlogn) O(nlogn) O(nlogn) 不穩定 O(1)-O(n) n大時較好 選擇排序

1. 快速排序

介紹：

快速排序是由東尼·霍爾所發展的一種排序算法。在平均狀況下，排序 n 個項目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況并不常見。事實上，快速排序通常明顯比其他Ο(n log n) 算法更快，因為它的内部循環（inner loop）可以在大部分的架構上很有效率地被實作出來，且在大部分真實世界的資料，可以決定設計的選擇，減少所需時間的二次方項之可能性。

步驟：

  1. 從數列中挑出一個元素，稱為 “基準”（Pivot），
  2. 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處于數列的中間位置。這個稱為分區（partition）操作。
  3. 遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。

代碼：

public class QuitSort {

	static int  cpNum = 0;
	static int  swapNum = 0;
	public static void main(String[] args) {

		int[] a = {5,44,3,64,3,64,34,45,4,112};
		
		QuitSort.quitSort(a,0,a.length-1);
		
		System.out.println("數組大小:"+a.length+"   比較次數:"+cpNum+"	交換次數："+swapNum);
		for (int i : a) {
			System.out.print(i+"--");
			
		}
	}

	public static void quitSort(int[] a,int start ,int end) {

		if (start >= end )
			return;
		
		int i = start;
		int j = end;
		int key = a[start];

		while (i < j) {

			for (; j > i; j--) {
				cpNum++;
				if (a[j] < key) {
					swapNum++;
					a[i] = a[j];
					break;
				}
			}

			for (; i < j; i++) {
				cpNum++;
				if (a[i] > key) {
					swapNum++;
					a[j] = a[i];
					break;
				}
			}
		}
		a [i] = key;

		
		quitSort(a,start,i-1);//sort left 
		quitSort(a,i+1,end);//sort left [
	}

}

2. 歸并排序

介紹：

歸并排序（Merge sort，台灣譯作：合并排序）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用

步驟：

  1. 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并後的序列
  2. 設定兩個指針，最初位置分别為兩個已經排序序列的起始位置
  3. 比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置
  4. 重複步驟3直到某一指針達到序列尾
  5. 将另一序列剩下的所有元素直接複制到合并序列尾

代碼：

import java.util.Arrays;

/**
 * 歸并排序
 * 
 * 空間換時間
 * Cworst(n) = O(n log n)
 * @author stephen
 * 
 */
public class MergeSort {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

	    int[] a = {5,4,3,2,1};
		//int[] a = { 5, 44, 9, 64, 3, 64, 34, 45, 3, 112 };
		sort(a);
		System.out.println("比較次數:" + cpNum);
		System.out.println("移動次數:" + moveNum);
		for (int i : a) {
			System.out.print(i + "--");

		}

	}

	static int cpNum = 0;
	static int moveNum = 0;

	public static void sort(int[] a) {

		int t;
		int length = a.length;
		int middle = (length) / 2;

		if (length > 1) {
			int[] b = Arrays.copyOfRange(a, 0, middle);
			int[] c = Arrays.copyOfRange(a, middle, length);
			moveNum += length;
			sort(b);
			sort(c);
			merge(a, b, c);
		}

	}

	private static void merge(int[] a, int[] b, int[] c) {

		int i = 0, j = 0, k = 0;
		while (i < b.length && j < c.length) {

			cpNum++;
			if (b[i] > c[j]) {

				a[k] = c[j];
				k++;
				j++;

				moveNum++;
			} else {
				a[k] = b[i];
				k++;
				i++;
				moveNum++;
			}

		}
		if (i == b.length) {
			while (j < c.length) {
				a[k] = c[j];
				j++;
				k++;
				moveNum++;
			}

		} else {
			while (i < b.length) {
				a[k] = b[i];
				i++;
				k++;
				moveNum++;
			}
		}
	}

}

3. 堆排序

介紹：

堆積排序（Heapsort）是指利用堆這種資料結構所設計的一種排序算法。堆是一個近似完全二叉樹的結構，并同時滿足堆性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。

步驟：

（比較複雜，略）

4. 選擇排序

介紹：

選擇排序(Selection sort)是一種簡單直覺的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小元素，然後放到排序序列末尾。以此類推，直到所有元素均排序完畢。

代碼：

/**
 * C(c) = n*(n-1)/2   O(n^2) 
 * @author stephenluu
 *
 */
public class SelectionSort {
	
	public static void main(String[] args) {

	   // int[] a = {5,4,3,2,1};
		int[] a = { 5, 44, 9, 64, 3, 64, 34, 45, 3, 112 };
	    selectionSort(a);
		System.out.println("比較次數:" + cpNum);
		System.out.println("移動次數:" + swapNum);
		for (int i : a) {
			System.out.print(i + "--");

		}

	}

	static int cpNum = 0;
	static int swapNum = 0;
    public static void selectionSort (int[] a){
    	
    	int t;
    	
    	for (int i = 0; i < a.length; i++) {
			for (int j = i+1 ; j < a.length; j++) {
				
				cpNum++;
				
				if (a[i] > a[j]){
					
					swapNum++;
					t =  a[i];
					a[i] = a[j];
					a[j] = t;
				}
			}
		}
    };

}

5. 冒泡排序

介紹：

冒泡排序（Bubble Sort，台灣譯為：泡沫排序或氣泡排序）是一種簡單的排序算法。它重複地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。

步驟：

  1. 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
  2. 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。
  3. 針對所有的元素重複以上的步驟，除了最後一個。
  4. 持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。

代碼：

/**
 * 冒泡排序
 * key 相鄰
 * 跌帶出最大的數放到最後
 * @author stephen
 *
 */
public class BubbleSort {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		//int[] a = {1,2,3,4,5};
		int[] a = {5,44,3,64,3,64,34,45,4,112};
		//sort(a);
		sortImproved(a);
		System.out.println("比較次數:"+n);
		for (int i : a) {
			System.out.print(i+"--");
			
		}

	}
		
	static int n = 0;
	
	//C(n) = n(n-1)/2  Sworst(n) = n(n-1)/2 -- O(n^2)
	public static void sort(int[] a){
		int t;
		
		for (int i = a.length-1; i >0; i--) {
			
			for (int j = 0; j <i ; j++) {
				
				if (a[j] > a[j+1]) 
				{
					t = a[j+1];
					a[j+1] = a[j];
					a[j] = t;
				}
				n++;
			}
		}
	}
	
	//Cmin(n) = n-1  Sworst(n) = n(n-1)/2 -- O(n^2)
	public static void sortImproved(int[] a){
		int t;
		
		for (int i = a.length-1; i >0; i--) {
			
			boolean isSwap = false;
			
			for (int j = 0; j <i ; j++) {
				
				if (a[j] > a[j+1]) 
				{
					t = a[j+1];
					a[j+1] = a[j];
					a[j] = t;
					
					isSwap = true;
				}
				n++; //計算次數
			}
			
			if (!isSwap)
				return;
		}
	}
	
}

6. 插入排序

介紹：

插入排序（Insertion Sort）的算法描述是一種簡單直覺的排序算法。它的工作原理是通過建構有序序列，對于未排序資料，在已排序序列中從後向前掃描，找到相應位置并插入。插入排序在實作上，通常采用in-place排序（即隻需用到O(1)的額外空間的排序），因而在從後向前掃描過程中，需要反複把已排序元素逐漸向後挪位，為最新元素提供插入空間。

步驟：

  1. 從第一個元素開始，該元素可以認為已經被排序
  2. 取出下一個元素，在已經排序的元素序列中從後向前掃描
  3. 如果該元素（已排序）大于新元素，将該元素移到下一位置
  4. 重複步驟3，直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到該位置中
  6. 重複步驟2

代碼：

/**
 * Cworst(n) = (n-1)n/2 : O(n^2) Cavg = (n^2)/4 : O(n^2)
 * 
 * @author stephenluu
 * 
 */
public class InsertionSort {

	public static void main(String[] args) {

		// int[] a = {5,4,3,2,1};
		int[] a = { 5, 44, 9, 64, 3, 64, 34, 45, 3, 112 };
		insertionSort(a);
		System.out.println("比較次數:" + cpNum);
		for (int i : a) {
			System.out.print(i + "--");

		}

	}

	static int cpNum = 0;
	public static void insertionSort(int[] a) {

		int t;
		int j;
		for (int i = 1; i < a.length; i++) {
			t = a[i];
			j = i - 1;
			while (j >= 0 && a[j] > t) {

				cpNum++;
				a[j + 1] = a[j];
				j--;
			}
			a[j + 1] = t;
		}
	}

}

7. 希爾排序

介紹：

希爾排序，也稱遞減增量排序算法，是插入排序的一種高速的改進版本。

希爾排序是基于插入排序的以下兩點性質而提出改進方法的：

1、插入排序在對幾乎已經排好序的資料操作時， 效率高， 即可以達到線性排序的效率

2、但插入排序一般來說是低效的， 因為插入排序每次隻能将資料移動一位>

代碼：

這是D.Shell 的實作版本，不是我寫的

int shellsortSh(int p[], int n) {
		int op = 0;
		int h, i, j, temp;
		for (h = n / 2; h > 0; h = h / 2) {
			for (i = h; i < n; i++) {
				temp = p[i];
				for (j = i - h; j >= 0 && p[j] > temp; j -= h) {
					p[j + h] = p[j];
					op++;
				}
				p[j + h] = temp;
				op++;
			}
		}
		return op;
	}
算法 排序 排序算法 快速排序 歸并排序
上一篇: #初學算法# 歸并排序與冒泡排序算法對比
下一篇: 歸并排序和快速排序總結歸并排序和快速排序總結

繼續閱讀