各类排序算法总结（Java代码实现）

一、   稳定性

稳定性是指待排序的序列中有两个或者两个以上相同的项，排序前和排序后，看这些相同的项的相对位置有没有没发生变化，如果没有发生变化，就是稳定的；如果发生变化，就是不稳定的。

二、   排序分类以及复杂度

2.1、      插入类排序

2.1.1、直接插入排序

最坏时间复杂度：O(n^2)

最好时间复杂度：O(n)

平均时间复杂度：O(n^2)

空间复杂度：O(1)

2.1.2、折半插入排序

最坏时间复杂度：O(n^2)

最好时间复杂度：O(n)

平均时间复杂度：O(n^2)

空间复杂度：O(1)

2.1.3、希尔排序

平均时间复杂度：O(nlogn)

空间复杂度：O(1)

2.2、      交换类排序

2.2.1、冒泡排序

最坏时间复杂度：O(n^2)

最好时间复杂度：O(n)

平均时间复杂度：O(n^2)

空间复杂度：O(1)

2.2.2、快速排序

最坏时间复杂度：O(n^2)

最好时间复杂度：O(nlogn)

平均时间复杂度：O(nlogn)

空间复杂度：O(logn)

2.3、      选择类排序

2.3.1、简单选择排序

最坏时间复杂度：O(n^2)

最好时间复杂度：O(n^2)

平均时间复杂度：O(n^2)

空间复杂度：O(1)

2.3.2、堆排序

最坏时间复杂度：O(nlogn)

最好时间复杂度：0(nlogn)

平均时间复杂度：O(nlogn)

空间复杂度：O(1)

2.4、      归并类排序

2.4.1、二路归并排序

最坏时间复杂度：O(nlogn)

最好时间复杂度：O(nlogn)

平均时间复杂度：O(nlogn)

空间复杂度：O(n)

2.5、      基数类排序

最坏时间复杂度：O(d(n+rd))

最好时间复杂度：

平均时间复杂度：O(d(n+rd))

空间复杂度：O(rd)

三、   各类排序算法Java代码

3.1、      直接插入排序

介绍和思想

介绍：插入排序基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。

思想：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

算法代码

public static <T extends Comparable<? super T>> void insertionSort(T[] a) {
		int j;
		for (int i = 1; i < a.length; i++) {
			T tmp = a[i];
			for (j = i; j > 0 && tmp.compareTo(a[j-1])<0; j--) {
				a[j] = a[j-1];
			}
			a[j] = tmp;
		}
	}

3.2、      折半插入排序

介绍和思想

折半插入排序的基本思想和直接插入排序一样，区别在于寻找插入位置的方法不同，折半插入排序是采用折半查找方法类寻找插入位置的。

算法代码

public static void binaryInsertSort(int[] a) {
		for(int i = 1;i < a.length;i++) {
			int temp = a[i];
			int low = 0;
			int high = i-1;
			while(low<=high) {
				int mid = (low+high)/2;
				if(temp < a[mid]) {
					high = mid-1;
				}else {
					low = mid+1;
				}
			}
			for(int j = i;j>=low+1;j--) {
				a[j] = a[j-1];
			}
			a[low] = temp;
		}
	}

3.3、      冒泡排序

算法介绍和思想

冒泡排序是通过一系列的“交换”动作完成的，是交换类排序的一种。

首先第一个记录和第二个记录比较，如果第一个大，则两者交换，否则不交换；

然后第二个记录和第三个记录比较，如果第二个大，则两者交换，否则不交换……一直按这种方式进行下去，最终最大的那个记录被交换到了最后，一趟冒泡排序完成。

然后进行第二趟冒泡排序，对前n-1个记录进行同样的操作，使关键字次大的记录被安置到第n-1个记录的位置上……一直这样进行下去，直到“在一趟排序过程中没有进行过交换记录的操作”，这也是冒泡排序算法的结束条件。

算法代码

public static <T extends Comparable<? super T>> void bubbleSort(T[] a) {
		int i,j,flag;
		T temp;
		for(i=a.length-1;i>0;i--) {//最多进行a.length-1趟排序
			flag = 0;
			for(j=0;j<i;j++) {////对当前无序区间a[0......i]进行排序
				if(a[j].compareTo(a[j+1])>0) {//大值交换到后面
					temp = a[j+1];
					a[j+1] = a[j];
					a[j] = temp;
					flag = 1;
				}
			}
			if(flag == 0) {//结束条件：某一趟排序是否有交换
				return;
			}
		}
	}

3.4、      快速排序

算法介绍和思想

快速排序是对冒泡排序的一种改进，它也是“交换”类排序的一种。它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

算法步骤和过程

一趟快速排序的具体做法是：附设两个指针low和high，它们的初值分别为low和high，设枢轴记录的关键字为pivotkey，则首先从high所指位置起向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录互相交换，然后从low所指位置起向后搜索，找到第一个关键字大于pivotkey的记录和枢轴记录互相交换，重复这两步直至low=high为止。

实质上，快速排序就三个步骤：

第一步：将待排序序列一分为二

第二步：对小于pivotkey的低子表递归排序

第三步：对大于pivotkey的高子表递归排序

算法代码

/**
 * 第一步：将待排序序列一分为二
 * 第二步： 对低子表递归排序
 * 第三步：对高子表递归排序
 * @author 卡罗-晨
 */
public class QuickSort {
	
	/**
	 * 将序列一分为二，并返回枢轴位置
	 */
	private static <T extends Comparable<? super T>> int partition(T[] a,int low,int high) {
		T pivotkey = a[low];
		while(low<high) {
			while(low<high && a[high].compareTo(pivotkey)>=0) --high;
			a[low] = a[high];
			while(low<high && a[low].compareTo(pivotkey)<=0) ++low;
			a[high] = a[low];
		}
		a[low] = pivotkey;
		return low;
	}
	
	/**
	 * 快速排序三步走
	 */
	private static <T extends Comparable<? super T>> void qSort(T[] a,int low,int high) {
		if(low<high) {
			int pivotloc = partition(a, low, high);
			qSort(a, low, pivotloc-1);
			qSort(a, pivotloc+1, high);
		}
	}
	public static <T extends Comparable<? super T>> void quickSort(T[] a) {
		qSort(a, 0, a.length-1);
	}
}

一个方法实现快速排序

public static void quickSort(int[] a,int low,int high) {
		int temp;
		int i = low,j = high;
		if(low < high) {
			temp = a[low];
			while(i != j) {
				while(j>i&&a[j]>=temp) --j;
				if(i<j) {
					a[i] = a[j];
					++i;
				}
				while(i<j&&a[i]<=temp) ++i;
				if(i<j) {
					a[j] = a[i];
					--j;
				}
				a[i] = temp;
				quickSort(a, low, i-1);
				quickSort(a, i+1, high);
			}
		}
	}

3.5、      简单选择排序

算法介绍和思想

选择类排序的主要动作是“选择”，简单选择排序采用最简单的选择方式，从头至尾扫描序列，找出最小的一个记录，和第一个记录交换，接着从剩下的记录中继续这种选择和交换吗，最终使序列有序。

算法代码

public static void selectSort(int[] a) {
		int minIndex;
		int temp;
		for(int i = 0;i<a.length;i++) {
			minIndex = i;
			for(int j = i+1;j<a.length;j++) {
				if(a[j]<a[minIndex]) {
					minIndex = j;
				}
			}
			if(minIndex != i) {
				temp = a[i];
				a[i] = a[minIndex];
				a[minIndex] = temp;
			}
		}
	}

3.6、      堆排序

算法介绍

堆是一种数据结构，可以把堆看成一棵完全二叉树，这棵完全二叉树满足：任何一个非叶结点的值都不大于（或不小于）其左右孩子结点的值。若父亲大孩子小，叫大顶堆；若父亲小孩子大，则这样的堆叫做小顶堆。

二叉树：每个结点最多只有两棵子树，即二叉树中结点的度只能为0、1、2。子树有左右之分，不能颠倒。

满二叉树：在一棵二叉树中，如果所有的分支结点都有左孩子和右孩子结点，并且叶子结点都集中在二叉树的最下一层。另一种定义：一棵深度为k且有 个结点的二叉树称为满二叉树。

完全二叉树：深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。通俗来讲，一棵完全二叉树是由一棵满二叉树从右至左从下而上，挨个删除结点所得到的。

堆排序的思想：将一个无序序列调整为一个堆，就可以找出这个序列的最大（或最小）值，然后将找出的这个值交换到序列的最后（或最前），这样有序序列元素增加·个，无序序列中元素减少1个，对新的无序序列重复这样的操作，就实现了排序。

堆排序的过程（自述）：

（1）首先，建堆：原始序列对应一个还不是堆的完全二叉树。对非叶子节点从右至左，从下至上，进行下滤操作，得到一个大顶堆。

待下滤操作的第一个非叶子节点计算方法：a.length/2-1

下滤操作思想：首先判断非叶子节点是否为两个孩子，两个孩子谁更大，指针指向大孩子；接着，判断非叶子节点和指针指向的大孩子谁更大，孩子大则交换。

（2）接着，排序：将大顶堆堆顶和无序序列最后一个记录交换，有序+1记录，无序-1记录。

（3）然后，将交换后的完全二叉树，从堆顶下滤，将其调整为一个大顶堆，重复上述过程。直到树中只剩下1个节点时排序完成。

堆排序执行过程

l  将原始序列化为一个完全二叉树。

l  从无序序列所确定的完全二叉树的第一个非叶子结点开始，从右至左，从下至上，对每一个结点进行调整，最终将得到一个大顶堆。

对结点的调整方法：将当前结点（假设为a）的值与其孩子结点进行比较，如果存在大于a值的孩子结点，则从中选出最大的一个与a交换。当a来到下一层的时候重复上述过程，直到a的孩子结点值都小于a的值为止。

l  将当前无序序列中第一个元素，反映在树中是根节点（假设为a）与无序序列中最后一个元素交换（假设为b）。a进入有序序列，到达最终位置。无序序列中元素减少1个，有序序列中元素增加1个。此时只有结点b可能不满足堆的定义，对其进行调整。

l  重复3）中的过程，知道无序序列中的元素剩下1个时排序结束

算法代码（Java）

/**
 * 堆排序
 * @author 卡罗-晨
 */
public class HeapSort {

	public static int leftChild(int i) {
		return 2*i+1;
	}
	
	private static <T extends Comparable<? super T>> void percDown(T[] a,int i,int n) {
		int child;
		T tmp;
		for (tmp = a[i];leftChild(i)<n;i=child) {
			child = leftChild(i);
			if(child != n-1 && a[child].compareTo(a[child+1])<0) {
				child++;
			}
			if(tmp.compareTo(a[child])<0) {
				a[i] = a[child];
			}else 
				break;
		}
		a[i] = tmp;
	}
	/**
	 * 标准堆排序
	 * @param a可比较的集合
	 */
	public static <T extends Comparable<? super T>> void heapsort(T[] a) {
		//建立堆
		for(int i=a.length/2-1;i>=0;i--) {
			percDown(a, i, a.length);
		}
		for(int i=a.length-1;i>0;i--) {
			T tmp = a[0];
			a[0] = a[i];
			a[i] = tmp;
			percDown(a, 0, i);
		}
	}
}

3.7、      二路归并排序

算法描述

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

若将两个有序表合并成一个有序表，称为二路归并。

算法思想

1、  划分：将待排序序列划分为两个长度相等的子序列。

2、  求解子问题：分别对这两个子序列进行归并排序，得到两个有序子序列。

3、  合并：将两个有序子序列合并成一个有序序列。

算法核心步骤

核心步骤就一下三步：

l  1、归并排序前半个子序列

l  2、归并排序后半个子序列

l  3、合并两个已排序的子序列

其中，前两个步骤的是一样的方法mergeSort()进行递归，第三步是另一个方法merge()。这个算法中基本的操作就是第三步合并两个已排序的表。因为这两个表是已排序的，所以若将输出放到第三个表中，则该算法可以通过对输入数据一趟排序来完成。基本的合并算法是取两个输入数组A和B，一个输出数组C，以及3个计数器Actr、Bctr、Cctr，它们初始置于对应数组的开始端。A[Actr]和B[Bctr]中较小者被拷贝到C中的下一个位置，相关的计数器向前推进一步。当两个输入表有一个用完的时候，则将另一个表中剩余部分拷贝到C中。

实现代码

public class MergeSortExample {
	public static void mergeSort(int[] a) {
		int[] tempArray = new int[a.length];
		mergeSort(a, tempArray, 0, a.length - 1);
	}
	private static void mergeSort(int[] a, int[] tempArray, int left, int right) {
		if (left < right) {
			int center = (left + right) / 2;
			mergeSort(a, tempArray, left, center);
			mergeSort(a, tempArray, center + 1, right);
			merge(a, tempArray, left, center + 1, right);
		}
	}
	private static void merge(int[] a, int[] tempArray, int leftPos, int rightPos, int rightEnd) {
		int leftEnd = rightPos-1;
		int temPos = leftPos;
		int numElements = rightEnd-leftPos+1;
		while(leftPos<=leftEnd && rightPos<=rightEnd) {
			if(a[leftPos] <= a[rightPos]) {
				tempArray[temPos++] = a[leftPos++];
			}else {
				tempArray[temPos++] = a[rightPos++];
			}
		}
		while(leftPos<=leftEnd) {
			tempArray[temPos++] = a[leftPos++];
		}
		while(rightPos <= rightEnd) {
			tempArray[temPos++] = a[rightPos++];
		}
		for(int i=0;i<numElements;i++,rightEnd--) {
			a[rightEnd] = tempArray[rightEnd];
		}
	}
}

merge()方法很精巧。如果对merge的每个递归调用均局部声明一个临时数组，那么在任一时刻就可能有个临时数组处在活动期。精密的考察表明，由于merge是mergeSort的最后一行，因此在任一时刻只需要一个临时数组在活动，而且这个临时数组可以在public型的mergeSort驱动程序中建立。