排序总结（不断更新）

为什么80%的码农都做不了架构师？>>>   

排序法	最好时间分析	最差时间分析	平均时间复杂度	稳定度	空间复杂度
冒泡排序	O(n)（改进的冒泡排序）	O(n2)	O(n2)	稳定	O(1)
快速排序	O(n*log2n)	O(n2)	O(n*log2n)	不稳定	O(log2n)~O(n)
选择排序	O(n2)	O(n2)	O(n2)	不稳定	O(1)
二叉树排序		O(n2)	O(n*log2n)		O(n)
插入排序	O（n）	O(n2)	O(n2)	稳定	O(1)
堆排序	O(n*log2n)	O(n*log2n)	O(n*log2n)	不稳定	O(1)
希尔排序	/	与增量序列的选取有关	与增量序列的选取有关	不稳定	O(1)
归并排序	O(n*log2n)	O(n*log2n)	O(n*log2n)	稳定	O(n)

本文中的排序验证OJ：http://pta.patest.cn/pta/test/18/exam/4/question/633

OJ测试点说明：

数据1：只有1个元素； 数据2：11个不相同的整数，测试基本正确性； 数据3：10³个随机整数； 数据4：10⁴个随机整数； 数据5：10⁵个随机整数； 数据6：10⁵个顺序整数； 数据7：10⁵个逆序整数； 数据8：10⁵个基本有序的整数； 数据9：10⁵个随机正整数，每个数字不超过1000。

排序算法稳定性：

    假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

    对于不稳定的排序算法，只要举出一个实例，即可说明它的不稳定性；而对于稳定的排序算法，必须对算法进行分析从而得到稳定的特性。需要注意的是，排序算法是否为稳定的是由具体算法决定的，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。

    稳定的算法在排序复杂数据时能保持同样数据的原本顺序不变，比如你已经有一组按年龄排好的学生信息，你想按照身高排序并且相同身高时，年龄是有序的，这时稳定的算法才能达到要求。

冒泡排序：

冒泡排序算法的运作如下：（从后往前）

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

代码：

public void bubbleSort(int num[])
	{
		for (int i = 0; i < num.length - 1; i++)
		{
			for (int j = 0; j < num.length - 1 - i; j++)
			{
				if (num[j] > num[j + 1])
				{
					int temp = num[j];
					num[j] = num[j + 1];
					num[j + 1] = temp;
				}
			}
		}
	}

性能分析：

需要n(n-1）/2次比较，复杂度为O(n^2)，最差最好都是O(n^2)，空间复杂度为O(1)，但是如果排好序的很明显一次都不用移动，应该是O(n)才对。

改进的冒泡排序：

加了一个标志位来判断是否有过交换。使最好的排序复杂度为O(n)

public void bubbleSort(int num[])
	{
		boolean swap = false;
		for (int i = 0; i < num.length; i++)
		{
			swap = false;
			for (int j = 0; j < num.length - 1 - i; j++)
			{
				if (num[j] > num[j + 1])
				{
					int temp = num[j];
					num[j] = num[j + 1];
					num[j + 1] = temp;
					swap = true;
				}
			}
			if (!swap)
			{
				break;
			}
		}
	}

改进后的冒泡排序代码在OJ上的运行情况：

可以发现在数据达到10^5时就超时了，当然在顺序序列时依旧能够通过。

插入排序：

插入排序的基本思想是：

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

代码：

public static void InsertSort(int num[], int N)
	{
		int temp = 0;
		int j = 0;
		for (int i = 1; i < N; i++)
		{
			temp = num[i];
			for (j = i; j > 0 && temp < num[j - 1]; j--)
			{
				num[j] = num[j - 1];
			}
			num[j] = temp;
		}
	}

插入排序在OJ上的运行情况：

性能分析：

插入排序的最好情况是，待排序列正好是正序的，此时每次只要在末尾插入数字即可，不需要进行移位判断，此时时间复杂度为O（n）；最坏情况是，待排序列是逆序的，此时每次都要移位所有的数字，腾出第一个位置再插入，此时时间复杂度为O（n^2）。

我们可以发现，冒泡排序和插入排序交换的次数是相同的。这里提出逆序对的概念，逆序对就是对于下标i<j，如果A[i]>A[j]，则称(i,j)是一对逆序对。每次交换就是消灭了一对逆序对，所以交换次数就是逆序对的个数。

所以插入排序的复杂度T(N,I)=O(N+I)，I是逆序对的个数。所以如果I很少（基本有序），则插入排序简单高效。

这里提出个定理：任意N个不同元素组成的序列平均具有N（N-1）/4个逆序对。

定理：任何仅以交换相邻两元素来排序的算法，其平均复杂度为Ω（n^2）（Ω指的是下界）。

这意味着：要提高算法效率，我们必须每次消去不止一个逆序对，每次交换相隔较远的的2个元素。

希尔排序：

克服先前所说的仅交换相邻元素的缺点，提出了一种新的排序方法。

希尔排序的基本思想是：

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量（增量要互质）减至1时，整个文件恰被分成一组，算法便终止。

低（比如2）间隔有序的序列，高间隔也有序（比如5）。

原始希尔排序：

public static void ShellSort(int num[], int N)
	{
		int temp = 0;
		int j = 0;
		for (int n = N / 2; n > 0; n = n / 2)
		{
			for (int i = n; i < N; i++)
			{
				temp = num[i];
				for (j = i; j >= n && temp < num[j - n]; j = j - n)
				{
					num[j] = num[j - n];
				}
				num[j] = temp;
			}
		}
	}

最坏情况θ（n^2）（θ表示即是上界也是下界，表明增长速度是跟n^2一样快的）

希尔排序在OJ上运行情况：

可以发现相比于插入排序来说，快了很多，速度比较稳定。

性能分析：

上述代码最坏情况的原因是增量不互质（比如8,4,2,1）时，就如同插入排序。增量序列的选择对希尔排序的时间复杂度影响很大。

已知的最好步长序列是由Sedgewick提出的(1, 5, 19, 41, 109,...)，该序列的项来自

这两个算式。

一般来说希尔排序的速度在插入排序和快速排序之间。

选择排序：

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。

public static void SelectionSort(int num[], int N)
	{
		int min = 0;
		for (int i = 0; i < N - 1; i++)
		{
			min = i;
			for (int j = i; j < N; j++)
			{
				if (num[j] < num[min])
				{
					min = j;
				}
			}
			if (min != i)
			{
				int temp = num[min];
				num[min] = num[i];
				num[i] = temp;
			}
		}
	}

选择排序在OJ上的结果：

性能分析：

无论最好最坏情况，都需要n(n-1)/2次比较，最坏情况需要每次交换，最好情况不交换，所以无论最好最坏都是O(n^2)

发现选择排序和冒泡排序其实差不多，每次都是最大（小）的数字交换到开头，那两者有什么区别呢？

1. 冒泡排序是稳定的，选择排序不稳定。

2. 选择排序每次只交换一组数据，冒泡排序可能交换多次，但是两者比较次数是一样的。

3. 冒泡最坏的情况复杂度才是O(n^2)，最好是O(n)， 选择平均复杂度就是O(n^2) 但是冒泡的最坏情况处理要比选择慢。

堆排序：

选择排序太慢了，时间复杂度达到O(n^2)。如何减少时间复杂度呢？由于在选择排序中找到最小元需要O(n)的时间复杂度，有没有更快的方法呢？我们想到了堆。堆排序其实是对选择排序的一种改进。

public static void HeapSort(int num[], int N)
	{
		BuildMinHeap(num);//O(n)
		int[] temp = new int[N];
		for (int i = 0; i < N; i++)
		{
			temp[i] = DeleteMin(num);//O(logN)
		}
		for (int i = 0; i < N; i++)
		{
			num[i] = temp[i];//O(n)
		}
	}

很直观的想法，建立一个最小堆，然后不断取出根节点，保存到临时数组中，为了与其他算法保持一致，我们还需把临时数组赋值给原本的数组。时间复杂度为O(NlogN)，但是空间复杂度就很高了。其实复制temp数组给num数组又费时间又费空间，有没有办法把这一步简化掉呢？

我们想到一种方法：不建立最小堆，建立最大堆，建好堆以后，把根节点和最后一位进行交换（交换后最大的那个数放到了最后一位）。然后排除最后一位，继续建最大堆，重复这个过程。

public static void HeapSort(int num[], int N)
 {
     BuildMaxHeap(num, N);//建立最大堆O(N)
     for (int i = N - 1; i > 0; i--)
     {
         int temp = num[0];
         num[0] = num[i];
         num[i] = temp;
         MaxHeapFixdown(num, i, 0);//这个就相当于只调整根元素，只需要一次logN
     }
 }


 private static void BuildMaxHeap(int num[], int N)
 {
     for (int i = (N % 2 == 0 ? (N - 1) / 2 : (N - 2) / 2); i >= 0; i--)
     {
         MaxHeapFixdown(num, N, i);
     }
 }


 private static void MaxHeapFixdown(int[] num, int N, int i)
 {
     int child = 0;
     int temp = num[i];
     int j = 0;
     for (j = i; (j * 2 + 1) < N; j = child)
     {
         child = 2 * j + 1;
         if (2 * j + 2 < N && num[2 * j + 1] < num[2 * j + 2])
         {
             child++;
         }
         if (temp > num[child])
         {
             break;
         }
         else
         {
             num[j] = num[child];
         }
     }
     num[j] = temp;
 }

堆排序在OJ上的结果：

由于每次重新恢复堆的时间复杂度为O(logN)，共N - 1次重新恢复堆操作，再加上前面建立堆时间复杂度也为O(N)。二次操作时间相加还是O(N * logN)。故堆排序的时间复杂度为O(N * logN)。

定理：堆排序处理N个不同元素的随机排列的平均比较次数是：2NlogN-O（NloglogN）

虽然堆排序给出最佳平均时间复杂度，但实际效果不如Sedgewick增量序列的希尔排序。

归并排序：

思想很简单，下面的图就一目了然了，总体思想就是“分解”和“合并”

最朴素的递归的思想：把整体数组分成两组，然后每组再分成两组，直到两个数组整体有序，再不断合并起来。

private static void MergeSort(int[] num, int n)
	{
		int temp[] = new int[n];
		MSort(num, temp, 0, n - 1);
	}

	public static void MSort(int num[], int temp[], int left, int right)
	{
		int center;
		if (left < right)
		{
			center = (left + right) / 2;
			MSort(num, temp, left, center);
			MSort(num, temp, center + 1, right);
			Merge(num, temp, left, center + 1, right);
		}
	}

	/**
	 * 
	 * @param num
	 *            待排数组
	 * @param temp
	 *            临时数组
	 * @param left
	 *            第一个数组的第一个位置
	 * @param right
	 *            第二个数组的第一个位置（两个数组是紧挨着的）
	 * @param end
	 *            最后一个位置
	 */
	private static void Merge(int[] num, int[] temp, int left, int right,
			int end)
	{
		int tmp = left;// 指向插入到temp数组的位置
		int leftEnd = right - 1;
		int sum = end - left + 1;
		while (left <= leftEnd && right <= end)
		{
			if (num[left] < num[right])
			{
				temp[tmp++] = num[left++];
			}
			else
			{
				temp[tmp++] = num[right++];
			}
		}
		while (left <= leftEnd)
		{
			temp[tmp++] = num[left++];
		}
		while (right <= end)
		{
			temp[tmp++] = num[right++];
		}
		for (int i = end; sum > 0; i--, sum--)//left已经改变，只能从后往前赋值
		{
			num[i] = temp[i];
		}
	}

归并排序在OJ上的结果：

由于分治的思想，并且一次merge的时间复杂度为O(n)，所以T(n)=T(n/2)+T(n/2)+O(n)=>T(n)=O(NlogN)，归并排序的平均时间复杂度，最差最好时间复杂度都是为O(NlogN)

在这里简单证明一下：

T(n)=2T(n/2)+O(n)=>T(n)=2^k*(T(n/(2^k)))+k*O(n)

取2^k=n => k=logn => T(n)=n*T(1)+O(nlogn) => T(n)=O(nlogn)

在上述代码中，临时数组temp[]是在MergeSort中就声明了，但是只有在Merge时才用到，在MSort时每次都被传来传去的，为什么不在Merge时声明呢？

上图给了解释，如果在Merge中声明，则要不断的声明然后释放，如果一开始就声明，Merge时用的都是一个数组。

非递归的归并排序

上面给出了递归方式的归并排序，我们知道递归对栈的开销很大，并且速度上也会慢，有没有非递归的归并排序呢？

当然上图是非递归的思想。我们可以看出，和递归的分治思想相比，非递归的感觉就是一种合并的过程，不断合并，直到有序。

private static void MergeSort(int[] num, int n)
	{
		int temp[] = new int[n];
		int length = 1;
		while (length < n)
		{
			MergePass(num, temp, n, length);//把num赋给了temp
			length = length * 2;
			MergePass(temp, num, n, length);//有可能这一步会多余，但是确保了最后结果会在num中
			length = length * 2;
		}

	}

	private static void MergePass(int[] num, int[] temp, int n, int length)
	{
		int i = 0;
		for (i = 0; i <= n - 2 * length; i = i + 2 * length)
		{
			Merge(num, temp, i, i + length, i + 2 * length - 1);
		}
		if (i + length < n)//剩余两个不等长的数组
		{
			Merge(num, temp, i, i + length, n - 1);
		}
		else//就剩一个
		{
			for (int j = i; j < n; j++)
			{
				temp[j] = num[j];
			}
		}
	}
	
	/**
	 * 
	 * @param num
	 *            待排数组
	 * @param temp
	 *            临时数组
	 * @param left
	 *            第一个数组的第一个位置
	 * @param right
	 *            第二个数组的第一个位置（两个数组是紧挨着的）
	 * @param end
	 *            最后一个位置
	 */
	private static void Merge(int[] num, int[] temp, int left, int right,
			int end)
	{
		int tmp = left;// 指向插入到temp数组的位置
		int leftEnd = right - 1;
		int sum = end - left + 1;
		while (left <= leftEnd && right <= end)
		{
			if (num[left] < num[right])
			{
				temp[tmp++] = num[left++];
			}
			else
			{
				temp[tmp++] = num[right++];
			}
		}
		while (left <= leftEnd)
		{
			temp[tmp++] = num[left++];
		}
		while (right <= end)
		{
			temp[tmp++] = num[right++];
		}
		//最后不再赋值给num
	}

非递归归并在OJ上的结果：

与递归的相比似乎没什么太大变化，时间复杂度都是O(NlogN)，Merge函数有了一点区别，不再最后再次赋给了num数组，为什么使最终结果在num数组中，MergeSort函数while循环中每次都执行两次Merge，当然在最后时，最后一个Merge有可能是多余的操作，但是为了确保结果在num中，也就不kao虑这些了。

在实际应用中，归并排序经常被用于外排序（全部元素不能在内存中一次完成）

快速排序：

该方法的基本思想是：

1．先从数列中取出一个数作为基准数(pivot)。

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数。

性能分析：

快排最好的情况是，每次正好中分，复杂度为O(nlogn)。最差情况，复杂度为O(n^2)，退化成冒泡排序

快排中有些要注意的问题：

第一个问题：pivot的选择

刚刚谈到快排的最坏情况。最快情况和pivot的选择有关，假设我们选择了第一个元素作为pivot，当待排序列为顺序时，每次将除了pivot以外的其他元素再次递归，

时间复杂度T(n)=T(n-1)+O(n)=>T(n)=O(n^2)，退化成冒泡排序。

经典的取pivot的方法有以下几种：

1. 取头、中、尾的中位数

public static int mid3(int[] arr, int left, int right)
	{
		int mid = (left + right) / 2;
		int temp;
		if (arr[left] > arr[mid])
		{
			temp = arr[left];
			arr[left] = arr[mid];
			arr[mid] = temp;
		}
		if (arr[left] > arr[right])
		{
			temp = arr[left];
			arr[left] = arr[right];
			arr[right] = temp;
		}
		if (arr[mid] > arr[right])
		{
			temp = arr[mid];
			arr[mid] = arr[right];
			arr[right] = temp;
		}
		temp = arr[mid];
		arr[mid] = arr[right - 1];
		arr[right - 1] = temp;
		//Sort(arr, left + 1, right - 2);
		return arr[right - 1];
	}

将头、中、尾按大小排好，把中当做pivot，移到right-1处，此时只需将left+1到right-2排序就可以了，因为left肯定比mid小，right肯定比mid大。

2. 取头

3. 取尾

4. 随机函数(随机函数的代价很大，不建议)

第二个问题：如果有元素等于pivot，是换还是不换呢？

1. 如果换，那当遇到全是一样的数，每一次都要交换，但是有一个好处是，pivot会移动到中间的地方，正好中分，符合快排最好的情况，复杂度为O(nlogn)

2. 如果不换，同样是全是一样的数，的确不用交换，i指针一直移到最后遇到j指针，pivot被移动到最后一位。分治时，右边没有元素，左边n-1个元素，重复一下。符合快排最坏情况，复杂度为O(n^2)

综上，还是换吧。

private static void quickSort(int[] arr, int n)
	{
		Sort(arr, 0, n - 1);
	}

	public static void Sort(int[] arr, int left, int right)
	{
		if (left >= right)
		{
			return;
		}
		int pivot = mid3(arr, left, right);
		int i = left;
		int j = right - 1;
		for (;;)
		{
			while (i < right - 1 && arr[++i] < pivot)
				;
			while (j > left + 1 && arr[--j] > pivot)
				;
			if (i < j)
			{
				int temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
			else
			{
				break;
			}
		}
		arr[right - 1] = arr[i];
		arr[i] = pivot;
		Sort(arr, left, i - 1);
		Sort(arr, i + 1, right);
	}

	public static int mid3(int[] arr, int left, int right)
	{
		int mid = (left + right) / 2;
		int temp;
		if (arr[left] > arr[mid])
		{
			temp = arr[left];
			arr[left] = arr[mid];
			arr[mid] = temp;
		}
		if (arr[left] > arr[right])
		{
			temp = arr[left];
			arr[left] = arr[right];
			arr[right] = temp;
		}
		if (arr[mid] > arr[right])
		{
			temp = arr[mid];
			arr[mid] = arr[right];
			arr[right] = temp;
		}
		temp = arr[mid];
		arr[mid] = arr[right - 1];
		arr[right - 1] = temp;
		// Sort(arr, left + 1, right - 2);
		return arr[right - 1];
	}

这里要注意的是，由于我把pivot放到了right-1处，所以要i指针先动，如果放到left，就先动j指针。同理，在取a[0]为pivot时，就先动j指针，取a[n-1]为pivot时，就先动i指针。上面已经描述了，其实真正排序的是left+1到right-2的数据，代码中i,j指针的初始值定义为left,right-1是因为我后面的判断是arr[++i]，在此简单说明一下。

看下在OJ上跑的结果：

第三个问题：小规模数据时，快排的速度。

由于传统快排是使用递归的，递归速度很慢，在小规模数据时（例如N<50），可能还不如插入排序快。

所以在小规模数据时，不要用传统快排。（或者在写快排时，设置一个Cutoff值，在规模小于Cutoff值时，调用插入排序，在规模大于Cutoff值时，再使用传统快排）。

加上cutoff以后：

private static void quickSort(int[] arr, int n)
	{
		Sort(arr, 0, n - 1);
	}

	public static final int CUTOFF = 50;

	public static void Sort(int[] arr, int left, int right)
	{
		if (right - left >= CUTOFF)
		{
			if (left >= right)
			{
				return;
			}
			int pivot = mid3(arr, left, right);
			int i = left;
			int j = right - 1;
			for (;;)
			{
				while (i < right - 1 && arr[++i] < pivot)
					;
				while (j > left + 1 && arr[--j] > pivot)
					;
				if (i < j)
				{
					int temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
				}
				else
				{
					break;
				}
			}
			arr[right - 1] = arr[i];
			arr[i] = pivot;
			Sort(arr, left, i - 1);
			Sort(arr, i + 1, right);
		}
		else
		{
			InsertSort(arr, left, right);
		}
	}

	public static int mid3(int[] arr, int left, int right)
	{
		int mid = (left + right) / 2;
		int temp;
		if (arr[left] > arr[mid])
		{
			temp = arr[left];
			arr[left] = arr[mid];
			arr[mid] = temp;
		}
		if (arr[left] > arr[right])
		{
			temp = arr[left];
			arr[left] = arr[right];
			arr[right] = temp;
		}
		if (arr[mid] > arr[right])
		{
			temp = arr[mid];
			arr[mid] = arr[right];
			arr[right] = temp;
		}
		temp = arr[mid];
		arr[mid] = arr[right - 1];
		arr[right - 1] = temp;
		return arr[right - 1];
	}

	private static void InsertSort(int[] num, int start, int end)
	{
		int temp = 0;
		int j = 0;
		for (int i = start; i <= end; i++)
		{
			temp = num[i];
			for (j = i; j > 0 && temp < num[j - 1]; j--)
			{
				num[j] = num[j - 1];
			}
			num[j] = temp;
		}
	}

在OJ上的结果：

感觉稍微快了点吧。

性能分析：

快速排序为什么快呢？因为每次将pivot交换后的位置都是pivot这个数的最终位置，他不像插入排序那样，位置始终在变化。

快排最好的情况是，每次正好中分，复杂度为O(nlogn)。最差情况是，如果pivot选的是第一个元素，那么排好序的情况耗时最多，复杂度为O(n^2)

快排的空间复杂度呢？快速排序在对序列的操作过程中只需花费常数级的空间。空间复杂度O(1)。 但需要注意递归栈上需要花费最少O(logn) 最多O(n)的空间。

参考资料：

1. http://blog.csdn.net/morewindows/article

2. http://www.cnblogs.com/luchen927/tag/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/

3. http://mooc.study.163.com/learn/ZJU-1000033001?tid=1000044001#/learn/content

转载于:https://my.oschina.net/hosee/blog/521245