7种常用排序算法总结

比较一览

排序法	最优时间	平均复杂度	最差情形	稳定度	额外空间	备注	类型
选择	O(n2)	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个项目要Ο(nlogn)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(nlogn) 算法更快，因为它的内部循环（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;
	}