摘要：
所谓排序，就是根据排序码的递增或者递减顺序把数据元素依次排列起来，使一组任意排列的元素变为一组按其排序码线性有序的元素。本文将介绍八种最为经典常用的内部排序算法的基本思想与实现，包括插入排序(直接插入排序，希尔排序)、选择排序(直接选择排序，堆排序)、交换排序(冒泡排序，快速排序)、归并排序、分配排序(基数排序)，并给出各种算法的时间复杂度、空间复杂度和稳定性。
友情提示：
若读者需要本博文相关完整代码，请移步我的Github自行获取，项目名为 DataStructure(具体算法实现在cn.tju.edu.rico.sort包)，项目链接地址为：https://github.com/githubofrico/DataStructure。
所谓排序，就是根据排序码的递增或者递减顺序把数据元素依次排列起来，使一组任意排列的元素变为一组按其排序码线性有序的元素。本文将介绍八种最为经典常用的内部排序算法，包括插入排序(直接插入排序，希尔排序)、选择排序(直接选择排序，堆排序)、交换排序(冒泡排序，快速排序)、归并排序、分配排序(基数排序)。实际上，无论是基本排序方法(直接插入排序，直接选择排序，冒泡排序)，还是高效排序方法(快速排序，堆排序，归并排序)等，它们各有所长，都拥有特定的使用场景。因此，在实际应用中，我们必须根据实际任务的特点和各种排序算法的特性来做出最合适的选择。一般地，我们衡量一个算法的指标包括：
·时间复杂度 (在排序过程中需要比较和交换的次数)
·空间复杂度 (在排序过程中需要的辅助存储空间)
·稳定性 (该算法的实现是否可以保证排序后相等元素的初始顺序，只要该算法存在一种实现可以保证这种特征，那么该算法就是稳定的)
·内部排序/外部排序 (在排序过程中数据元素是否完全在内存)
笔者将在本文着重探讨上述八种排序算法的思想和实现，并就各算法根据以上指标进行分析和归类，以便进一步熟悉它们各自的应用场景。
插入排序的基本思想：每步将一个待排序元素，按其排序码大小插入到前面已经排好序的一组元素中，直到元素全部插入为止。在这里，我们介绍三种具体的插入排序算法：直接插入排序，希尔排序与折半插入排序。
1、直接插入排序
直接插入排序的思想：当插入第i(i>=1)个元素时，前面的V[0],…,V[i-1]等i-1个 元素已经有序。这时，将第i个元素与前i-1个元素V[i-1]，…，V[0]依次比较，找到插入位置即将V[i]插入，同时原来位置上的元素向后顺移。在这里，插入位置的查找是顺序查找。直接插入排序是一种稳定的排序算法，其实现如下：
/**
*Title: 插入排序中的直接插入排序，依赖于初始序列
*Description: 在有序序列中不断插入新的记录以达到扩大有序区到整个数组的目的
* 时间复杂度：最好情形O(n)，平均情形O(n^2)，最差情形O(n^2)
* 空间复杂度：O(1)
* 稳 定 性：稳定
* 内部排序(在排序过程中数据元素完全在内存)
* @author rico
* @created 2017年5月20日 上午10:40:00
*/
public class StraightInsertionSort {
public static int[] insertSort(int[] target){
if(target != null && target.length != 1){ // 待排序数组不为空且长度大于1
for (int i = 1; i < target.length; i++) { // 不断扩大有序序列，直到扩展到整个数组
for (int j = i; j > 0; j--) { // 向有序序列中插入新的元素
if(target[j] <target[j-1]){ // 交换
int temp = target[j];
target[j] = target[j-1];
target[j-1] = temp;
}
}
}
}
return target;
}
}
2、希尔排序
希尔排序的思想：设待排序序列共n个元素，首先取一个整数gap<n作为间隔，将全部元素分为间隔为gap的gap个子序列并对每一个子序列进行直接插入排序。然后，缩小间隔gap，重复上述操作，直至gap缩小为1，此时所有元素位于同一个序列且有序。由于刚开始时，gap较大，每个子序列元素较少，排序速度较快；待到排序后期，gap变小，每个子序列元素较多，但大部分元素基本有序，所以排序速度仍较快。一般地，gap取 （gap/3 + 1）。希尔排序是一种不稳定的排序方法，其实现如下：
/**
*Title: 插入排序中的希尔排序，依赖于初始序列
*Description: 分别对间隔为gap的gap个子序列进行直接插入排序，不断缩小gap,直至为 1
*
* 刚开始时，gap较大，每个子序列元素较少，排序速度较快；
* 待到排序后期，gap变小，每个子序列元素较多，但大部分元素基本有序，所以排序速度仍较快。
*
* 时间复杂度：O(n) ~ O(n^2)
* 空间复杂度：O(1)
* 稳 定 性：不稳定
* 内部排序(在排序过程中数据元素完全在内存)
*@author rico
*@created 2017年5月20日 上午10:40:00
*/
public class ShellSort {
public static int[] shellSort(int[] target){
if(target != null && target.length != 1){
int gap = target.length; // gap个大小为gap的子序列
do{
gap= gap/3 + 1; // 不断缩小gap直至为1
for (int i = 0 + gap; i < target.length; i++) { // 对每个子序列进行直接插入排序
if(target[i] < target[i-gap]){
int j = i - gap;
int temp = target[i]; // 待插入值
do{
target[j + gap] =target[j]; // 后移元素
j = j - gap; // 再比较前一个元素
}while(j >= 0 && target[j] > temp); // 向前比较的终止条件
target[j + gap] = temp; // 将待插入值插入合适的位置
}
}
}while(gap > 1);
}
return target;
}
}
3、折半插入排序
折半插入排序的思想：当插入第i(i>=1)个元素时，前面的V[0],…,V[i-1]等i-1个 元素已经有序。这时，折半搜索第i个元素在前i-1个元素V[i-1]，…，V[0]中的插入位置，然后直接将V[i]插入，同时原来位置上的元素向后顺移。与直接插入排序不同的是，折半插入排序比直接插入排序明显减少了关键字之间的比较次数，但是移动次数是没有改变。所以，折半插入排序和插入排序的时间复杂度相同都是O（N^2），但其减少了比较次数，所以该算法仍然比直接插入排序好。折半插入排序是一种稳定的排序算法，其实现如下：
/**
*Title: 插入排序中的折半插入排序，依赖于初始序列
*Description: 折半搜索出插入位置，并直接插入;与直接插入搜索的区别是，后者的搜索要快于顺序搜索
* 时间复杂度：折半插入排序比直接插入排序明显减少了关键字之间的比较次数，但是移动次数是没有改变。所以，
* 折半插入排序和插入排序的时间复杂度相同都是O（N^2），在减少了比较次数方面它确实相当优秀，所以该算法仍然比直接插入排序好。
* 空间复杂度：O(1)
* 稳 定 性：稳定
* 内部排序(在排序过程中数据元素完全在内存)
*@author rico
*@created 2017年5月25日 下午12:03:23
*/
public class BinaryInsertSort {
public static int[] binaryInsertSort(int[] target) {
if (target != null && target.length > 1) {
for (int i = 1; i < target.length; i++) {
intleft = 0;
int right = i - 1;
intmid;
inttemp = target[i];
if(temp < target[right]){ // 当前值小于有序序列的最大值时，开始查找插入位置
while(left <= right){
mid = (left + right)/2;
if(target[mid] < temp){
left = mid + 1; // 缩小插入区间
}else if(target[mid] > temp){
right = mid - 1; // 缩小插入区间
}else{ // 待插入值与有序序列中的target[mid]相等，保证稳定性的处理
left = left + 1;
}
}
// left及其后面的数据顺序向后移动，并在left位置插入
for (int j = i; j > left; j--) {
target[j] = target[j-1];
}
target[left] = temp;
}
}
}
return target;
}
}
三. 选择排序
选择排序的基本思想：每一趟 (例如第i趟，i = 0,1,…)在后面第n-i个待排序元素中选出最小元素作为有序序列的第i个元素，直到第n-1趟结束后，所有元素有序。在这里，我们介绍两种具体的选择排序算法：直接选择排序与堆排序。
1、直接选择排序
直接选择排序的思想：第一次从R[0]~R[n-1]中选取最小值，与R[0]交换，第二次从R1~R[n-1]中选取最小值，与R1交换，….，第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换，…..，第n-1次从R[n-2]~R[n-1]中选取最小值，与R[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。直接选择排序是一种不稳定的排序算法，其实现如下：
/**
*Title: 选择排序中的直接选择排序，依赖于初始序列
*Description: 每一趟 (例如第i趟，i = 0,1,...)在后面第n-i个待排序元素中选出最小元素作为有序序列的第i个元素
* 时间复杂度：最好情形O(n^2)，平均情形O(n^2)，最差情形O(n^2)
* 空间复杂度：O(1)
* 稳 定 性：不稳定
* 内部排序(在排序过程中数据元素完全在内存)
* @author rico
* @created 2017年5月20日 上午10:40:00
*/
public class StraightSelectSort {
public static int[] selectSort(int[] target){
if(target != null && target.length != 1){
for (int i = 0; i < target.length; i++) {
int min_index = i;
for (int j = i + 1; j < target.length; j++) {
if(target[min_index] > target[j]){
min_index = j;
}
}
if(target[min_index] != target[i]){ // 导致不稳定的因素：交换
int min = target[min_index];
target[min_index] = target[i];
target[i] = min;
}
}
}
return target;
}
}
2、堆排序
堆排序的核心是堆调整算法。首先根据初始输入数据，利用堆调整算法shiftDown()形成初始堆；然后，将堆顶元素与堆尾元素交换，缩小堆的范围并重新调整为堆，如此往复。堆排序是一种不稳定的排序算法，其实现如下：
/**
*Title: 堆排序(选择排序)，升序排序(最大堆)，依赖于初始序列
*Description: 现将给定序列调整为最大堆，然后每次将堆顶元素与堆尾元素交换并缩小堆的范围，直到将堆缩小至1
* 时间复杂度：O(nlgn)
* 空间复杂度：O(1)
* 稳 定 性：不稳定
* 内部排序(在排序过程中数据元素完全在内存)
* @author rico
* @created 2017年5月25日 上午9:48:06
*/
public class HeapSort {
public static int[] heapSort(int[] target) {
if (target != null && target.length > 1) {
// 调整为最大堆
int pos = (target.length - 2) / 2;
while (pos >= 0) {
shiftDown(target, pos, target.length - 1);
pos--;
}
// 堆排序
for (int i = target.length-1; i > 0; i--) {
int temp = target[i];
target[i] = target[0];
target[0] = temp;
shiftDown(target, 0, i-1);
}
return target;
}
return target;
}
/**
* @description 自上而下调整为最大堆
* @author rico
* @created 2017年5月25日 上午9:45:40
* @param target
* @param start
* @param end
*/
private static void shiftDown(int[] target, int start, intend) {
int i = start;
int j = 2 * start + 1;
int temp = target[i];
while (j <= end) { // 迭代条件
if (j < end && target[j + 1] >target[j]) { //找出较大子女
j =j + 1;
}
if (target[j] <= temp) { // 父亲大于子女
break;
} else {
target[i]= target[j];
i =j;
j =2 * j + 1;
}
}
target[i] =temp;
}
}
四. 交换排序
交换排序的基本思想：根据序列中两个元素的比较结果来对换这两个记录在序列中的位置，也就是说，将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
1、冒泡排序
冒泡排序的思想：根据序列中两个元素的比较结果来对换这两个记录在序列中的位置，将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。因此，每一趟都将较小的元素移到前面，较大的元素自然就逐渐沉到最后面了，也就是说，最大的元素最后才能确定，这就是冒泡。冒泡排序是一种稳定的排序算法，其实现如下：
/**
*Title: 交换排序中的冒泡排序 ，一般情形下指的是优化后的冒泡排序，最多进行n-1次比较，依赖于初始序列
*Description:因为越大的元素会经由交换慢慢"浮"到数列的顶端(最后位置)，最大的数最后才确定下来，所以称为冒泡排序
* 时间复杂度：最好情形O(n)，平均情形O(n^2)，最差情形O(n^2)
* 空间复杂度：O(1)
* 稳 定 性：稳定
* 内部排序(在排序过程中数据元素完全在内存)
*
* @author rico
* @created 2017年5月20日 上午10:40:00
*/
public class BubbleSort {
/**
* @description 朴素冒泡排序(共进行n-1次比较)
* @author rico
*/
public static int[] bubbleSort(int[] target) {
int n = target.length;
if (target != null && n != 1) {
// 最多需要进行n-1躺，每一趟将比较小的元素移到前面，比较大的元素自然就逐渐沉到最后面了，这就是冒泡
for (int i = 0; i < n-1; i++){
for (int j = n-1; j > i; j--) {
if(target[j] < target[j-1]){
int temp = target[j];
target[j] = target[j-1];
target[j-1] = temp;
}
}
System.out.println(Arrays.toString(target));
}
}
return target;
}
/**
* @description 优化冒泡排序
* @author rico
*/
public static int[] optimizeBubbleSort(int[] target) {
int n = target.length;
if (target != null && n != 1) {
// 最多需要进行n-1躺，每一趟将比较小的元素移到前面，比较大的元素自然就逐渐沉到最后面了，这就是冒泡
for (int i = 0; i < n-1; i++){
boolean exchange = false;
for (int j = n-1; j > i; j--) {
if(target[j] < target[j-1]){
int temp = target[j];
target[j] = target[j-1];
target[j-1] = temp;
exchange = true;
}
}
System.out.println(Arrays.toString(target));
if (!exchange){ // 若 i 到 n-1 这部分元素已经有序，则直接返回
return target;
}
}
}
return target;
}
}
2、快速排序
快速排序的思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小(划分过程)，然后再按此方法对这两部分数据分别进行快速排序(快速排序过程)，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序是一种不稳定的排序算法。
/**
*Title: 交换排序中的快速排序，目前应用最为广泛的排序算法，是一个递归算法，依赖于初始序列
*Description:快速排序包括两个过程：划分 和 快排
*"划分"是指将原序列按基准元素划分两个子序列
*"快排"是指分别对子序列进行快排
*
* 就平均计算时间而言，快速排序是所有内部排序方法中最好的一个
*
* 对大规模数据排序时，快排是快的；对小规模数据排序时，快排是慢的，甚至慢于简单选择排序等简单排序方法
*
* 快速排序依赖于原始序列，因此其时间复杂度从O(nlgn)到O(n^2)不等
* 时间复杂度：最好情形O(nlgn)，平均情形O(nlgn)，最差情形O(n^2)
*
* 递归所消耗的栈空间
* 空间复杂度：O(lgn)
*
* 可选任一元素作为基准元素
* 稳 定 性：不稳定
*
*
* 内部排序(在排序过程中数据元素完全在内存)
*
* @author rico
* @created 2017年5月20日 上午10:40:00
*/
public class QuickSort {
/**
* @description 快排算法(递归算法)：在递去过程中就把问题解决了
* @author rico
* @created 2017年5月20日 下午5:12:06
* @param target
* @param left
* @param right
* @return
*/
public static int[] quickSort(int[] target, int left, int right) {
if(right > left){ // 递归终止条件
int base_index = partition(target,left, right); // 原序列划分后基准元素的位置
quickSort(target, left, base_index-1); // 对第一个子序列快速排序，不包含基准元素！
quickSort(target, base_index+1, right); // 对第二个子序列快速排序，不包含基准元素！
return target;
}
return target;
}
/**
* @description 序列划分，以第一个元素为基准元素
* @author rico
* @created 2017年5月20日 下午5:10:54
* @param target 序列
* @param left 序列左端
* @param right 序列右端
* @return
*/
public static int partition(int[] target, int left, intright){
int base = target[left]; // 基准元素的值
int base_index = left; // 基准元素最终应该在的位置
for (int i = left+1; i <= right; i++) { // 从基准元素的下一个元素开始
if(target[i] < base){ // 若其小于基准元素
base_index++; // 若其小于基准元素,则基准元素最终位置后移；否则不用移动
if(base_index != i){ // 相等情况意味着i之前的元素都小于base,只需要换一次即可，不需要次次都换
int temp = target[base_index];
target[base_index] = target[i];
target[i] = temp;
}
}
}
// 将基准元素就位
target[left] = target[base_index];
target[base_index] = base;
System.out.println(Arrays.toString(target));
return base_index; //返回划分后基准元素的位置
}
}
联系客服
