文章目录

• 参考资料
• 0. 基本概念
• • 10大经典排序算法比较
• 1. 插入排序
• • 1.1 直接插入排序
  • • 1.1.1 基本思想
    • 1.1.2 直接插入排序效率分析
  • 1.2 希尔排序（缩小增量排序）
  • • 1.2.1 基本思想
    • 1.2.2 希尔排序的效率分析
• 2. 交换排序
• • 2.1 冒泡排序(Bubble Sort)
  • • 2.1.1 基本思想
    • 2.1.2 冒泡排序的效率分析
  • 2.2 快速排序(Quick Sort)
  • • 2.2.1 排序思想
    • 2.2.2 快速排序的递归树
    • 2.2.3 快速排序的时间复杂度
    • 2.2.4 快速排序的空间复杂度及稳定性
• 3. 选择排序
• • 3.1 简单选择排序
  • • 3.1.1 基本过程
    • 3.1.2 简单选择排序的效率分析
  • 3.2 堆排序
  • • 3.2.1 堆的定义
    • 3.2.2 堆排序的基本思想
• 4. 二路归并排序
• • 4.1 基本思想
  • 4.2 效率分析
• 5. 基数排序

参考资料

1. 十大经典排序算法动画与解析，看我就够了！（配代码完全版）
2. https://www.bilibili.com/video/BV1Kb411W75N
3. 归并排序
4. 图解排序算法(四)之归并排序

0. 基本概念

1. 排序:是计算机程序设计中的一项重要操作,其功能是指一个数据元素集合或序列重新排列成一个按数据元素某个数据项值有序的序列。
2. 排序码(关键码):排序依据的数据项。
3. 稳定排序:排序前与排序后相同关键码元素间的位置关系,保持一致的排序方法。
4. 不稳定排序:排序前与排序后相同关键码元素间的相对位置发生改变的排序方法
5. 排序分为两类:
   1. 内排序:指待排序列完全存放在内存中所进行的排序。内排序大致可分为五类:插入排序、交换排序、选择排序、归并排序和分配排序。
   2. 外排序:指排序过程中还需访问外存储器的排序。

10大经典排序算法比较

1. 插入排序

• 基本思想
  每次将一个待排序的元素,按其关键字的大小插入到前面已经排好序的子文件的适当位置,直到全部记录插入完成为止。

1.1 直接插入排序

1.1.1 基本思想

把n个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只包含1个元素,无序表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,把它的排序码依次与有序表元素的排序码进行比较,将它插入到有序表中的适当位置,使之成为新的有序表。

• 例如, n=6,数组R的六个排序码分别为:[ 17, 3, 25, 14, 20, 9], 它的直接插入排序的执行过程如下:
  

package pers.chh3213.sort;

import java.util.Arrays;

/**
* DirectInsertSort.java
* @Description 直接插入法
* @author chh3213
* @version
* @date 2021年12月26日上午11:19:07
 */
public class DirectInsertSort {
	public static void main(String[] args) {
		DirectInsertSort insertSort = new DirectInsertSort();
		int[] arr = {9, -16, 310, 23, -30, -49, 25, 21, 30};
		insertSort.directInsertSort(arr);
		System.out.println(Arrays.toString(arr));
	}
	public void directInsertSort(int[] arr) {
		// 法一
		for (int i = 1; i < arr.length; i++) {
				int temp = arr[i];           // 记录要插入的数据
				int j=i;
				for ( ; j>0&&arr[j-1]>temp; j--) {// 从已经排序的序列最右边的开始比较，找到比其小的数
					arr[j]=arr[j-1];
				}
				if(j!=i)arr[j]=temp;	
		}
		//法二
//		for (int i = 1; i < arr.length; i++) {
//			for(int j=i;j>0;j--) {
//				if(arr[j]<arr[j-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;
	}


}

1.1.2 直接插入排序效率分析

• 首先从空间来看,它只需要一个元素的辅助空间用于元素的位置交换。从时间分析,首先外层循环要进行n-1次插入,每次插入最少比较一次(正序),移动0次;最多比较i次(包括同temp的比较),移动i+1次(逆序)(i=2,3,…,n)。因此,直接插入排序的时间复杂度为 O ( n 2 ) O(n^2) O(n2) 。
• 直接插入排序的元素移动是顺序的，该方法是稳定的。

1.2 希尔排序（缩小增量排序）

1.2.1 基本思想

先将整个待排元素序列分割成若干个子序列(由相隔某个增量的元素组成的)分别进行直接插入排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下(接近最好情况) ,效率是很高的,因此希尔排序在时间效率上有较大提高。

• 例如，8个元素的关键码分别为：91，67，35，62，29，72，46，57，希尔排序算法的执行过程为：

d1=8/2=4;
d2=4/2=2;
d3=2/2=1;

• 步骤

  1. 选择一个增量序列t1，t2，……，tk，其中ti > tj, tk = 1；

  2. 按增量序列个数 k，对序列进行 k 趟直接插入排序；

  3. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

package pers.chh3213.sort;

import java.util.Arrays;

public class ShellSort {
	public static void main(String[] args) {
		ShellSort shell = new ShellSort();
		int[] arr = {9, -16, 310, 23, -30, -49, 25, 21, 30};
		shell.shellSort(arr);
		System.out.println(Arrays.toString(arr));
	}
	public void shellSort(int[] arr) {
		//第一次步长为数组长度/2，后面依次步长/2
		for (int step = arr.length /2; step >0; step /= 2) {
			//直接插入排序
			for (int i = step; i < arr.length; i++) {
				int temp = arr[i];//右侧待排序区第一个数
				int j=i-step;//左侧已排序区域第一个数索引
				for( ;j>=0&&arr[j]>temp;j-=step) {
					arr[j+step]=arr[j];//满足条件则把已排序数字往后挪一个位置
//					swap(arr, j, j+step);
				}
				//插入待排序数字到指定位置
				arr[j+step]=temp;
			}


		}
	}
	public void swap(int[] arr, int i, int j) {
		int temp =arr[i];
		arr[i]=arr[j];
		arr[j]=temp;
	}
}

1.2.2 希尔排序的效率分析

• 虽然我们给出的算法是三层循环,最外层循环为 l o g 2 ( n ) log_2(n) log2​(n)数量级,中间的for循环是n数量级的,内循环远远低于n数量级,因为当分组较多时,组内元素少此循环次数少;当分组较少时,组内元素增多,但已接近有序,循环次数并不增加。因此,希尔排序的时间复杂性在 O ( n l o g 2 n ) O(nlog_2n) O(nlog2​n)和 O ( n 2 ) O(n^2) O(n2)之间,大致为 O ( n 1.3 ) O(n^{1.3}) O(n1.3) 。
• 由于希尔排序对每个子序列单独比较,在比较时
  进行元素移动,有可能改变相同排序码元素的原始顺
  序,因此希尔排序是不稳定的。

2. 交换排序

• 主要是通过排序表中两个记录关键码的比较，弱于排序要求相逆（不符合升序或降序），则将两者交换。

2.1 冒泡排序(Bubble Sort)

2.1.1 基本思想

冒泡排序通过重复地走访要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。

• 原理描述
  通过对待排序序列从前向后，依次比较相邻元素的排序码，若发现逆序则交换，使排序码较大的元素逐渐从前部移向后部。

• 实现步骤（默认升序的情况）

  1. 比较相邻的元素，如果前一个比后一个大，就交换这两个数；
  2. 针对所有元素重复以上的步骤，最后一个除外，直到没有任何一对数字需要交换位置为止。

• 示例

package pers.chh3213.sort;
import java.util.Iterator;
import java.util.Scanner;
public class BubbleSort {
	public static void main(String[] args) {
		int[] arr = {5,4,1,966,2,3,56,89,12,0,56562};
		System.out.println("before sort:");
		for (int i : arr) {
			System.out.print(i+"\t");
		}
		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 temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
				}
			}
		}
		System.out.println();
		System.out.println("after sort:");
		for (int i : arr) {
			System.out.print(i+"\t");
		}
	}
}

因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序， 因此可以在排序过程中设置一个标志swap判断元素是否进行过交换，从而减少不必要的比较。改进代码如下：

	public void bubbleSort(int[] data) {
		for (int i = 0; i < data.length-1; i++) {
			boolean swap = false;
			for (int j = 0; j < data.length-i-1; j++) {
				if(data[j]>data[j+1]) {
					int temp = data[j];
					data[j]= data[j+1];
					data[j+1] = temp;
					swap = true;
				}
			}
			if(!swap)break; //不交换时停止排序
		}
	}

2.1.2 冒泡排序的效率分析

• 从冒泡排序的算法可以看出,若待排序的元素为正序,则只需进行一趟排序,比较次数为(n-1)次，移动元素次数为0;若待排序的元素为逆序,则需进行n-1趟排序,比较次数为 ( n 2 − n ) / 2 (n^2-n)/2 (n2−n)/2,移动次数为 3 ( n 2 − n ) / 2 3(n^2-n )/2 3(n2−n)/2,因此冒泡排序算法的时间复杂度为 O ( n 2 ) O(n^2) O(n2) 。由于其中的元素移动较多,所以属于内排序中速度较慢的一种。因为冒泡排序算法只进行元素间的顺序移动,所以是一个稳定的算法。

2.2 快速排序(Quick Sort)

• 由图灵奖获得者Tony Hoare发明，被列为20世纪十大算法之一，是迄今为止所有内排序算法中速度最快的一种。冒泡排序的升级版，交换排序的一种。快速排序的时间复杂度为 O ( n l o g ( n ) ) O(nlog(n)) O(nlog(n))。
• 快排采用了分治法的思想。

2.2.1 排序思想

1. 从数列中挑出一个元素，称为基准（pivot），一般取第一个元素；
2. 通过一次划分，将待排元素分为左右两个子序列，所有元素比基准值小的摆放在左序列，所有元素比基准值大的摆在右序列（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为**分区**（partition）操作；
3. 然后分别对两个子序列继续进行划分，直至每一个序列只有一个元素为止；
4. 最后得到的序列便是有序的序列。

(注：图片来源：参考资料1)

• 一次划分的具体过程

  1. low指向待划分区域首元素（index=0）, high指向待划分区域尾元素（index=R.length-1）;
  2. base=R[low] (为了减少数据的移动,将作为标准的元素暂存到临时变量base中,最后再放入最终位置);
  3. high从后往前移动直到R[high]<base;
  4. R[low]=R[high], low++;
  5. low从前往后移动直到R[low]>=base;
  6. R[high]=R[low], high–;
  7. goto 3;
  8. 直到low==high时, R[low]=base (即将作为标准的元素放到其最终位置)。

  概括地说,一次划分就是从表的两端交替地向中间进行扫描,将小的放到左边,大的放到右边,作为标准的元素放到中间。
  之后采用递归的方式分别对前半部分和后半部分排序，当前半部分和后半部分均有序时该数组就自然有序了。

• 一次划分的具体过程示例

  1. low指向待划分区域首元素, high指向待划分区域尾元素;
     
  2. R[0]=R[low] (为了减少数据的移动,将作为标准的元素暂存到R[0]中,最后再放入最终位置);
     
  3. high从后往前移动直到R[high].key<R[0].key;
     
  4. R[low]=R[high], low++;

5. low从前往后移动直到R[low].key>=R[0].key;
   
6. R[high]=R[low], high–;
   
7. goto 3;

8. 直到low==high时, R[low]=R[0] (即将作为标准的元素放到其最终位置)。
- 示例

package pers.chh3213.sort;
public class QuickSort {
	public static void main(String[] args) {
		System.out.println("quick sort test");
		int[] arr = {9, -16, 30, 23, -30, -49, 25, 21, 30};
		System.out.println("before sort:");
		for (int i : arr) {
			System.out.print(i+"\t");
		}
		QuickSort quick = new QuickSort();
		quick.quickSort(arr, 0, arr.length-1);
		System.out.println();
		System.out.println("after sort:");
		for (int i : arr) {
			System.out.print(i+"\t");
		}

	}
	public  void quickSort(int[] arr,int start, int end) {
		if(start<end) {
			 int index = partition(arr, start, end); //将表一分为2
			 quickSort(arr, start, index-1); // 对左子序列进行快速排序
			 quickSort(arr, index+1, end); //对右子序列进行快速排序
		}

	}
//	一次划分
	public  int partition(int[] arr, int low,int high) {

		int base = arr[low]; //暂存基准元素到base
		while (low<high) {//从表的两端交替的向中间扫描
			while(low<high && arr[high]>=base)high--;//右端扫描
			if(low<high) {
				arr[low]=arr[high];//把比基准小的元素放到基准前面
				low++;
			}
			while(low<high && arr[low]< base)low++;//左端扫描
			if(low<high) {
				arr[high]=arr[low];//把比基准大的元素放到基准后面
				high--;
			}
		}
		arr[low] = base;//把基准元素放到最终位置

		return low;//返回基准元素所在的位置
	}
}

2.2.2 快速排序的递归树

• 快速排序的递归过程可用一棵二叉树形象地给出。下图为待排序列4,38,65,97,76,13,27,49所对应的快速排序递归调用过程的二叉树(简称为快速排序递归树)。
  

• 从快速排序算法的递归树可知，快速排序的趟数取决于递归树的高度。

2.2.3 快速排序的时间复杂度

• 如果每次划分对一个对象定位后,该对象的左子序列与右子
  序列的长度相同,则下一步将是对两个长度减半的子序列进行排序,这是最理想的情况。

• 假设n是2的幂, n = 2 k , ( k = l o g 2 n ) n=2^k,(k=log_2n) n=2k,(k=log2​n),假设基准位置位于序列中间，这样划分的子区间大小基本相等。
  n + 2 ( n / 2 ) + 4 ( n / 4 ) + . . . + n ( n / n ) = n + n + . . . + n = n ∗ k = n ∗ l o g 2 n n+2(n/2)+4(n/4)+ ...+n(n/n)=n+n+ ...+n=n*k=n*log_2n n+2(n/2)+4(n/4)+...+n(n/n)=n+n+...+n=n∗k=n∗log2​n

• 因此,快速排序的最好时间复杂度为 O ( n l o g 2 n ) O(nlog_2n) O(nlog2​n) 。而且在理论上已经证明,快速排序的平均时间复杂度也为 O ( n l o g 2 n ) O ( nlog_2n) O(nlog2​n) 。实验结果表明:就平均计算时间而言,快速排序是所有内排序方法中最好的一个。

• 在最坏的情况,即待排序对象序列已经按其排序码从小到大排好序的情况下,其递归树成为单支树,每次划分只得到一个比上一次少一个对象的子序列(蜕化为冒泡排序)。必须经过n-1趟才能把所有对象定位,而且第i趟需要经过n-i次排序码比较才能找到第i个对象的安放位置,总的排序码比较次数将达到
  ∑ i = 1 n − 1 ( n − i ) = 1 2 n ( n − 1 ) ≈ n 2 2 \sum_{i=1}^{n-1}{(n-i)}=\frac{1}{2}n(n-1) \approx \frac{n^2}{2} ∑i=1n−1​(n−i)=21​n(n−1)≈2n2​
  因此,快速排序的最坏时间复杂度为 O ( n 2 ) O(n^2) O(n2)。

2.2.4 快速排序的空间复杂度及稳定性

• 快速排序是递归的,需要有一个栈存放每层递归调用时的指针和参数。最大递归调用层次数与递归树的高度一致。理想情况为 l o g 2 ( n + 1 ) log_2(n+1) log2​(n+1)；最坏情况即待排序对象序列已经按其排序码从小到大排好序的情况下,其递归树成为单支树,深度为n。因此,快速排序最好的空间复杂度为 O ( l o g 2 n ) O (log_2n) O(log2​n) ,最坏的空间复杂度为 O ( n ) O(n) O(n)(即快速排序所需用的辅助空间)。
• 快速排序是一种不稳定的排序方法。

3. 选择排序

• 基本原理: 将待排序的元素分为已排序(初始为空)和未排序两组,依次将未排序的元素中值最小的元素放入已排序的组中。

3.1 简单选择排序

3.1.1 基本过程

1. 在一组元素R[i]到R[n]中选择具有最小关键码的元素
2. 若它不是这组元素中的第一个元素,则将它与这组元素中的第一个元素对调。
3. 除去具有最小关键字的元素,在剩下的
   元素中重复第1、2步,直到剩余元素只有一个为止。

package pers.chh3213.sort;

import java.util.Arrays;

public class SelectSort {
	public static void main(String[] args) {
		SelectSort select = new SelectSort();
		int[] arr = {9, -16, 310, 23, -30, -49, 25, 21, 30};
		select.selectSort(arr);
		System.out.println(Arrays.toString(arr));
	}
	public void selectSort(int[] arr) {
		for (int i = 0; i < arr.length; i++) {//进行n-1趟排序
			int min = i;
			for (int j = i+1; j < arr.length; j++) {
				if(arr[min]>arr[j])min=j; // 记录目前能找到的最小值元素的下标
			}
			 // 找到最小值后，再将找到的最小值和i位置所在的值进行交换
			if(i!=min)swap(arr, i, min);
		}
	}
	public void swap(int[] arr, int i, int j) {
		int temp =arr[i];
		arr[i]=arr[j];
		arr[j]=temp;
	}
}

3.1.2 简单选择排序的效率分析

1. 无论初始状态如何,在第i趟排序中选择最小关键码的元素,需做n-i次比较,因此总的比较次数为:
   ∑ i = 1 n − 1 n − i = n ( n − 1 ) / 2 = O ( n 2 ) \sum_{i=1}^{n-1}{n-i}=n(n-1)/2=O(n^2) ∑i=1n−1​n−i=n(n−1)/2=O(n2)(即时间复杂度)

2. 最好情况:序列为正序时,移动次数为 0 0 0, 最坏情况:序列为反序时,每趟排序均要执行交换操作,总的移动次数取最大值 3 ( n − 1 ) 3(n-1) 3(n−1)。

3. 由于在直接选择排序中存在着不相邻元素之间的互换,因此,直接选择排序是一种不稳定的排序方法。例如,给定排序码为3, 7, 3’, 2, 1,排序后的结果为1, 2, 3’, 3, 7

3.2 堆排序

• 堆排序是简单选择排序的改进。用直接选择排序从n个记录中选出关键字值最小的记录要做n-1次比较,然后从其余n-1个记录中选出最小者要作n-2次比较显然,相邻两趟中某些比较是重复的，为了避免重复比较,可以采用树形选择排序比较。
• 树形选择排序总的比较次数为 O ( n l o g 2 n ) O(nlog2 n) O(nlog2n),与直接选择排序比较减少了比较次数,但需要增加额外的存储空间存放中间比较结果和排序结果。故引入堆排序。

3.2.1 堆的定义

• n个元素的序列{k1, k2 , .... , kn },当且仅当满足
  { k i ≤ k 2 i k i ≤ k 2 i + 1 (1) \begin{cases} k_i\le k_{2i} \\ k_i \le k_{2i+1} \tag{1} \end{cases} {ki​≤k2i​ki​≤k2i+1​​(1)
  或者
  { k i ≥ k 2 i k i ≥ k 2 i + 1 (1) \begin{cases} k_i\ge k_{2i} \\ k_i \ge k_{2i+1} \tag{1} \end{cases} {ki​≥k2i​ki​≥k2i+1​​(1)
  称之为堆。

• 若将此排序码按顺序组成一棵完全二叉树,则(1)称为小顶堆(二叉树的所有结点值小于或等于左右孩子的值) , (2)称为**大顶堆(**二叉树的所有结点值大于或等于左右孩子的值).

• 小顶堆和大顶堆示例
  

3.2.2 堆排序的基本思想

1. 建初始堆
   将排序码k1, k2, k, ..,kn表示成一棵完全二叉树,然后从第n/2个排序码(即树的最后一个非终端结点)开始筛选,使由该结点作根结点组成的子二叉树符合堆的定义,然后从第n/2-1个排序码重复刚才操作,直到第一个排序码止。这时候,该二叉树符合堆的定义,初始堆已经建立。

2. 堆排序
   将堆中第一个结点(二叉树根结点)和最后一个结点的数据进行交换(k1,与kn,),再将 k 1 k_1 k1​~ k n − 1 k_{n-1} kn−1​,重新建堆,然后k1,和k_{n-2}交换,如此重复下去,每次重新建堆的元素个数不断减1,直到重新建堆的元素个数仅剩一个为止。这时堆排序已经完成,则排序码 k 1 , k 2 , k 3 , . . , k n k1, k2, k3, .., kn k1,k2,k3,..,kn已排成一个有序序列。

3. 堆排序的两大步骤

   • 根据初始输入数据形成初始堆
   • 通过一系列的元素交换和重新调整堆进行排序。

4. 堆排序的关键问题

   • 如何由一个无序序列建成一个堆?
   • 如何在输出堆顶元素之后,调整剩余元素,使之成为一个新的堆?

4. 二路归并排序

4.1 基本思想

• 将两个有序表合并成一个有序表。
  例如,将下列两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素,小者移入另一表中,反复如此,直至其中任一表都移入另一表为止。

• 示例
  （图片来源：参考资料3）

• 特点

  1. 在“递”的过程中，对数组均等一分为二，再将子数组，一分为二…；
  2. 在“归”的过程中，将这两个有序的子数组合并成一个有序的子数组；

package pers.chh3213.sort;

import java.util.Arrays;
/**
 *
* MergeSort.java
* @Description 归并排序
* @author chh3213
* @version
* @date 2021年12月26日下午4:54:53
 */
public class MergeSort {
	public static void main(String[] args) {
		MergeSort Sort = new MergeSort();
		int[] arr = {9, -16, 310, 23, -30, -49, 25, 21, 30};
		Sort.mergeSort(arr,0,arr.length-1);
		System.out.println(Arrays.toString(arr));
	}
	public void mergeSort(int[] arr,int left, int right) {
		int mid = (left+right)/2;
		if(left<right) {
			//递归
			mergeSort(arr, left, mid);//左边归并排序，使得左子序列有序
			mergeSort(arr, mid+1, right);//右边归并排序，使得右子序列有序
			//合并
			merge(arr, left, right, mid);//将两个有序子数组合并操作
		}
	}

	public void merge(int[] arr, int left,int right, int mid) {
		/*
		 * 将两个有序数组合并
		 */
		int[] temp = new int[right-left+1]; //建好一个临时数组
		int i=left; //左子序列索引（理解成指针）
		int j = mid+1;//右子序列索引（理解成指针）
		int k =0;//临时数组的索引（理解成指针）
		while(i<=mid && j<=right) {
			if(arr[i]<=arr[j]) {
				temp[k++]=arr[i++];
			}
			else {
				temp[k++]=arr[j++];
			}
		}
		while(i<=mid)temp[k++]=arr[i++];//将左子序列剩余元素填充进temp中
		while(j<=right)temp[k++]=arr[j++];//将右子序列剩余元素填充进temp中
		//将temp中的元素全部拷贝回原数组中
		for (int k2 = 0; k2 < temp.length; k2++) {
			arr[k2+left]=temp[k2];
		}
	}
}

4.2 效率分析

• 二路归并排序的时间复杂度等于归并趟数与每一趟时间复杂度的乘积。对n个元素的表,将这n个元素看作叶结点,若将两两归并生成的子表看作它们的父结点，则归并过程对应由叶向根生成一棵二叉树的过程。所以归并趟数等于二叉数的高度减1,即 l o g 2 n log_2n log2​n。每一趟归并需移动n个元素,即每一趟归并的时间复杂度为 O ( n ) O(n) O(n)。因此, 二路归并排序的时间复杂度为 O ( n l o g 2 n ) O(nlog_2n) O(nlog2​n)。
• 利用二路归并排序时,需要利用与待排序数组相同的辅助数组作临时单元故该排序方法的空间复杂度为 O ( n ) O(n) O(n) ,比前面介绍的其它排序方法占用的空间大。
• 由于二路归并排序中,每两个有序表合并成一个有序表时,若分别在两个有序表中出现有相同排序码,则会使前一个有序表中相同排序码先复制,后一有序表中相同排序码后复制,从而保持它们的相对次序不会改变。所以, 二路归并排序是一种稳定的排序方法。

5. 基数排序