数据结构：排序

简介

内部排序：是指在排序期间元素全部存放在内存中的排序

外部排序：是指在排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求不断地在内、外存之间移动的排序

插入排序

插入排序是一种简单直观的排序方法，其基本思想在于每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中，直到全部记录插入完成。

直接插入排序

直接插入排序基本思想是每一步将一个待排序的记录，从右到左依次比较插入到前面已经排好序的有序序列中去，直到插完所有元素为止。

直接插入排序算法的性能分析如下：

• 空间效率：仅使用了常数个辅助单元，因而空间复杂度为O(1)
• 时间效率：在排序过程中，向有序子表中逐个地插入元素的操作进行了n-1趟，每趟操作都分为比较关键字和移动操作，而比较次数和移动次数取决于待排序表的初始状态。

在最好的情况下，表中元素已经有序，此时每插入一个元素，都只需比较一次而不用移动元素，因而时间复杂度为O(n)。

平均情况下考虑待排元素是随机的，此时可以取上述最好与最坏情况下的平均值作为平均情况下的时间复杂度，总的比较次数和总的移动次数均为n²/4。由此，直接插入排序算法的最坏和平均的时间复杂度为O(n²)

• 稳定性：由于每次插入元素时总是从后往前先比较再移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序算法。
• 适用性：直接插入排序算法适用于顺序存储和链式存储的线性表。

public class InsertSort {
    public void insertSort(int[] array, int first, int last) {
        int temp, i, j;
        for (i = first + 1; i <= last - 1; i++) {// 默认以第一个数为有序序列，后面的数为要插入的数。
            temp = array[i];
            j = i - 1;
            while (j >= first && array[j] > temp) {// 从后进行搜索如果搜索到的数小于temp则该数后移继续搜索，直到搜索到小于或等于temp的数即可
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = temp;
            // 打印每次排序结果
            for (int m = 0; m <= array.length - 1; m++) {
                System.out.print(array[m] + "\t");
            }
            System.out.println();
        }
    }
  
    public static void main(String[] args) {
        InsertSort insertSort = new InsertSort();
        int[] array = { 5, 69, 12, 3, 56, 789, 2, 5648, 23 };
        insertSort.insertSort(array, 0, array.length);// 注意此处是0-9而不是0-8
        for (int i = 0; i <= array.length - 1; i++) {
            System.out.print(array[i] + "\t");
        }
    }
}

public void insertSort(int[] arr) {
		//一开始只能保证第一个元素是已有序的序列。所以从第二个元素开始，逐个插入到已有序序列
	for(int i=1;i<arr.length;i++) {
		int j=i;
		while(j>0 && arr[j]<arr[j-1]) {   //这种情况就说明顺序开始出现问题，需要通过交换位置来调整
			swap(arr,j-1,j);  
			j--;//一旦需要调整位置，j每次都要变化，和前面的已有序元素都要进行比较，保证当前遍历的元素在正确的位置
		}
	}
}

注意：大部分排序算法都仅适用于顺序存储的线性表

折半插入排序

折半插入排序仅仅是减少了比较元素的次数，该比较的次数与待排序的初始状态无关，仅取决于表中的元素个数n，而元素的移动次数没有改变，它依赖于待排序表的初始状态。

折半排序的性能分析：

• 空间效率：仅使用了常数个辅助单元，因而空间复杂度为O(1)
• 时间效率：折半插入排序的时间复杂度为O(n²)
• 稳定性：折半插入排序是一个稳定的排序算法

希尔排序

希尔排序又称“缩小增量排序”，该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某 个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插 入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。

希尔排序是插入排序的改进版。主要改进思路是减少插入排序中数据的移动次数，设置步长，在初始数组较大时取较大步长，通常初始步长为待排数组长度1/2，此时只有两个元素比较，交换一次，此时数组为部分有序数组；之后步长依次减半直至步长为1，即为插入排序，此时数组已接近有序，所以插入元素时数据移动次数会相对较少，效率得到提高。

原始数组，元素颜色相同的为一组：

初始增量gap = length / 2 = 5，也就是说整个数组分成5组:[8, 3] [9, 5] [1, 4] [7, 6] [2, 0]

对这5组进行插入排序，结果如下，之后缩小增量gap = 5 / 2 = 2，数组分成了2组：[3, 1, 0, 9, 7] [5, 6, 8, 4, 2]

再对上面两个数组进行插入排序，结果如下，再次缩小增量gap = 2 / 2 = 1，整个数组只有一组数据了[0, 2, 1, 4, 3, 5, 7, 6, 9, 8]

之后只需对这个数组进行微调，无需进行大量的移动操作，即可完成整个数组的排序

希尔排序算法性能分析：

• 空间效率：仅适用了常数个辅助单元，因而空间复杂度为O(1)
• 时间效率：最坏情况下希尔排序的时间复杂度O(n²)
• 稳定性：当相同关键字的记录被划分到不同的子表中时，可能会改变他们之间的相对次序，因此，希尔排序算法是一个不稳定的排序算法。例如：表L={3，2，2}，经过一趟排序后，L={2，2，3}，最终排序也是L={2，2，3}，显然，2与2的相对次序已经发生了变化。
• 适用性：希尔排序算法仅适用当线性表为顺序存储的情况

void shellsort(int a[], int n) {   
   int gap = n / 2;  
   int i, j;  
   int tmp;  
   for(gap = n / 2; gap > 0; gap /= 2)  {   //增量起始值为n/2,之后逐次减半  
      //从第gap个元素，逐个对其所在组进行直接插入排序操作
      for(i = gap; i < n; i++)  {
          tmp=a[i];  
          j = i;
          if(a[j] < a[j - gap]) {
             while(j - gap >= 0 && tmp < a[j - gap]) {
                 //移动法
                 a[j] = a[j - gap];
                 j = j - gap;
             }
             a[j] = temp;
          }
       }  
    }
}

交换排序

所谓交换，就是根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。

冒泡排序

每趟冒泡的结果把序列中的最小元素放到序列的最终位置

public void bubbleSort(int[] arr) {
// 冒泡趟数--首先确定最大的元素放到了最后一个位置.一共要确定arr.length-1个元素的位置，所以一共冒泡了arr.length-1趟
	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])  { //j和j+1比较，所以j最多只能到倒数第二个元素，即j<arr.length-1
				swap(arr,j,j+1);
			}
		}
	}
}

//交换数组中两个位置上的元素
public void swap(int[] arr,int i,int j) {
	int temp=arr[i];
	arr[i]=arr[j];
	arr[j]=temp;
}

冒泡排序的性能分析：

• 空间效率：仅使用了常数个辅助单元，因而空间复杂度为O(1)
• 时间效率：当初始序列有序时，显然第一趟冒泡后flag依然为false（本趟冒泡没有元素交换），从而直接跳出循环，比较次数为n-1，移动次数为0，从而最好情况下的时间复杂度为O(n)；当初始序列为逆序时，需要进行n-1趟排序，第i趟排序要进行n-i词关键字的比较，而且每次比较都必须移动元素3次来交换元素位置。这种情况下比较次数=n(n-1)/2，移动次数=3n(n-1)/2。从而最坏情况下时间复杂度为O(n²)，其平均时间复杂度也为O(n²)。
• 稳定性：由于当i>j且A[i].key=A[j].key时，不会交换两个元素，从而冒泡排序是一个稳定的排序算法。

冒泡排序中所产生的的有序子序列一定是全局有序的（不同于直接插入排序），也就是说有序子序列中的所有元素的关键字一定小于或大于无序子序列中所有元素关键字，这样每一趟排序都会将一个元素放置到其最终的位置上。

快速排序

快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然 后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序算法的性能分析：

• 空间效率：由于快速排序是递归的，需要借助一个递归工作栈来保存每一层递归调用的必要信息，其容量应与递归调用的最大深度一致。最好情况下为og₂(n+1)向上取整；最坏情况下，因为要进行n-1次递归调用，所以栈的深度为O(n)；平均情况下，栈的深度为O(log₂n)。因而空间复杂度在最坏情况下为O(n)，平均情况下为O(log₂n)
• 时间效率：快速排序的运行时间与划分是否对称有关，而后者又与具体使用的划分算法有关。
  • 快速排序的最坏情况发生在两个区域分别包含n-1个元素和0个元素时，这种最大程度的不对称性若发生在每一层的递归上，即对应于初始排序表基本有序或基本逆序时，就得到最坏情况下的时间复杂度O(n²)
  • 最好的情况是枢纽元选取得当，每次都能均匀的划分序列。 时间复杂度O(nlog₂n)
• 稳定性：在划分算法中，若右端区间存在两个关键字相同，且均小于基准值记录，则在交换到左端区间后，它们的相对位置会发生变化，即快速排序是一个不稳定的排序算法。例如，表L={3, 2, 2}，经过一趟排序之后，L={2, 2, 3}，最终排序序列也是L={2, 2, 3}，显然，2与2的相对次序已经发生了变化

快速排序是所有内部排序算法中平均性能最优的排序算法

选择排序

选择排序的基本思想是：每一趟（例如第i趟）在后边n-i+1个待排序元素中选取关键字最小的元素，作为有序子序列的第i个元素，直到n-1趟做完，待排序元素只剩下1个，就不用再选了。

简单选择排序

简单选择排序的思想是：假设排序表为L[1 ....... n]，第i趟排序即从L[i .... n]中选择关键字最小的元素与L(i)交换，每一趟排序可以确定一个元素的最终位置，这样经过n-1趟排序就可以使得整个排序表有序。

简单选择排序的性能分析：

• 空间效率：仅适用常数个辅助单元，故空间复杂度为O(1)
• 时间效率：简单选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有N个元素，则比较次数总是N (N - 1) / 2。而移动次数与序列的初始排序有关。当序列正序时，移动次数最少，为0当序列反序时，移动次数最多，为3N (N - 1) /  2。所以，综合以上，简单排序的时间复杂度为O(n²)
• 稳定性：在第i趟找到最小元素后，和第i个元素交换，可能会导致第i个元素与其含有相同关键字元素的相对位置发生变化。例如，表L={2, 2, 1}，经过一趟排序后，L={1, 2, 2}，最终排序序列也是L={1, 2, 2}，显然2月2的相对位置已经发生了变化。因此简单选择排序是一个不稳定的排序方法

堆排序

堆排序是一种树形选择排序方法，它的特点是：在排序过程中，将L[1 ..... n]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内阻关系，在当前无序区中选择关键字最大（或最小）的元素。

堆的定义如下：n个关键字序列L[1 ..... n]称为堆，当且仅当该序列满足：

• 大根堆：L(i)≥L(2i) 且 L(i)≥L(2i+1)
• 小根堆：L(i)≤L(2i) 且 L(i)≤L(2i+1)

向下调整的时间与树的高度有关，为O(h)。建堆过程中每次向下调整时，大部分结点的高度都较小。因此，可以证明在元素个数为n的序列上建堆，其时间复杂度为O(n)，这说明可以在一个线性时间内，将一个无序数据建成一个大顶堆。

应用堆这种数据结构进行排序的思路很简单，首先将存放在L[1......n]中的n个元素建成初始堆，由于堆本身的特点（以大顶堆为例），堆顶元素就是最大值。输出堆顶元素后，通常将堆低元素送入堆顶，此时根结点以不满足大顶堆的性质，堆被破坏，将堆顶元素向下调整使其继续保持大顶堆的性质，再输出堆顶的元素，如此重复，直到堆中剩下一个元素为止。

同时堆也支持删除和插入操作，由于堆顶元素或为最大值或为最小值，删除堆顶元素时，先将堆的最后一个元素与堆顶元素交换，由于此时堆的性质被破坏，需对此时的根结点进行向下调整操作。对堆进行插入操作时，先将新结点放在堆的末端，再对这个新结点执行向上调整操作。

堆算法的性能分析：

• 空间效率：仅适用常数个辅助单元，所以空间复杂度为O(1)
• 时间效率：建堆时间为O(n)，之后有n-1次向下调整操作，每次调整的时间复杂度为O(h)，故在性能最好、最坏和平均的情况下，堆排序的时间复杂度为O(nlog₂n)
• 稳定性：在进行筛选时，有可能把后边相同关键字的元素调整到前面，所以堆排序是一个不稳定的排序算法。例如，表L={1，2，2}，构造初始堆时，可能将2交换到堆顶，此时L={2，1，2}，最终排序序列为L={1，2，2}，显然，2与2的相对次序已经发生了变化

归并排序

“归并”的含义是将两个或者两个以上的有序表组成一个新的有序表。

2-路归并排序

2-路归并排序算法性能分析：

• 空间效率：辅助空间刚好要占用n个单元，所以归并排序的空间复杂度为O(n)
• 时间效率：每一趟归并的时间复杂度为O(n)。共需进行⌈log₂n⌉趟归并，所以算法时间复杂度为O(nlog₂n)
• 稳定性：由于Merge()操作不会改变相同关键字的相对次序，所以2-路归并排序算法是一个稳定的排序算法

注意：一般而言，对于N个元素进行k-路归并排序时，排序的趟数m满足k^m=N，从而m=logk^N，又考虑到m为整数，所以m=⌈logk^N⌉。这个和前面的2-路归并是一致的。

基数排序

基数排序是一种很特别的排序算法，它不是基于比较进行排序的，而是采用多关键字排序思想，借助“分配”和“收集”两种操作对单逻辑关键字进行排序。基数排序又分为最高位优先（MSD）排序和最低位优先（LSD）排序。

如下为基数排序作用于一个由7个3位数组成的表的过程。最左端为输入端，其余各列表示了对各个不断递增的有效位连续排序后的情况，阴影表示当前正被排序的数位。

基数排序算法的性能分析：

• 空间效率：一趟排序需要辅助存储空间为r（r个队列），但以后的排序中重复使用这些队列，所以基数排序的空间复杂度为O(r)
• 时间效率：基数排序需要进行d趟分配和收集，一趟分配需要O(n)，一趟收集需要O(r)，所以基数排序的时间复杂度为O(d*(n+r))，它与序列的初始状态无关
• 稳定性：对于基数排序而言，很重要的一点就是按位排序时必须是稳定的。因此，这也保证了基数排序保持稳定性

d 为位数，r 为基数，n 为原数组个数