排序（Sort） 原
排序（Sort）
1、概述
排序是计算机程序设计中的一种重要操作。如果数据能够根据某种规则排序，就能大大挺高数据处理的算法效率。
1．基本概念
排序就是整理文件中的记录，使之按关键字递增（或递减）的次序排列起来。
排序的对象是文件，它由一组记录组成。每条记录则由一个或若干个数据项（或域）组成。
关键字项就是可用来标识一个记录的一个或多个组合的数据项。该数据项的值称为关键字（key）。需要注意的是，在不易产生混淆时，可将关键字项简称为关键字。
用来作为排序运算的关键字，可以是数字类型，也可以是字符类型。关键字的选取应根据问题的要求而定。
2．稳定性
当待排序记录的关键字均不相同时，排序结果是惟一的，否则排序结果不惟一。
在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。
3．分类
根据排序时待排序的数据元素数量的不同，使得排序过程中涉及的存储器不同，可以将排序方法分为两类。 一类是整个排序过程在内存储器中进行，称为内部排序，简称内排序。
另一类是由于待排序元素数量太大，以至于内存储器无法容纳全部数据，排序需要借助外部存储设备才能完成，这类排序称为外部排序。
一般情况下，内排序适宜在记录个数不多的小文件中使用，外排序则适用于记录个数太多，不能一次将其全部记录放入内存的大文件。
对于外排序，可进一步分为两种方法：
- 合并排序法
- 直接合并排序法。
对于内排序，按策略进行划分，可以分为：
- 插入排序
- 交换排序
- 选择排序
- 归并排序
- 分配排序
4．排序算法分析
分析排序算法时，应该考虑比较的次数和数据移动的次数。
具体需要考虑以下3中情况的比较和移动次数：
- 最好情况（通常是数据已经排序）
- 最坏情况（通常是数据按反序存放）
- 平均情况（数据是随机顺序的）
很多排序方法在这3种情况下的性能是迥然不同的，所以可以根据实际条件选择使用哪一种算法。
2、插入排序
插入排序的思想：
每次将一个待排序的记录按其关键字大小插入到前面已经排好序的子文件的适当位置，直到全部记录插入完成为止。
1．直接插入排序（Insertion Sort）
直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的有序表。
1>基本思想
假设待排序的记录存放在数组R[1……n]中，排序过程中，R被分为两个子区间R[1……i]和R[i+1……n]，其中R[1……i]是已经排好序的有序区；R[i+1……n]是当前未排序的部分。将当前无序区的第一个记录R[i+1]插入到有序区R[1……i]的适当位置，使R[1……i+1]变为新的有序区，每次插入一个数据，知道所有的数据有序为止。
2>算法步骤
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
- 1.从第一个元素开始，该元素可以认为已经被排序；
- 2.取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 3.如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
- 5.将新元素插入到该位置后；
- 6.重复步骤2~5。
3>java代码
// 插入排序
public static int[] insertionSort(int[] arr) {
int preIndex, temp;
//比较的论数
for (int i = 1; i < arr.length; i++) {
//当前下标的前一位下标
preIndex = i - 1;
//当前位置的元素
temp = arr[i];
//前一位下标不越界并且前一位的元素值大于当前位置的元素值
while (preIndex >= 0 && arr[preIndex] > temp) {
//移动元素位置
arr[preIndex + 1] = arr[preIndex];
//下标前移继续比较
preIndex--;
}
//插入相应位置
arr[preIndex + 1] = temp;
}
return arr;
}4>算法分析
①时间复杂度
对于具有n个记录的文件，要进行n-1趟排序。 各种状态下的时间复杂度如下表：
②空间复杂度
算法所需的辅助空间是一个监视哨，辅助空间负责度S(n)=O(1)，是一个就地排序。
③稳定性
直接插入排序是稳定的排序方法。
2．希尔排序（Shell Sort）
希尔排序是插入排序的一种，因D.L.Shell于1959年提出而得名。希尔排序也称作缩减增量排序（diminishing increment sort）
1>基本思想
先取定一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组，所有距离为d1的倍数的记录放在同一个组中，在各组内进行插入排序；然后，取第二个增量d2＜d1，重复上述的分组和排序，直至所取的增量dt=1（dt＜……＜d2＜d1），即所有记录放在同一组中进行直接插入排序为止。
2>算法步骤
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
- 1.选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
- 2.按增量序列个数k，对序列进行k 趟排序；
- 3.每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
3>java代码
// 希尔排序
public static void shellSort2(int[] arr) {
int j;
// 初始值为数组长度的一半，然后按照一半的一半递减至1
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
// 初始取值为数组长度的一半，然后加一递增，不能超过数组长度
for (int i = gap; i < arr.length; i++) {
int tmp = arr[i];// 取出数组的一半位置的元素。
// 比较步长两端的元素，如果后端小于前端
for (j = i; j >= gap && tmp - arr[j - gap] < 0; j -= gap) {
arr[j] = arr[j - gap];// 将前端的值赋予后端
}
// 此时j减去了gap则为前端的位置，将后端的值赋予前端。完成不同位置的元素交换。
arr[j] = tmp;
}
}
}4>算法分析
①增量序列的选择则
Shell排序的执行时间依赖于增量序列。
好的在增量序列的共同特征为：
- 最后一个增量必须为1；应尽量避免序列中的值（尤其是相邻的值）互为倍数的情况。
- 当n较大时，比较和移动的次数约在n^1.25 到1.6n^1.25 之间。
②时间复杂度
希尔排序的时间性能优于直接插入排序，原因如下：
- 当文件初态基本有序时，直接插入排序所需的比较和移动次数均较少。
- 当n值较小时，n和n^2的差别也较小，即插入排序的最好时间复杂度是O(n)和最欢的时间复杂度O(n^2)差别不大。
- 在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di组件缩小，分组数组件减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。因此，希尔排序在效率上较直接插入排序有较大的改进。
③稳定性
希尔排序是一种不稳定的排序方法。
3、交换排序
交换排序的基本思想：
两两比较待排序记录的关键字，发现两个记录的次序相反时，即进行交换，直到没有反序的记录为止。 应用交换排序基本思想的主要排序方法有冒泡和快速排序。
1．冒泡排序（Bubble Sort）
1>基本思想
设想被排序的记录关键字保存在数组R[1……n]中，将每个记录R[i]看做是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R；凡扫描到违反本原则的轻气泡，就使其向上“漂浮”。如此反复进行，直到最后任何两个气泡都轻者在上，重者在下为止。
2>算法步骤
- 1.比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
- 3.针对所有的元素重复以上的步骤，除了最后一个；
- 4.重复步骤1~3，直到排序完成。
3>java代码
// 冒泡排序
public static void bubbleSort(int[] arr) {
// 比较的轮数
for (int i = 0; i < arr.length - 1; i++) {
// 每轮比较的次数
for (int j = 0; j < arr.length - 1 - i; j++) {
// 从小到大排序
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}4>算法分析
①时间复杂度
若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值：
Cmin=n-1；Mmin=0
冒泡最好的时间复杂度为O(n)。
若成绩是文件是反序的，需要进行n-1趟排序。每趟排序要进行n-i此关键字的比较（1≤i≤n-1），且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：
Cmax=n(n-1)/2=O(n^2)；Mmax=3n(n-1)/2=O(n^2)
冒泡的最坏时间复杂度为O(n^2)。
冒泡算法的平均时间复杂度为O(n^2)。
②稳定性
冒泡排序是就地排序，且它是稳定的。
2．快速排序（Quick Sort）
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法（Divide-and-ConquerMethod）。
1>基本思想
将原有问题分解为若干个规模更小但结构与原问题相似的子问题，递归地解这些子问题。然后将这些子问题的解组合为原问题的解。然后将这些子问题的解组合为原问题的解。
2>算法步骤
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
- 1.从数列中挑出一个元素，称为 “基准”（pivot）；
- 2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
3>java代码
// 快速排序
public static void fastSort(int[] arr, int left, int right) {
// 最小位置
int minIndex = left;
// 最大位置
int maxIndex = right;
// 三方变量
int temp = 0;
// 最大和最小位置不相等时
if (minIndex < maxIndex) {
// 三方变量从最小位置开始取值比较
temp = arr[minIndex];
// 当最大和最小位置不重叠时
while (minIndex != maxIndex) {
// 小位置没有越过大位置，并且大位置的值大于等于temp的取值
while (maxIndex > minIndex && arr[maxIndex] >= temp) {
// 大位置向左移
maxIndex--;
}
// 否则，小位置的元素取大位置的元素
arr[minIndex] = arr[maxIndex];
// 小位置没有越过大位置，并且小位置的元素值小于等于三方变量
while (minIndex < maxIndex && arr[minIndex] <= temp) {
// 小位置右移
minIndex++;
}
// 否则，大位置的元素取小位置的元素
arr[maxIndex] = arr[minIndex];
}
// 停止处的小位置去三方变量的值。
arr[maxIndex] = temp;
// 左半数组重复上面的操作
fastSort(arr, left, minIndex - 1);
// 右半数组重复上面的操作
fastSort(arr, maxIndex + 1, right);
}
}4>算法分析
快速排序的时间主要耗费在划分操作上，对长度为k的区间进行划分，共需k-1次关键字的比较。
①时间复杂度
最坏情况是每次划分宣州区的基准都是当前无序区中关键字最小（或最大）的记录，划分的结果是基准左边的子区间为空（或右边的子区间为空），而划分所得的另一个非空的子区间中记录数目仅仅比划分前的无序区中记录个数减少一个。
因此，快速排序必须做n-1此划分，第i此划分开始区间长度为n-i+1，所需的比较次数为n-i（1≤i≤n-1），故总的比较次数达到最大值：
Cmax=n(n-1)/2=O(n^2)
最好情况下，每次划分所取的基准都是当前无序区的“中值”记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数为：O(nlgn)。 平均时间复杂度为：O(nlgn)。
②空间复杂度
快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀，则其递归树的高度为O(lgn)，故递归后需要栈空间为O(lgn)。最坏情况下，递归树的高度为O(n)，所需的栈空间为O(n)。
③稳定性
快速排序是非稳定的。
4、选择排序
选择排序的基本思想：
每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。
选择排序方法主要有一下两种：直接选择排序（或称简单选择排序）和堆排序。
1．直接选择排序（Selection Sort）
1>基本思想
第i趟排序开始时，当前有序区和无序区分别为R[1……i-1]和R[i……n](1≤i≤n-1)，该趟排序则是从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第一个记录R[i]交换，是R[1……i]和R[i+1……n]分别变为新的有序区和新的无序区。因为每趟排序均使有序区中增加了一个记录，且有序区中的记录关键字均不大于无序区无序区轰炸过记录的关键字，即第i趟排序之后R[1……i].keys≤R[i+1……n].keys，所以进行n-1趟排序之后有R[1……n-1].keys≤R[n].key，即经过n-1趟排序之后，整个文件R[1……n]递增有序。
2>算法步骤
n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：
- 1.初始状态：无序区为R[1..n]，有序区为空；
- 2.第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
- 3.n-1趟结束，数组有序化了。
3>java代码
//直接选择排序
public static void SelectionSort(int[] arr) {
int minIndex,temp;
for(int i = 0;i<arr.length;i++) {
minIndex=i;
for(int j=i+1;j<arr.length;j++) {
if(arr[j]<arr[minIndex]) {
minIndex = j;
}
}
temp = arr[i];
arr[i] =arr[minIndex];
arr[minIndex]=temp;
}
}4>算法分析
①时间复杂度
直接选择排序的平均时间复杂度为O(n^2)。
②稳定性
直接选择排序是一个就地排序，并且是不稳定的。
2．堆排序（Heap Sort）
堆排序是利用完全二叉树进行排序的方法。
堆有大根堆（根结点的关键字值最大的堆）和小根堆（根结点关键字值最小）之分。
堆排序利用了大根堆（或小根堆）堆顶记录的关键字最大（或最小）这一特征，使得在当前无序区中选取最大（或最小）关键字的记录变得简单。
1>基本思想
大根堆排序思想：
首先将初始文件R[1……n]建成一个大根堆，此堆的初始的无序区；将关键字最大的记录R[1]（即堆顶）堆顶和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1……n-1]和有序区R[n]，且满足R[1……n-1].keys≤R[n].keys，由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1……n-1]调整为堆；然后再次将R[1……n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1……n-2]和有序区R[n-1……n]，且仍满足关系R[1……n-2].keys≤R[n-1……n].keys。同样要将R[1……n-2]调整为堆。重复以上步骤，直至按关键字有序。
2>算法步骤
- 1.将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
- 2.将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
- 3.由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
3>java代码
//交换值
private static void swap(int[] arr,int biggerIndex,int rootIndex) {
int temp=arr[rootIndex];
arr[rootIndex]=arr[biggerIndex];
arr[biggerIndex]=temp;
}
//调整大根堆
private static void adjustHeap(int[] arr,int rootIndex,int lastIndex) {
//从根结点开始往下调整
int biggerIndex = rootIndex;
int leftChildIndex=rootIndex * 2+1;
int rightChildIndex=rootIndex*2+2;
if(rightChildIndex<=lastIndex) {//如果右结点存在，则左结点一定存在
if(arr[rightChildIndex]> arr[rootIndex]||arr[leftChildIndex]>arr[rootIndex]) {
//将子节点更大的元素下标赋值给biggerIndex
biggerIndex = arr[rightChildIndex]>arr[leftChildIndex]?rightChildIndex:leftChildIndex;
}
}else if(leftChildIndex<=lastIndex) {//保证左结点存在，且不越界
if(arr[leftChildIndex]>arr[rootIndex]) {
biggerIndex = leftChildIndex;
}
}
if(biggerIndex!=rootIndex) {
swap(arr, biggerIndex, rootIndex);
adjustHeap(arr, biggerIndex, lastIndex);
}
}
//构建大根堆
private static void buildMaxHeap(int[] arr,int lastIndex) {
//从最后一个元素的父结点开始进行调整，一直调整到根结点结束
int j=(lastIndex-1)/2;
while(j>=0) {
int rootIndex = j;
adjustHeap(arr, rootIndex, lastIndex);
j--;
}
}
//堆排序
public static void heapSort(int[] arr,int len) {
int lastIndex = len -1;
//构建最大堆
buildMaxHeap(arr, lastIndex);
while(lastIndex>0) {
swap(arr, 0, lastIndex);
if(--lastIndex==0) {//剩余元素个数为1，排序结束，跳出循环
break;
}
adjustHeap(arr, 0, lastIndex);
}
}4>算法分析
堆排序的时间主要由建立初始堆和反复重建堆这两部分的时间开销构成，他们均是通过调用heapSort实现的，
①时间复杂度
堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。
由于建初始堆岁序的比较次数较多，所欲堆排序不适宜与记录数较少的文件。
②空间复杂度
堆排序是就地排序，辅助空间为O(1)
③稳定性
堆排序是一种不稳定的排序方法。
5、归并排序（Merge Sort）
归并排序是将两个或两个以上的有序表组合成一个新的有序表。
1>基本思想
先将N个数据看成N个长度为1的表，将相邻的表成对合并，得到长度为2的N/2个有序表，进一步将相邻的合并，得到长度为4的N/4个有序表，一次类推，知道所有数据均合并成一个长度为N的有序表为止。
2>算法步骤
- 1.把长度为n的输入序列分成两个长度为n/2的子序列；
- 2.对这两个子序列分别采用归并排序；
- 3.将两个排序好的子序列合并成一个最终的排序序列。
3>java代码
// 合并数据
private static void merge(int[] arr,int left,int center,int right) {
int[] newArr = new int[arr.length];
int mid = center+1;
int third = left;
int tmp = left;
while(left <=center&& mid<=right) {
if(arr[left]<=arr[mid]) {
newArr[third++]=arr[left++];
}else {
newArr[third++]=arr[mid++];
}
}
while(mid<=right) {
newArr[third++]=arr[mid++];
}
while(left<=center) {
newArr[third++]=arr[left++];
}
while(tmp<=right) {
arr[tmp]=newArr[tmp++];
}
}
//排序
private static void sort(int[] arr,int left,int right) {
if(left>=right) {
return;
}
int center = (left+right)/2;
sort(arr, left, center);
sort(arr, center+1, right);
merge(arr, left, center, right);
}
//归并排序
public static void mergeSort(int[] arr) {
sort(arr, 0, arr.length-1);
}4>算法分析
①时间复杂度
归并排序的时间复杂度无论是在最好情况下，还是在最坏情况下均是O(nlgn)。
②空间复杂度
需要一个辅助向量来暂存两个有序子文件归并的结果，故其辅助空间复杂度为O(n)。
③稳定性
归并排序是一种稳定的排序。
6、外部排序
算法和数据结构的实现可以基于住存储器，也可以基于辅助存储器，但这会影响算法和数据结构的设计。
主存储器和辅助存储器的差别主要与存储介质中的访问速度、数据的存储量和数据的永久性有关。
访问辅助存储器比访问主存储器要慢很多，而外部排序的过程需要进行多次的主存储器和辅助存储器之间的交换。
调整内部排序算法使之应用于外部排序，这种思路的更普遍的问题是这样做不可能比设计一个新的尽量减少磁盘存取的算法更有效。
1．二路归并排序
进行外部排序的一个更好的方法源于归并排序。
1>基本思想
首先，按可用内存大小，将外存上喊n个记录的文件分成若干长度为l的子文件或段（segment），依次读入内存并利用有效的内部排序方法对它们进行排序，并将排序后得到的有序子文件重新写入外存。通常称这些有序子文件为归并段或顺串；然后对这些归并段进行逐趟归并，使归并段组件由小到大，直至整个有序文件为止。
2>算法步骤
- 1.把原来的文件分成两个大小相等的顺串文件。
- 2.从每个顺串文件中取出一个块，读入输入缓冲区中。
- 3.从每个输入缓冲区中取出第一条记录，把它们按照排好的顺序写入一个顺串输出缓冲区中。
- 4.从每个输入缓冲区中取出第二条记录，把它们按照排好的顺序写入另一个顺串输出缓冲区中。
- 5.在两个顺串输出缓冲区之间交替输出，重复这些步骤直到结束。当一个输入块用完时，从相应的输入文件独处第二个块。当一个顺串输出缓冲区已满时，把它写回相应的输出文件。
- 6.使用原来的输出文件作为输入文件，重复2至5步。在第二趟扫描中，每个输入顺串文件的前两条记录已经排好了次序。这样一来，就可以把这两个顺串归并成一个长度为4个元素的顺串输出。
- 7.对顺串文件的每一堂扫描产生的顺串越来越大，知道最后只剩下一个顺串。
2．置换选择排序
置换选择实际上是堆排序算法的一个微小变种。
1>算法步骤
- 从磁盘中独处数据到数组中，设置LAST=M-1.
- 建立一个最小值堆。
- 重复以下步骤，直到数组为空。 （1） 把具有最小关键码值的记录（根结点）送到输出缓冲区。 （2） 设R是输入缓冲区中的下一条记录。如果R的关键码值大于刚刚输出的关键码值，则把R放到根结点，否则使用数组中LAST位置的记录代替根结点，然后把R放到LAST位置，并设置LAST=LAST-1。 （3） 筛出根结点，重新排列堆。
3．多路归并排序
多路归并与二路归并类似。如果有B个顺串需要归并，从每个顺串中取出一个块放在主存中使用，那么B路归并算法仅仅查看B个值，并且选择最小的一个输出。把这个值从它的顺串中移出，然后重复这个过程。当任何顺串的当前块用完时，就从磁盘中独处这个顺串的下一个块。
一般来说，简历大的初始顺串可以把运行时间减少到标准归并排序的四分之一，使用多路归并可以进一步把时间减半。
7、排序算法性能表
本博文，部分参考十大经典排序算法（动图演示），所涉及的动图，均出自此博文！