八大排序初步-JAVA实现

[TOC]

八大排序初步-JAVA实现

内部排序（使用内存）

插入排序

基本思想

每趟将一个元素，按其关键字大小插入到它前面已排序的子序列中，使得插入后的子序列仍是排序的，一次重复，知道全部元素插入完毕。

直接插入排序(Straight Insertion Sort)

基本思想

先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。

算法描述

• 第i（1 ≤ i < n）趟，数据序列为{a0，a1，…, ai-1, …, an-1},其前面i个元素构成的子序列{a0,a1,…,ai-1}是排序的，将元素ai插入到子序列{a0，a1，…, ai-1}的适当位置，使插入后的子序列仍然是排序的，$a_i$的插入位置由关键字比较决定。
• 重复上述操作，n个元素共需n-1趟扫描，每趟将一个元素插入到它前面的子序列中。

代码实现（java）

public static void insertSort(int[] a) {
	for (int i=1; i<a.length; i++) {//i从1开始，n-1趟扫描
		int temp = a[i], j = i - 1;//每趟将a[i]插入到前面排序序列中

		while (j >= 0 && temp < a[j]) {//数组后移
			a[j+1] = a[j];//从后往前移动
			j--;//j递减
		}

		a[j+1] = temp;//temp值到达插入位置中
		print(a);//打印每次结果，可省略
	}
}

时间性能

对于具有n个记录的数据序列，要进行n-1趟排序。

最好情况：（初始队列状态是升序时）

每趟比较操作1次。共执行 $n-1$次。

每趟移动操作2次。共执行 $2(n-1)$ 次。

时间复杂度 $O(n)$。

最坏情况：（初始队列状态是反序时）

第i趟需要执行比较操作i次。共执行：

第i趟需要执行移动操作i+2次。共执行：

时间复杂度是 $O(n^2)$。

随机情况：（初始队列状态是随机排列）

查找一个元素的平均比较次数为 $(i+1)/2$
插入一个元素的平均需要移动全部元素的一半 $(i/2)$

平均比较次数为：

平均移动次数为：

空间复杂度是 $O(n^2)$。

空间复杂度

算法的辅助空间是一个临时变量temp，辅助空间复杂度 $S(n) = O(1)$。是一个就地排序。

稳定性：稳定

希尔（缩小量）排序(Shell’s Sort)

基本思想

先将整个待排序的记录序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全天记录进行依次直接插入排序。

算法描述

• 将一个数据序列分成若干组，每组由若干相隔一段距离的元素组成，这段距离称为增量，在一组内采用直接插入排序算法进行排序。

• 增量的初始值通常为数据序列长度的一半，以后每趟增量逐渐减小，最后值为1。随着增量逐渐减小，组数也减少，组内元素个数增加，整个序列则接近有序。当增量为1时，只有一组，元素是整个序列，再进行一趟直接插入排序即可。

代码实现(java)

public static void shellSort(int[] a) {
	for (int d=a.length/2; d>0; d/=2) {//d为增量，若干趟，每次减半
		for (int i=d; i<a.length; i++) {//一趟分为若干组，每组直接插入排序
			int temp = a[i], j = i - d;//每趟将a[i]插入到前面排序序列中
			
			while (j >= 0 && temp < a[j]) {//数组后移
				a[j + d] = a[j];//从后往前移动
				j -= d;//j递减，递减量变为d
			}
			
			a[j + d] = temp;//temp值到达插入位置中
		}
		
		print(a);//打印每趟结果，可以省略
	}
}

时间性能

时间复杂度比较复杂，实际所需要的时间取决于具体的增量序列

$$O(N^1+a) $$,0＜ａ＜１ ### 空间复杂度 $$ Ｏ(１)$$

稳定性：不稳定

交换排序

基本思想

两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。

应用交换排序基本思想的主要排序方法有：冒泡排序（Bubble sort）和快速排序（Quick sort）。

冒泡排序(Bubble Sort)

基本思想

比较相邻两个元素的关键字值，如果反序，则交换。若按升序排序，每一趟将被扫描的数据序列中的最大元素交换到最后位置，就像气泡从水里冒出来一样。

算法描述

外层for循环控制最多n-1趟扫描，内层for循环进行一趟扫描的比较和交换。其中，布尔变量exchange用做本趟扫描是否交换的标记。

代码实现(java)

没有优化的冒泡法

public static void bubbleSort1(int[] a) {
	int n = a.length;//数组长度
	
	for (int i=0; i<n-1; i++) {//外层循环
		for (int j=0; j<n-i-1; j++) {//内层循环
			if (a[j] > a[j + 1]) {
				int temp = a[j];//元素交换
				a[j] = a[j + 1];
				a[j + 1] = temp;
			}
		}
		
		print(a);//打印每次结果，可以省略
	}
}

设置一标志性变量index,用于记录每趟排序中最后一次进行交换的位置。由于index位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到index位置即可。

public static void bubbleSort2(int[] a) {
	int n = a.length - 1;	
	
	while (n > 0) {
		int index = 0;//每次开始设置标记
		
		for (int j=0; j<n; j++) {
			if (a[j] > a[j+1]) {
				index = j;//标记更改
				
				int temp = a[j];//元素交换
				a[j] = a[j+1];
				a[j+1] = temp;
			}
		}
		n = index;//重置 i 记录上次排序位置
		
		print(a);//打印每次结果，可以省略
	}
}

设置boolean变量，可提前结束循环

public static void bubbleSort3(int[] a) {
	boolean exchange = true;//设置标记，用于判断是否有交换
	
	for (int i=1; i<a.length && exchange; i++) {//外层循环用于控制n-1趟扫描
		exchange = false;//假定每趟开始初始没有交换
		
		for (int j=0; j<a.length-i; j++) {//内层循环，比较和交换
			if (a[j] > a[j+1]) {//比较大小
				int temp = a[j];//元素交换
				a[j] = a[j+1];
				a[j+1] = temp;
				
				exchange = true;//更改标记，有交换
				
				print(a);//打印每次结果，可以省略
			}
		}
	}
}

时间性能

最好情况：（初始队列状态是升序时）

一趟扫描即可完成排序。
所需关键字的比较次数：$n-1$
所需关键字的移动次数：$0$
最好时间复杂度：$O(N)$

最坏情况：（初始队列状态是降序时）

需要进行n-1趟排序。
每趟排序要进行的比较次数：$C_{max} = n(n-1)/2=O(n^2)$
每趟排序要进行的交换次数(每次比较交换3个)：$M_{max} = 3n(n-1)/2=O(n^2)$
最坏时间复杂度：$O(N^2)$

随机情况：（初始队列状态是随机排列）

越接近升序，冒泡的效率越高。
平均时间复杂度：$O(N^2)$

空间复杂度

只需要一个辅助空间用于交换两个元素或者需要一个标记变量
时间复杂度为：$O(1)$

稳定性：稳定

快速排序(Quick Sort)

基本思想

在数据序列中选择一个值作为比较的基准值，每趟从数据序列的两端开始交替进行，将小于基准值的元素交换到序列前端，将大于基准值的元素交换到序列后端，介于两者之间的位置则成为基准值的最终位置。

算法描述

首先选取第一个值38作为基准值，空出第一个元素位置：

• 设i、j分别是数据序列前后两端元素下标，将j位置元素与基准值比比较，若小，则移动到序列前端的下标为i的空位置，i+1，此时j位置空出来；
• 再将i位置元素与基准值比较，若大，则移动到序列后端的j空位置，j-1；
• 直到i=j，数据序列中的每个元素都与基准值比较过了，并已将小于基准值的元素移到前端，将大于基准值的元素移到后端，当前i(j)位置则是基准值的最终位置。

代码实现(java):

public static void quickSort(int[] a) {
	quickSort(a, 0, a.length-1);
}

/*对存在于b数组中begin~end之间的子序列进行一趟快速排序，递归算法*/
private static void quickSort(int[] b, int begin, int end) {
	if (begin >= 0 && begin < b.length && end >= 0 && end < b.length && begin < end) {//序列有效
		int i = begin, j = end;//i、j下标分别从子序列前后两端开始
		int guard = b[i];//设置子序列第一个值为基准值
		
		while (i != j) {//一趟排序
			while (i < j && b[j] > guard) {//从后往前寻找最小值，相等不移动
				j--;
			}
			
			if (i < j) {//子序列后端较小的元素向前移动
				b[i++] = b[j];
			}
			
			while (i < j && b[i]<=guard) {//从前往后寻找最大值，相等不移动
				i++;
			}
			
			if (i < j ) {//子序列前端较大元素向后移动
				b[j--] = b[i];
			}
		}
		b[i] = guard;//基准值到达最终位置
		
		quickSort(b, begin, j - 1);//前端子序列再排序，递归调用
		quickSort(b, i + 1, end);//后端子序列再排序，递归调用
		
		print(b);//打印每次结果，可以省略
	}
}

时间性能

快速排序的时间主要耗费在划分操作上，对长度为k的子序列进行划分，共需k-1次关键字的比较。

最好情况

每次划分所取的基准都是当前子序列的“中值”记录，划分的结果使得基准的左、右两个子序列的长度大致相等。
所需关键字的比较次数： $O(n*log_2n)$
所需关键字的移动次数：< $O(n*log_2n)$
最好时间复杂度：$O(n*log_2n)$

最坏情况

最坏情况是每次划分选取的基准都是当前排序子序列中关键字最小(或最大)的记录，划分的结果是基准左边的子序列为空(或右边的子序列为空)，而划分所得的另一个非空的子序列中记录数目，仅仅比划分前的排序子序列中记录个数减少一个。

每趟排序要进行的比较次数：$n-i(1≤i≤n-1) C_{max} = n(n-1)/2=O(n^2)$

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

随机情况：（初始队列状态是随机排列）

平均时间复杂度：$O(n*log_2n)$

空间复杂度：

快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀，则其递归树的高度为 $O(log_2n)$ ，故需栈空间为 $O(log_2n)$ 。最坏情况下，递归树的高度为O(n)，所需的栈空间为O(n)。

稳定性：不稳定

选择排序

基本思想

区分交换排序，尽可能减少重复的数据移动。

简单（直接）选择排序(SimpleSelection Sort)

基本思想

第一趟从n个元素的数据序列中选出关键字最小(或最大)的元素并放到最前(或最后)位置，下一趟再从n-1个元素中选出最小(大)的元素并放到次前(后)位置。

以此类推，经过n-1趟完成排序。

直接选择排序算法可用顺序表和单/双链表实现。

算法描述

在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；
然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，
依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

代码实现(java)

public static void selectSort(int[] a) {
	for (int i=0; i<a.length; i++) {//n-1趟排序
		int min = i;//设置标记，用于记录最小值的下标
		
		for (int j=i+1; j<a.length; j++) {//每趟在a[i]开始的子序列中寻找最小值
			if (a[j] < a[min]) {//按升序排序
				min = j;
			}
		}
		
		if (min != i) {
			int temp = a[min];//元素交换
			a[min] = a[i];
			a[i] = temp;
		}
		
		print(a);//打印每次结果，可以省略
	}
}

时间性能

关键字比较次数

无论数据序列的初始状态如何，在第i趟排序中选出最小关键字的记录，需做n-i次比较，因此，总的比较次数为：

记录的移动次数

当数据序列的初始状态为升序时，移动次数为 0
当数据序列的初始状态为降序时，每趟排序均要执行1次交换操作，总的移动次数取最大值 $3(n-1)$

随机情况

直接选择排序的平均时间复杂度为O(n2)

空间复杂度

$$O(1)$$

需要临时变量temp做交换的中间变量。

稳定性：不稳定

堆排序(Heap Sort)

基本思想

是完全二叉树的应用，是充分利用完全二叉树特性的一种选择排序，对直接选择排序的有效改进。减少重复比较次数，每趟利用前一趟的比较结果，提高算法效率。

堆定义

具有n个元素的序列（k1,k2,…,kn),当且仅当满足

时称之为最小堆或最大堆。

由堆的定义可以看出，堆顶元素（即第一个元素）必为最小项（小顶堆）。若以一维数组存储一个堆，则堆对应一棵完全二叉树，且所有非叶结点的值均不大于(或不小于)其子女的值，根结点（堆顶元素）的值是最小(或最大)的。

• 大顶堆序列：{96, 83, 27, 38, 11, 09}
• 小顶堆序列：{12, 36, 24, 85, 47, 30, 53, 91}

将数据序列“堆”成树状，每趟只遍历树中的一条路径。(要求是具有“堆”特性的完全二叉树。
二叉树性质5：完全二叉树中第i(0 ≤ i < ｎ)个结点，如果有孩子，则左孩子为第2i+1个结点，右孩子为第2i+2个结点。)

算法描述

初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树（一维数组存储二叉树），调整它们的存储序，使之成为一个堆，将堆顶元素输出，得到n 个元素中最小(或最大)的元素，这时堆的根节点的数最小（或者最大）。

然后对前面(n-1)个元素重新调整使之成为堆，输出堆顶元素，得到n 个元素中次小(或次大)的元素。

依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。

创建最小堆(将n个待排序的数建成堆)

建堆方法：对初始序列建堆的过程，就是一个反复进行筛选的过程。

• n个结点的完全二叉树，则最后一个结点是第个结点的子树。
• 筛选从第个结点为根的子树开始，该子树成为堆。
• 之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。

如图建堆初始过程：无序序列：{ 49，38，65，97，76，13，27，49 }

堆排序(输出堆顶元素后，怎样调整剩余n-1个元素，使之成为一个新堆)

• 设有m个元素的堆，输出堆顶元素后，剩下m-1个元素。将堆底元素送入堆顶（（最后一个元素与堆顶进行交换），堆被破坏，其原因仅是根结点不满足堆的性质。
• 将根结点与左、右子树中较小元素的进行交换。
• 若与左子树交换：如果左子树堆被破坏，即左子树的根结点不满足堆的性质，则重复方法（ii）。
• 若与右子树交换，如果右子树堆被破坏，即右子树的根结点不满足堆的性质。则重复方法（ii）。
• 继续对不满足堆性质的子树进行上述交换操作，直到叶子结点，堆被建成。

称这个自根节点到叶子节点的调整过程为筛选。如图：

代码实现(java)

public static void heapSort(int[] a) {
	heapSort(a, true);
}

 //堆排序，若bol取值为true，升序排序，创建最大堆；否则降序，创建最小堆
public static void heapSort(int[] a, boolean bol) {//从最底层子树开始创建最小(大)堆，最底层的树根节点为(n/2-1)
	System.out.println("最"+((!bol?"小":"大")+"堆："));
	for (int i=a.length/2-1; i>=0; i--) {//创建最小/大堆，根节点值最小/大
		sift(a, i, a.length - 1, !bol);
		print(a);//打印每次结果，可以省略
	}
	
	System.out.println();//打印结果，可以省略
	
	for (int i=a.length-1; i>0; i--) {//每趟将最小(大)值交换到后面，在调整成堆
		int temp = a[0];//元素交换
		a[0] = a[i];
		a[i] = temp;
		
		sift(a, 0, i - 1, !bol);
		
		print(a);//打印每次结果，可以省略
	}
}

//将a数组中以parent为根的子树调整成最小/大堆，子序列范围为parent～end。
public static void sift(int[] a, int parent, int end, boolean minheap) {
	int child = 2*parent + 1;//child是parent的左孩子
	int value = a[parent];//value是树的根，child为parent结点的左孩子
	
	while (child <= end) {//沿较小(大)值孩子结点向下筛选
		if (child<end && (minheap ? a[child]>a[child+1]:a[child]<a[child+1])) {//数组元素比较(改成 < 为最大堆)
			child++;//确定为左右孩子中最小(大)的一个
		}
		
		if (minheap ? value>a[child] : value < a[child]) {//若父母结点值较小(大)
			a[parent] = a[child];//将较小(大)孩子结点值向上移动
			parent = child;//parent、child两者都向下一层
			child = 2*parent + 1;
		}
		
		else break;
	}
	
	a[parent] = value;//当前子树的原根值调整后的位置
}

时间性能

设树深度为k，$k=[log_2n]+1$ 。从根到叶的筛选，元素比较次数至多2(k-1)次，交换记录至多k 次。所以，在建好堆后，排序过程中的筛选次数不超过下式：

$$2([log_2(n-1)]+[log_2(n-2)]+...+log_2)<2n*([log_2n])$$

而建堆时的比较次数不超过4n 次，因此堆排序最坏情况下，时间复杂度也为：$O(n*logn)$

空间复杂度

$$O(1)$$

稳定性：不稳定

归并排序（Merge Sort）

基本思想

将两个排序的子序列合并，形成一个排序的数据序列，又称为两路归并排序。

算法描述

n个元素的数据序列可看成是由n个长度为1的排序自序列组成，反复将相邻的两个子序列归并成一个排序的子序列，直到合并成一个序列，则排序完成。

代码实现(java)

public static void mergeSort(int[] a) {//归并排序(升序)
	int[] b = new int[a.length];//拷贝数组
	int n = 1;//已排序的子序列长度，初值为1
	
	while (n < a.length) {
		mergepass(a, b, n);//一趟排序，将a数组中各子序列归并到b中
		n *= 2;//子序列长度加倍
		
		if (n < a.length) {
			mergepass(a, b, n);//将b组中各子序列再归并到a中
			n *= 2;
		}
	}
}

public static void mergepass(int[] a, int[] b, int n) {//一趟归并
	int i = 0;
	
	while (i < a.length - 2*n + 1) {//将a中若干相邻子序列归并到b中
		merge(a, b, i ,i+n, n);//一次归并
		
		i += 2*n;
	}
	
	print(a);//打印每次结果，可以省略
}

public static void merge(int[] a, int[] b, int begin1, int begin2, int n) {//一次归并
	int i = begin1, j = begin2, k = begin1;
	
	while (i < begin1+n && j<begin2+n && j<a.length) {//将a中两个相邻子序列归并到b中
		if (a[i] < a[j]) {//（升序）将较小值复制到b中
//	        if (X[i]>X[j])                                 //（降序）将较大值复制到b中
			b[k++] = a[j++];
		} else {
			b[k++] = a[j++];
		}	
	}
	
	while (i<begin1+n && i<a.length) {//将前一个子序列剩余元素复制到b中，子序列长度可能不足n
		b[k++] = a[i++];
	}
	
	while (j<begin2+n && j<a.length) {//将后一个子序列剩余元素复制到b中
		b[k++] = a[j++];
	}
}

时间性能

n个元素的归并排序，每趟比较n-1次，共进行$log_2n$趟

时间复杂度为

$$N(n*log_2n)$$

空间复杂度

归并排序需要$O(N)$容量的附加空间，与数据序列的存储容量相等，空间复杂度为$O(N)$

稳定性：稳定

桶排序/基数排序(Radix Sort)

桶排序

是将阵列分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）。当要被排序的阵列内的数值是均匀分配的时候，桶排序使用线性时间$O(n)$。但桶排序并不是比较排序，他不受到$O(n*logn)$下限的影响。

简单来说，就是把数据分组，放在一个个的桶中，然后对每个桶里面的再进行排序。

多关键字排序：

最高位优先法（MSD/Most Significant Digit first)

认为习惯思维是高位优先方法，排序方式由键值的最左边开始。

最低位优先法（LSD/Least Significant Digit first)

计算机通常会选择低位优先方法，排序方式由键值的最右边开始。

基数排序方法对任一子关键字排序时必须借助于另一种排序方法，而且这种排序方法必须是稳定的。

对于多关键字拆分出来的子关键字，它们一定位于0-9这个可枚举的范围内，这个范围不大，因此用桶式排序效率非常好。

对于多关键字排序来说，程序将待排数据拆分成多个子关键字后，对子关键字排序既可以使用桶式排序，也可以使用任何一种稳定的排序方法。

基本思想

基数排序的总体思路就是将待排序数据拆分成多个关键字进行排序，也就是说，基数排序的实质是多关键字排序。利用桶排序的思想，基数排序过程无须比较关键字，而是通过“分配”和“收集”过程来实现排序。

算法描述

是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
设待排序的数据元素关键字是m位d进制整数（不足m位的关键字在高位补0）。

1.设置d个桶，令其编号分别为0,1,2…. d-1。
2.首先，按关键字最低位的数值一次把各数据元素放到相应的桶中。
3.然后，按照桶号从小到大和进入桶中数据元素的先后次序收集分配在各桶中的数据元素。
4.这样就形成了数据元素集合的一个新的排列，此为一次基数排序。
5.重复m次，就得到了排好序的数据元素序列。

代码实现(java)：

public static void RadixSort(int[] a) {
	RadixSort(a, countMaxLength(a));
}

public static void RadixSort(int[] a, int d) {//d表示最大的数有多少位
	int k = 0;//一次基数排序的辅助变量
	int n = 1;//表示位数值
	int m = 1;//控制键值排序依据在哪一位，从各位开始
	int[][]temp = new int[10][a.length];//(桶)数组的第一维表示可能的余数0-9
	int[]order = new int[10];//(桶的一维标记数组)数组orderp[i]用来表示该位是i的数的个数
    
	while(m <= d) {//比较位数小于数组最大位数为循环条件
		for(int i=0; i<a.length; i++) {//按关键字最低位的数值一次把各数据元素放到相应的桶中
			int lsd = ((a[i] / n) % 10);//计算余数
			temp[lsd][order[lsd]] = a[i];//按照余数将数组分桶
			order[lsd] ++;//记录余数是lsd的个数
		}

		for(int i=0; i<10; i++) {//按照桶号从小到大和进入桶中数据元素的先后次序收集分配在各桶中的数据元素
			if(order[i] != 0) {//order数组若为空，则表示没有该桶号
				for(int j=0; j<order[i]; j++) {//一次基数排序
					a[k] = temp[i][j];
					k ++;
				}
			}
			order[i] = 0;
		}
        
		n *= 10;//最大位数还原
		k = 0;//辅助变量还原
		m ++;//最低位数+1
        
		print(a);//打印每次结果，可以省略
    }     
}

//[基数排序]计算一个数组中最大位数
public static int countMaxLength(int[] a) {
	String temp;		//将数字转换为字符串用于计算位数
	int result = 1;			//记录最大位数结果
	
	for (int i=0; i<a.length; i++) {
		temp = String.valueOf(a[i]);
		
		if (temp.length() > result) {
			result = temp.length();
		}
	}
	
	return result;
}

稳定性：稳定

排序比较

时间复杂度

平方阶$ O(n^2) $排序

直接插入、直接选择和冒泡排序

线性对数阶$ O(nlog_2n) $排序

快速排序、堆排序和归并排序

$ O(n1+§) $排序,§是介于0和1之间的常数。

希尔排序

线性阶$ O(n) $排序

基数排序

说明

当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至$O(n)$；

而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为$O(n2)$；

原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。

稳定的排序算法

冒泡排序、插入排序、归并排序和基数排序

不稳定的排序算法

选择排序、快速排序、希尔排序、堆排序

关于如何选择排序方法

• 待排序的记录数目n的大小；
• 记录本身数据量的大小，也就是记录中除关键字外的其他信息量的大小；
• 关键字的结构及其分布情况；
• 对排序稳定性的要求。

设待排序元素的个数为n

当n较大，则应采用时间复杂度为O(nlog2n)的排序方法

快速排序、堆排序或归并排序序。

• 快速排序
  是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
• 堆排序
  如果内存空间允许且要求稳定性的，
• 归并排序
  它有一定数量的数据移动，所以我们可能过与插入排序组合，先获得一定长度的序列，然后再合并，在效率上将有所提高。

当n较大，内存空间允许，且要求稳定性

归并排序

当n较小，可采用直接插入或直接选择排序

• 直接插入排序
  当元素分布有序，直接插入排序将大大减少比较次数和移动记录的次数。
• 直接选择排序
  元素分布有序，如果不要求稳定性，选择直接选择排序

一般不使用或不直接使用传统的冒泡排序

基数排序

它是一种稳定的排序算法，但有一定的局限性：

• 关键字可分解。
• 记录的关键字位数较少，如果密集更好
• 如果是数字时，最好是无符号的，否则将增加相应的映射复杂度，可先将其正负分开排序。

外部排序（内存和外存相结合）

暂无

辅助方法

public static void print(int[] a) {//打印数组方法
	for(int i=0; i<a.length; i++) {
		System.out.print(a[i] + " ");
	}
	System.out.println();
}