面试中常用排序算法实现（Java）
当我们进行数据处理的时候，往往需要对数据进行查找操作，一个有序的数据集往往能够在高效的查找算法下快速得到结果。所以排序的效率就会显的十分重要，本篇我们将着重的介绍几个常见的排序算法，涉及如下内容：
- 排序相关的概念
- 插入类排序
- 交换类排序
- 选择类排序
- 归并排序算法实现
一、排序相关的基本概念
排序其实是一个相当大的概念，主要分为两类：内部排序和外部排序。而我们通常所说的各种排序算法其实指的是内部排序算法。内部排序是基于内存的，整个排序过程都是在内存中完成的，而外部排序指的是由于数据量太大，内存不能完全容纳，排序的时候需要借助外存才能完成（常常是算计着某一部分已经计算过的数据移出内存让另一部分未被计算的数据进入内存）。而我们本篇文章将主要介绍内排序中的几种常用排序算法：
这里写图片描述
还有一个概念问题，排序的稳定性问题。如果Ai = Aj，排序前Ai在Aj之前，排序后Ai还在Aj之前，则称这种排序算法是稳定的，否则说明该算法不稳定。
二、插入类排序算法
插入类排序算法的核心思想是，在一个有序的集合中，我们将当前值插入到适合位置上，使得插入结束之后整个集合依然是有序的。那我们接下来就学习下这几种同一类别的不同实现。
1、直接插入排序
直接插入排序算法的核心思想是，将第 i 个记录插入到前面 i-1 个已经有序的集合中。下图是一个完整的直接插入排序过程：
这里写图片描述
整个程序的逻辑是从数组的第二个元素开始，每个元素都以其前面所有的元素为基本，找到合适的位置进行插入。对于这种按照从小到大的排序原则，程序使用一个临时变量temp保存当前需要插入的元素的值，从前面的子序列的最后一个元素开始，循环的与temp进行比较，一旦发现有大于temp的元素，让它顺序的往后移动一个位置，直到找到一个元素小于temp，那么就找到合适的插入位置了。
因为我们使用的判断条件是，key>array[j]。所以来说，插入排序算法也是稳定的算法。对于值相同的元素并不会更改他们原来的位置顺序。至于该算法的效率，最好的情况是所有元素都已有序，比较次数为n-1，最坏的情况是所有元素都是逆序的，比较次数为（n+2）（n-1）/2，所以该算法的时间复杂度为O（n*n）。
2、二分折半插入排序
既然我们每次要插入的序列是有序的，我们完全可以使用二分查找到合适位置再进行插入，这显然要比直接插入的效率要高一些。代码比较类似，不再做解释。
public static void halfInsertSort(int[] array){
for(int k=1;k<array.length;k++){
int key = array[k];
//找到合适的位置
int low,high,mid;
low = 0;high = k-1;
while(low <= high){
mid = (low+high)/2;
if(key == array[mid])break;
else if(key > array[mid]){
low = mid+1;
}else{
high = mid-1;
}
}
//low的索引位置就是即将插入的位置
//移动low索引位置后面的所有元素
for(int x=k-1;x>=low;x--){
array[x+1] = array[x];
}
array[low] = key;
}
//遍历输出有序队列内容
for(int key:array){
System.out.print(key + ",");
}
}
虽然，折半插入改善了查找插入位置的比较次数，但是移动的时间耗费并没有得到改善，所以效率上优秀的量可观，时间复杂度仍然为O(n*n)。
2、希尔排序
直接插入排序在整个待排序序列基本有序的情况下，效率最佳，但我们往往不能保证每次待排序的序列都是基本有序的。希尔排序就是基于这样的情形，它将待排序序列拆分成多个子序列，保证每个子序列的组成元素相对较少，然后通过对子序列使用直接排序。对于本就容量不大的子序列来说，直接排序的效率是相当优秀的。
希尔排序算法使用一个距离增量来切分子序列，例如：
这里写图片描述
如图，我们初始有一个序列，按照距离增量为4来拆分的话，可以将整个序列拆分成四个子序列，我们对四个子序列内部进行直接插入排序得到结果如下：
这里写图片描述
修改距离增量重新划分子序列：
这里写图片描述
很显然，当距离增量变小的时候，序列的个数也会变少，但是这些子序列的内部都基本有序，当对他们进行直接插入排序的时候会使得效率变高。一旦距离增量减少为1，那么子序列的个数也将减少为1，也就是我们的原序列，而此时的序列内部基本有序，最后执行一次直接插入排序完成整个排序操作。
下面我们看算法是的具体实现：
/*渐减delete的值*/
public static void ShellSort(){
int[] array = {46,55,13,42,94,17,5,70};
int[] delets = {4,2,1};
for (int i=0;i<delets.length;i++){
oneShellSort(array,delets[i]);
}
//遍历输出数组内容
for(int value : array){
System.out.print(value + ",");
}
}
/*根据距离增量的值划分子序列并对子序列内部进行直接插入排序*/
public static void oneShellSort(int[] array,int delet){
int temp;
for(int i=delet;i<array.length;i++){
//从第二个子序列开始交替进行直接的插入排序
//将当前元素插入到前面的有序队列中
if(array[i-delet] > array[i]){
temp = array[i];
int j=i-delet;
while(j>=0 && array[j] > temp){
array[j+delet] = array[j];
j -= delet;
}
array[j + delet] = temp;
}
}
}
方法比较简单，具体的实现和直接插入排序算法相近，此处不再做解释。
三、交换类排序
交换类的排序算法一般是利用两个元素之间的值的大小进行比较运算，然后移动外置实现的，这类排序算法主要有两种：
1、冒泡排序
冒泡排序通过两两比较，每次将最大或者最小的元素移动到整个序列的一端。这种排序相当常见，也比较简单，直接上代码：
public static void bubbleSort(int[] array){
int temp = 0;
for(int i=0;i<array.length-1;i++){
for(int j =0;j<array.length-1-i;j++){
if(array[j]>array[j+1]){
//交换两个数组元素的值
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
//遍历输出数组元素
for(int value : array){
System.out.print(value + ",");
}
}
2、快速排序
快速排序的基本思想是，从序列中任选一个元素，但通常会直接选择序列的第一个元素作为一个标准，所有比该元素值小的元素全部移动到他的左边，比他大的都移动到他的右边。我们称这叫做一趟快速排序，位于该元素两边的子表继续进行快速排序算法直到整个序列都有序。该排序算法是目前为止，内部排序中效率最高的排序算法。具体它是怎么做的呢？
这里写图片描述
首先他定义了两个头尾指针，分别指向序列的头部和尾部。从high指针位置开始扫描整个序列，如果high指针所指向的元素值大于等于临界值，指针前移。如果high指针所指向的元素的值小于临界值的话：
这里写图片描述
将high指针所指向的较小的值交换给low指针所指向的元素值，然后low指针前移。
这里写图片描述
然后从low指针开始，逐个与临界值进行比较，如果low指向的元素的值小于临界值，那么low指针前移，否则将low指针所指向的当前元素的值交换给high指针所指向的当前元素的值，然后把high指针前移。
这里写图片描述
按照这样的算法，
这里写图片描述
当low和high会和的时候，就代表着本次快速排序结束，临界值的左边和右边都已归类。这样的话，我们再使用递归去快速排序其两边的子表，直到最后，整张表必然是有序的。下面我们看代码实现：
/*快速排序的递归定义*/
public static void FastSort(int[] array,int low,int high){
if(low<high){
int pos = OneFastSort(array,low,high);
FastSort(array,low,pos-1);
FastSort(array,pos+1,high);
}
}
public static int OneFastSort(int[] array,int low,int high){
//实现一次快速排序
int key = array[low];
int flag = 0;
while (low != high) {
if (flag == 0) {
//flag为0表示指针从high的一端开始移动
if (array[high] < key) {
array[low] = array[high];
low++;
flag = 1;
} else {
high--;
}
} else {
//指针从low的一端开始移动
if (array[low] > key) {
array[high] = array[low];
high--;
flag = 0;
} else {
low++;
}
}
}
array[low] = key;
return low;
}
如果上述介绍的快速排序的算法核心思想理解的话，这段代码的实现也就比较容易理解了。
四、选择类排序
选择类排序的基本思想是，每一趟会在n个元素中比较n-1次，选择出最大或者最小的一个元素放在整个序列的端点处。选择类排序有基于树的也有基于线性表的，有关树结构的各种排序算法，我们将在后续文章中进行描述，此处我们实现简单的选择排序算法。
public static void ChooseSort(int[] array){
for (int i=0;i<array.length;i++){
for (int j=i+1;j<array.length;j++){
if(array[i]>array[j]){
//发现比自己小的元素，则交换位置
int temp = array[j];
array[j]=array[i];
array[i] = temp;
}
}
}
//输出排序后的数组内容
for (int key : array){
System.out.print(key+",");
}
}
代码堪比冒泡排序的算法实现，比较简单直接，此处不再赘述。
五、归并类排序算法
这里的归并类排序算法指的就是归并排序。归并排序的核心思想是，对于一个初始的序列不断递归，直到子序列中的元素足够少时，对他们进行直接排序。然后递归返回继续对两个分别有序的序列进行直接排序，最终递归结束的时候，整个序列必然是有序的。
这里写图片描述
对于一个初始序列，我们递归拆分的结果如上图。最小的子序列只有两个元素，我们可以轻易的对他们进行直接的排序。简单的排序结果如下：
这里写图片描述
然后我们递归返回：
这里写图片描述
初看起来和我们的希尔排序的基本思想有点像，希尔排序通过对初始序列的稀疏化，使得每个子序列在内部上都是有序的，最终在对整个序列进行排序的时候，序列的内部基本有序，总体上能提高效率。但是我们的归并排序的和核心思想是，通过不断的递归，直到子序列元素足够少，在内部对他们进行直接的排序操作，当递归返回的时候，对返回的两个子表再次进行归并排序，使得合成的新序列是有序的，一直到递归返回调用结束时候，整个序列就是有序的。
/*归并排序的递归调用*/
public static void MergeSort(int[] array,int low,int high){
if(low == high){
//说明子数组长度为1，无需分解，直接返回即可
}else{
int p = (low+high)/2;
MergeSort(array,low,p);
MergeSort(array,p+1,high);
//完成相邻两个子集合的归并
MergeTwoData(array,low,high);
}
}
/*用于排序两个子序列的归并排序算法实现*/
public static void MergeTwoData(int[] array,int low,int high){
int[] arrCopy = new int[high-low+1];
int i,j;
i = low;j= (low+high)/2+1;
for (int key=0;key<=high-low;key++){
//如果左边子数组长度小于右边数组长度，当左数组全部入库之后，右侧数组不用做比较直接入库
if(i==(low+high)/2+1){
arrCopy[key] = array[j];
j++;
}
//如果右侧数组长度小于左侧数组长度，当右侧数组全部入库之后，左侧数组不用做比较直接入库
else if(j==high+1){
arrCopy[key]=array[i];
i++;
}else if(array[i]<array[j]){
arrCopy[key]=array[i];
i++;
}else{
arrCopy[key] = array[j];
j++;
}
}
j = 0;
//按顺序写回原数组
for(int x=low;x<=high;x++) {
array[x] = arrCopy[j];
j++;
}
}
我们的递归调用方法还是比较简单的，首先从一个序列的中间位置开始递归分成两个子序列并传入该序列的头尾索引，当头尾索引相等的时候，说明序列中只有一个元素，于是无需调用归并排序，直接返回。等待两边的子序列都返回的时候，我们调用归并排序对这两个子序列进行排序，继续向上返回直到递归结束，最终的序列必然是有序的。我们主要看看用于归并两个子序列的排序算法的实现。
假设我们递归返回了这样的两个子序列，因为这些子序列都是递归返回的，所以他们在内部都是有序的，于是我们需要对两个子序列排序和并成新序列并向上递归返回。
这里写图片描述
排序的算法如下：
分别取出两个序列的栈顶元素，进行比较，把小的一方的元素出栈并存入新序列中，值较大的元素依然位于栈顶。这样，当有一方的元素全部出栈之后，另一方的元素顺序填入新序列中即可。具体的算法实现已经在上述代码中给出了。
至此，线性的基本排序算法都已经介绍完成了，有些算法介绍的比较粗糙，待后续深入理解后再回来补充，总结不到之处，望指出！
