惯用内部排序分析

package sort;

public class SelectSort {
	public void selectSort(int[] A) {
		for (int i = 0; i < A.length - 1; ++i) {
			for (int j = i + 1; j < A.length; ++j) {
				if (A[i] > A[j]) {
					int tmp = A[i];
					A[i] = A[j];
					A[j] = tmp;
				}
			}
		}
	}

	public void printArray(int[] A) {
		for (int i = 0; i < A.length; i++)
			System.out.print(A[i] + "\t");
		System.out.println();
	}

	public static void main(String[] args) {
		SelectSort ss = new SelectSort();
		int[] A = new int[] { 21, 30, 49, 30, 16, 9 };
		ss.selectSort(A);
		ss.printArray(A);
	}
}

package sort;

public class SelectSort {
	public void selectSort(int[] A) {
		for (int i = 0; i < A.length - 1; ++i) {
			int minIndex = i;
			for (int j = i + 1; j < A.length; ++j) {
				if (A[minIndex] > A[j])
					minIndex = j;
			}
			if (minIndex != i) {
				int tmp = A[i];
				A[i] = A[minIndex];
				A[minIndex] = tmp;
			}
		}
	}

	public void printArray(int[] A) {
		for (int i = 0; i < A.length; i++)
			System.out.print(A[i] + "\t");
		System.out.println();
	}

	public static void main(String[] args) {
		SelectSort ss = new SelectSort();
		int[] A = new int[] { 21, 30, 49, 30, 16, 9 };
		ss.selectSort(A);
		ss.printArray(A);
	}
}

此时我们在整个堆中去掉最后一个节点“9”，变成了一个新的堆：

堆表现如下：

然后再利用我们上面所说的方法，对这个新的堆做建堆操作，建堆完成后，我们再拿堆的根节点和最后一个节点交换。

通过上面的分析我们不难看出来，堆排序的步骤可以总结如下：建堆；拿堆的根节点和最后一个节点交换。

由此课件，对于包含n个数据元素的数据组而言，堆排序需要经过n-1次建堆的过程，每次建堆的作用就是选出此序列的最大值或者最小值，因为堆排序本质上还是一种选择排序，可能有同学要问了，为什么同样是选择排序，为什么堆排序就可以节省这么多时间呢？

解答：堆排序和直接选择排序的差别在于，堆排序可以通过树形结构保存部门比较结果，可以减少比较此数。对于直接选择排序，为了从a1，a2，a3，...，an中选出最小的数据，必须进行n-1次比较，然后在a2，a3，...，an中选出关键字最小的记录，又需要做n-2次比较，事实上，后面的n-2次比较中，有许多比较可能前面的n-1次比较中已经做过，但是由于前面一趟比较中并没有保留这些比较结果，所以后一趟比较中又要重复这些操作。堆排序可以通过树形结构的一些性质保留前面的部分比较结果，从而在这个方面提高了效率。

下面是堆排序的源代码：这是以最大堆为基础的，而且数组的下标是从1开始的，可以将下标为0的部分置0即可。

package programmer;

public class HeapSort {
	public void HeapAdjust(int[] a, int i, int size) { // i是被调整的节点，size是数组序列的大小
		int lchild = i * 2, rchild = 2 * i + 1, max = i;   //注意此时的数组下标是从1开始的，不是从0开始的
		if (i <= size / 2) {            //这是要保证i节点一定是非叶子节点
			if (lchild <= size && a[lchild] > a[max])
				max = lchild;
			if (rchild <= size && a[rchild] > a[max])
				max = rchild;
			if (max != i) {
				int tmp = a[max];
				a[max] = a[i];
				a[i] = tmp;
				HeapAdjust(a, max, size); // 调整以后以max节点为父节点的堆可能不平衡
			}
		}
	}

	public void HeapBuild(int[] a, int size) {
		int i;
		for (i = size / 2; i >= 1; i--)
			// 非叶节点的最大序号值为 size/2
			HeapAdjust(a, i, size);
	}

	public void Heapsort(int[] a, int size) {
		int i;
		HeapBuild(a, size);
		for (i = size; i >= 1; i--) {
			int tmp = a[i];   //将堆顶元素与堆的最后一个元素交换
			a[i] = a[1];
			a[1] = tmp;
			HeapAdjust(a, 1, i - 1);   //将size-1，开始重新建堆操作
		}
	}

	public static void main(String[] args) {
		int[] a = new int[] { 0, 21, 30, 49, 30, 21, 16, 9 };
		new HeapSort().Heapsort(a, a.length - 1);
		for (int i = 1; i < a.length; i++) {
			System.out.print(a[i]+"\t");
		}
	}
}

对于堆排序算法，假设有n向数据，需要n-1此建堆，每次建堆本身耗时lgn，则其时间复杂度为O(n*lgn)，堆排序算法的空间效率很好，只需要一个附加程序单元，其空间效率为O(1)，但是堆排序是不稳定的排序。

选择类的排序都是不稳定的排序。

2、交换排序：

我以前曾经认为：直接选择排序和堆排序中间也是有交换的，为什么它们没有被称作交换排序，其实不然，我们既然要对数据排序，那么数据交换是肯定存在的，但这并不代表所有的排序就都是交换排序，交换排序的绝大部分操作都是交换，而对于直接选择排序和堆排序，它们的主要操作是不断地进行选择，所以它们不能被称为交换排序。

常见的交换排序主要有两类：冒泡排序和快速排序。

（1）冒泡排序：

冒泡排序的算法思路十分简单，且容易实现，对于一个数组序列，使用冒泡排序，最好的情况下（就是数组序列本来就正序），只要进行一趟比较（无需交换）；最坏的情况下（数组序列逆序），要进行n-1趟比较。

现将冒泡排序的源代码给出：

package sort;

public class BubbleSort {
	public void bubbleSort(int[] A) {
		for (int i = 0; i < A.length - 1; ++i) {  //每一趟都能将一个最大值放在后面
			boolean tag = false;
			for (int j = 0; j < A.length - i - 1; ++j) {  
				if (A[j] > A[j + 1]) {    
					tag = true;
					int tmp = A[j];
					A[j] = A[j + 1];
					A[j + 1] = tmp;
				}
			}
			if (!tag) //如果在一趟比较中没有交换，则说明排序已经完成
				break;
		}
	}

	public static void main(String[] args) {
		BubbleSort bs = new BubbleSort();
		int[] A = new int[] { 9, 16, 21, 23, 30, 49, 21, 30 };
		bs.bubbleSort(A);
		new SelectSort().printArray(A);
	}
}

冒泡排序的时间效率是不确定的，最好的情况下，初始数据序列已经处于有序的状态下，只要执行一趟冒泡即可，执行n-1比较，无需交换操作；在最坏的情况下，初始数据序列完全逆序，算法要执行n-1趟冒泡，第i趟执行n-i次比较，执行n-i-1次数据交换，此时的比较总的次数是n*(n-1)/2。

冒泡排序的空间复杂度为O(1)，时间复杂度为O(n*n)，同时冒泡排序是稳定的排序。

（2）快速排序：

快速排序是一种速度非常快的交换排序的方法，它的基本思想是：从待排序的数据序列中任取一个数据（一般取第一个数据元素）作为分界值，所有比它小的数据元素一律放到左边，所有比它大的数据元素一律放到右边，这样经过一趟下来，该序列形成左右两个子序列，左边序列中数据元素都比分界值小，右边序列中数据元素都比分界值大。接下来对左、右两个子序列进行递归，对两个子序列重新选择中心元素进行规划调整，直到每个子序列中的元素个数只剩下一个，说明排序完成。

根据上面的分析，快速排序需要做三个事情：

A、选出指定的分界值

B、将所有比分界值小的数据元素放在左边

C、将所有比分界值大的数据元素放在右边

下面以一个数组序列9，-16，21，23，-30，-49，21，30，30

可以看出来，第一次快排过后，分界值9已经位于其最终的位置，（所谓最终的位置：就是当数组序列完全有序的时候，9也是处在那个位置），9左边的值比它小，9右边的值比它大。

下面是快速排序的源代码：

package sort;

public class QuickSort {
	public int partition(int[] A, int low, int high) {
		int i = low, j = high;
		int tmp = A[i];
		while (i < j) {
			while (i < j && tmp <= A[j])
				--j;
			if (i < j && tmp > A[j])
				A[i] = A[j];
			while (i < j && tmp >= A[i])
				++i;
			if (i < j && tmp < A[i])
				A[j] = A[i];
		}
		A[i] = tmp;
		return i;
	}

	public void quickSort(int[] A, int low, int high) {
		if (low < high) {
			int mid = partition(A, low, high);
			quickSort(A, low, mid - 1);
			quickSort(A, mid + 1, high);
		}
	}

	public static void main(String[] args) {
		QuickSort qs = new QuickSort();
		int[] A = new int[] { 9, -16, 21, 23, -30, -49, 21, 30, 30 };
		qs.quickSort(A, 0, A.length - 1);
		new SelectSort().printArray(A);
	}
}

快速排序的最差时间就是对于快速排序的每次中间值划分，总是会产生，一边有0个元素，另外一遍有k-1个元素，（设这个划分的子序列长度为k），则此时产生最差的时间复杂度。但是快速排序的平均时间复杂度是很好的，为O(n*lgn)，由于开苏排序需要递归栈，而递归栈使用栈的结构，因为快速排序的空间复杂度为O(lgn)，快速排序中包含很多跳跃式的交换，为此快速排序是不稳定的排序。

在现实生活中，我们为了防止出现快速排序最差的情况，通常采用如下的方法：

快速排序的随机化：

randomized-partition(A,low,high)

i=random(low,high)

exchange A[i],A[low]

return partition(A,low,high)

randomized-quicksort(A,low,high)

if(low<high)

then mid=randomized-partition(A,low,high)

randomized-quicksort(A,low,mid-1)

randomized-quicksort(A,mid+1,high)

经过随机化的快速排序出现最差时间复杂度的可能性大大降低。

3、插入排序：

插入排序是一类非常常见的排序，主要包括直接插入排序、shell排序和折半插入排序等。

（1）直接插入排序：

一次将待排序的数据元素按其关键字值的大小插入前面的有序序列。直接插入排序还是很好理解的，这里就不一一分析每个步骤了，直接给出源码：

package sort;

public class InsertSort {
	public void insertSort(int[] A) {
		int i, j;
		for (i = 1; i < A.length; ++i) {   //因为开始的一个元素肯定是有序的，所以从第2个元素开始
			int tmp = A[i];    
			j = i - 1;
			while (j >= 0 && tmp < A[j]) {   //注意循环的条件
				A[j + 1] = A[j];
				--j;
			}
			A[j + 1] = tmp;   //最后要把A[i]放到合适的位置上
		}
	}

	public static void main(String[] args) {
		InsertSort is=new InsertSort();
		int[] A = new int[] { 9, -16, 21, 23, -30, -49, 21, 30, 30 };
		is.insertSort(A);
		new SelectSort().printArray(A);
	}
}

直接插入排序的时间效率并不高，在最坏的情况下，所有元素比较次数为O(n*n)，但是元素正序的情况下，直接插入排序的时间复杂度为O(n)，直接插入排序的空间复杂度为O(1)，直接插入排序是稳定的。

（2）shell排序：

shell排序对直接插入排序进行了简单的改进：它通过加大插入排序中元素之间的间隔，并在这些有间隔的元素中进行插入排序，从而使数据项大跨度的移动。当这些数据项排过一趟排序后，shell排序算法减小数据项的间隔再进行排序，依次进行下去，当数据项之间的间隔为1时，说明此数据元素排序已经完成。

这些排序时的数据项之间的间隔被称为增量，用字符d来表示。

注：直接插入排序是shell排序的一种特例：直接使用d=1的shell排序就是插入排序。

下面以 9，-16，21，23，-30，-49，21，30，30序列为例进行shell排序。

设本次shell排序的d=4，如下面所示，元素下面的下划线表示此时这些元素正在排序：

9，-16，21，23，-30，-49，21，30，30——>-30，-16，21，23，9，-49，21，30，30

30，-16，21，23，9，-49，21，30，30——>30，-49，21，23，9，-16，21，30，30

30，-49，21，23，9，-16，21，30，30——>30，-49，21，23，9，-16，21，30，30

30，-49，21，23，9，-16，21，30，30——>30，-49，21，23，9，-16，21，30，30

上面的一系列操作完成额d=4的shell排序，接下来应该减小d，直到d=1为止，d=1的shell排序完成后，则整个序列已经是正序了。

由上面的分析我们可以看出，最终决定shell排序算法的关键就在于确定d序列的值，Knuth提出一种d序列的方法：该序列从1开始，d=3*d+1

可以得到这个序列分别为1、4、13、40...

如果需要反向计算d序列，则d=(d-1)/3。

现在已经知道了shell排序的算法和d序列的取值，下面写出shell排序的源代码：

package sort;

public class ShellSort {
	public void insertSort(int[] A, int start, int d) {
		for (int i = start + d; i < A.length; i += d) {
			for (int j = i; j >= d; j -= d)
				if (A[j] < A[j - d]) {
					int tmp = A[j];
					A[j] = A[j - d];
					A[j - d] = tmp;
				}
		}
	}

	public void shellSort(int[] A) {
		for (int i = A.length / 2; i > 2; i /= 2)   //这里使用的增量d是用数组序列长度的1/2、1/4、1/8等作为d
			for (int j = 0; j < i; ++j)
				insertSort(A, j, i);
		insertSort(A, 0, 1);
	}

	public static void main(String[] args) {
		ShellSort ss = new ShellSort();
		int[] A = new int[] { 9, -16, 21, 23, -30, -49, 21, 30, 30 };
		ss.shellSort(A);
		new SelectSort().printArray(A);
	}
}

shell排序比插入排序快很多，当d很大的时候，数据元素每一趟排序所要移动的元素的个数很少，但是数据元素移动的距离很长，这很有效率。当d减小时，每一趟排序需要移动的元素个数增加，但是此时的数组序列已经接近有序，这对于插入排序而言非常有利，正是这两种情况结合才是shell排序的效率变高。

shell排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，

步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些，一般认为是O(n^7/6)~O(n^1.5)，shell排序的空间复杂度

为O(1)，迄今为止，还没有找到shell排序的精确下界。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的

插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。

（3）折半插入排序：

折半插入排序是对直接插入排序的简单改进，对于直接插入排序而言，当第I-1趟需要将第i个元素插入到前面的0~i-1个元素序列中，它总是从i-1个

元素开始，逐个比较每个元素，知道找到它的位置，但是此时0~i-1个元素已经有序了，这显然没有利用这个性质，而折半插入排序则利用了这个性

质对直接插入排序作了一些改进。

注：此处介绍的折半插入，其实就是通过不断地折半来快速确定第i个元素的插入位置。这实际上是一种查找方法——折半查找，但是这种方法通常

在序列元素有序的情况下才可以显示出它真正的效率。

下面是折半插入排序的源代码：

package sort;

public class BinaryInsertSort {
	public void binaryInsertSort(int[] A) {
		int i, j;
		for (i = 1; i < A.length; ++i) {
			int tmp = A[i];
			int low = 0, high = i - 1;
			while (low <= high) {
				int mid = (low + high) / 2;
				if (tmp > A[mid])
					low = mid + 1;
				else if (tmp < A[mid])
					high = mid - 1;
				else {
					low = mid;
					break;
				}
			}
			for (j = i; j > low; --j)
				A[j] = A[j - 1];
			A[low] = tmp;    //这里和直接插入排序有些区别
		}
	}

	public static void main(String[] args) {
		BinaryInsertSort bis = new BinaryInsertSort();
		int[] A = new int[] { 9, -16, 21, 23, -30, -49, 21, 30, 30 };
		bis.binaryInsertSort(A);
		new SelectSort().printArray(A);
	}
}

我们要分清楚此时的折半插入不同于折半查找，这里要找出插入的节点，而查找是要查找出具体的树，虽然细节有点不同，但是两者的思想基本相同。

下面的斜体部分是折半插入的核心代码，从上面的分析我们可以看出，折半插入的时间复杂度为O(nlgn)，空间复杂度仍为O(1)，这是比较优越的一面。

但是折半插入排序是不稳定的排序。

4、归并排序：

归并排序的基本思想是将两个或者两个以上的有序序列合并成一个新的有序序列，为了方便讲解，我们此处以两个有序序列合并为一个有序序列为例。

我们将归并排序细化来讲，归并排序先将长度为n的无序序列看成是n个长度为1的有序子序列，，首先做两两合并，得到n/2个长度为2的有序子序列，再做两两合并，不断重复这个过程，最终可以得到一个长度为n的有序序列。

长度为n的数据序列，需要经过lgn此合并。

下面用具体的例子讲解归并的过程：

对于一组数据序列  21，30， 49， 30， 97， 62， 72， 8， 37， 16， 54

我们了解了归并排序的整个实现过程，现在给出归并排序的源代码：

package sort;

public class Mergesort {
	// 归并操作
	public void Merge(int[] source, int[] dest, int low, int mid, int high) {//这个函数就是对两个有序序列作归并排序
		int i = low, j = mid + 1, k = low;
		for (; i <= mid && j <= high; k++) {
			if (source[i] < source[j]) {
				dest[k] = source[i++];
			} else {
				dest[k] = source[j++];
			}
		}
		if (i <= mid) {
			while (i <= mid)
				dest[k++] = source[i++];
		}
		if (j <= high) {
			while (j <= high)
				dest[k++] = source[j++];
		}
	}

	// 内部使用递归，空间复杂度为n+logn
	public void MergeSort(int[] source, int[] target, int low, int high) {
		int mid;
		int[] temp = new int[target.length]; // 中间置换数组，这儿体现了空间复杂度
		if (low == high)
			target[low] = source[low];
		else {
			mid = (low + high) / 2;
			MergeSort(source, temp, low, mid);
			MergeSort(source, temp, mid + 1, high);
			Merge(temp, target, low, mid, high);
		}
	}

	public static void main(String[] args) {
		int[] source = new int[] { 21, 30, 49, 30, 97, 62, 72, 8, 37, 16, 54 };
		int[] dest = new int[source.length];
		new Mergesort().MergeSort(source, dest, 0, source.length - 1);
		for (int i = 0; i < dest.length; i++)
			System.out.print(dest[i] + "\t");
		System.out.println();
	}
}

从上面的算法实现可以看出来，归并排序需要递归地进行分解、合并，每进行一趟二路归并排序需要调用MergeSort()方法一次，每次执行MergeSort()方法需要执行n次，所以归并排序的时间复杂度为O(n*lgn)，但是归并排序的空间复杂度较差，为O(n)，它需要一个与原始序列一样大小的辅助序列。归并排序是稳定的。

5、桶排序：

桶排序并不是一种基于比较的排序方法，它是一种非常巧妙的排序方法，但这种排序方法要满足如下两个特征：

A、待排序列的所有值处于一个可枚举的范围内

B、待排序列所在的这个枚举范围不应该太大，否则排序开销太大了

下面从一般的角度上讲解一下桶排序，

将区间[0,1)划分成n个大小相等的子区间，每个桶大小为1/n，分别为[0,1/n)，[1/n,2/n)，......，[k/n,(k+1)/n)，......其中0<=A[1]，A[2]，......，A[n]<=1辅助数字B[0]，B[1]，......，B[n-1]是一个指针数组，指向桶，其中n*A[i]将[0,1)映射到[0,n)上，这些都是桶排序的重要应用。

下面通过一个例子来体现桶排序的奥秘：

例：将1至100的100个随机自然数，放入一个数组中，获取当前重复次数最多，而且数是最大的一个。

我们可以同桶排序，使用100个桶，（可以用一个数组来表示），Bucket[100]，这里我们假设数组下标从1开始，到100结束，则Bucket[i]中存放的是数i的次数，我们可以做一次遍历，将每次遇到i，则将Bucket[i]加1，这个遍历结束之后，我们只要一次打印出对应的Bucket[i]个i，下面是本例题的源码：

package programmer;

import java.util.Random;

public class MaxRandomNumber {
	public static int[] bucket = new int[100];

	public static void randomNumber() {
		for (int i = 0; i < 100;) {
			Random r = new Random();
			int tmp = r.nextInt(101);   //这是生成0~100之间整数的随机函数
			if (tmp != 0 && tmp != 1) {
				bucket[tmp - 1]++;    //显然我们这里的数组下标是从0开始的，为了和上面的讲解一致，则我们可以将数减1作为数组下标
				i++;
			}
		}
		int index = 0;
		int maxCount = 0;
		for (int i = 0; i < 100; i++) {
			if (bucket[i] >= maxCount) {
				maxCount = bucket[i];
				index = i;
			}
		}
		System.out.println((index + 1) + "--->" + maxCount);
	}

	public static void main(String[] args) {
		randomNumber();
		for (int i = 0; i < 100; i++)
			System.out.println((i + 1) + "-->" + bucket[i]);
		int sum = 0;
		for (int i = 0; i < 100; i++)
			sum += bucket[i];
		System.out.println(sum);
	}
}

如何确立一个桶的大小，一般情况下，一些题目给的条件相当隐晦，但是我们一旦确定了是使用桶排序的方法，一般可以这么做，找出序列中最大值max和最小值min，然后max-min确定桶大小和桶长度。

桶排序是一种非常优秀的排序算法，时间效率非常高，它只要经过两轮遍历，时间复杂度为O(n)，但是桶排序的空间开销很大，一般为O(n+m)其中m为桶数量，桶排序是稳定的排序方法.

6、基数排序：

基数排序不是一种常规的排序方法，它必须依赖于另外的排序方法，基数排序的总体思路是将待排序的数据拆分成多个关键字进行排序，基数排序的实质是“多关键字”排序。

多关键字排序思路：将待排序数据里的排序关键字拆分成多个排序关键字，第1个关键字、第2个关键字、第3个关键字......然后，根据子关键字对待排序数据进行排序。

多关键字排序有两种解决方法：

A、最高位优先法MSD

B、最低位优先法LSD

A中的方法一般是人的思维，但是计算机一般使用B方法，即最低位优先法。

下面以192，221，13，23为例进行分析

第一轮比较个位，对个位关键字进行排序后得到：221，192，13，23

第二轮比较十位，对十位关键字进行排序后得到：13，23，221，192

第三轮比较百位，对百位关键字进行排序后得到：13，23，192，221

从上面的分析可以看出来，基数排序对任一关键字排序时必须借助另一种排序方法，而且这种排序方法必须是稳定的。

从上面对桶排序的分析来看，桶排序是稳定的，而且桶排序也是基于关键字排序的，这是桶排序的两个要求：

A、待排序列的所有值处于一个可枚举的范围内

B、待排序列所在的这个枚举范围不应该太大，否则排序开销太大了

对于多个关键字拆分出来的子关键字，它们一定位于0~9这个可枚举的范围内，而且这个范围也不大，可以使用桶排序。

下面是利用基数排序来对数组进行排序的代码：

package sort;

public class MutiKeyRadixSort {
	public void mutilKeyRadixSort(int[] A, int radix, int d) {
		int[] tmp = new int[A.length];// 临时数组
		int[] buckets;
		for (int i = 0, rate = 1; i < d; ++i) {
			buckets = new int[radix];
			System.arraycopy(A, 0, tmp, 0, A.length);
			for (int j = 0; j < A.length; ++j) {
				int subKey = (tmp[j] / rate) % radix; // 计算机指定数据位上的关键字
				buckets[subKey]++;
			}
			for (int j = 1; j < radix; ++j)
				// 确定子关键字在buckets中位置及个数
				buckets[j] += buckets[j - 1];
			for (int m = A.length - 1; m >= 0; --m) { // 从后往前遍历是为了保持排序的稳定性
				int subKey = (tmp[m] / rate) % radix; 
				A[--buckets[subKey]] = tmp[m];   //每次在子关键字上比较后都要经历排序
			}
			rate *= radix;  //现在开始跳到高位
		}
	}

	public static void main(String[] args) {
		MutiKeyRadixSort mkrs = new MutiKeyRadixSort();
		int[] A = new int[] { 1100, 192, 221, 223, 12, 13 };
		mkrs.mutilKeyRadixSort(A, 10, 4);
		new SelectSort().printArray(A);
	}
}

其实上面的基数排序就是多轮桶排序，技术排序的时间复杂度为O(n*d)，其中d是要排序的位数，空间复杂度为O(n+m)，其中m为radix位数，就是关键字个数，同桶排序一样，基数排序也是稳定的。

其实对于基数排序，除了可以使用桶排序，也是使用任何一种稳定的排序方法。

上面就是内部排序的一些简要介绍，希望大家多多指正。