1. 排序概念

  • 通常待处理的数据不是单一的值，选择一个字段的值作为排序中比较的依据，该字段称为关键字
  • 若待排序数字中有关键字值相同的元素，经过某种排序后相对先后位置在排序先后没有变化，称为稳定排序算法。若不能保证相对先后位置不变，称为不稳定排序
  • 内排序：数据可放入声明的一组变量
  • 外部排序：排序过程中要进行内外存之间的数据交换，只能分批从文件中读入至内存变量
  • ==无特殊说明，排序后假定是非递减序列==

2. 内排序

2.1 冒泡排序

以两两比较为基础
第一趟排序：最大元素换到尾部；
第二趟排序：次大元素被换到尾部倒数第二个位置；
以此类推直至前面余下的元素个数为1

基础版：

1
2
3
4
5
6
7
8
9
for (int j=n-1; j>0; j--){
	for(int i=0; i<j; i++){
		if(a[i]>a[i+1]){
			tmp=a[i];
			a[i]=a[i+1];
			a[i+1]=tmp;
		}
	}
}

若某一趟排序中一次交换都没有发生，说明已经有序了，可据此设置一个flag

改进版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void bubbleSort(int a[], int n){
	int i,j;
	bool change=true;
	int tmp;
	for(j=n-1; j>0 && change; j--){
		change=false;
		for(i=0;i<j;i++){
			if(a[i]>a[i+1]){
				tmp=a[i];
				a[i]=a[i+1];
				a[i+1]=tmp;
				change=true;
			}
		}
	}
}

冒泡排序前者大于后者才交换，相等时保持不动，所以是稳定排序

时间复杂度是$o(n^2)$

2.2 插入排序

插入实现：

1
2
3
4
5
6
7
8
void insert(int a[], const int &x){
	int i;
	for(i=n-1; i>=0; i--){
		if(a[i]<=x) break;
		else a[i+1]=a[i];
	}
	a[i+1]=x;
}

每一次将第k个元素插入前面k-1个元素的有序序列中

1
2
3
4
5
6
7
8
9
void insertSort(int a[], int n){
	int i;
	int tmp;
	
	for(i=1; i<n; i++){
		tmp=a[i];
		insert(a,i,tmp);
	}
}

稳定排序，时间复杂度为o($n^2$)

2.3 希尔排序

先进行预处理：将原始序列按不同步长分成若干子序列，分别进行插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void shellSort(int a[], int n){
	int step,i,j;
	int tmp;
	for(step=n/2; step>0; step/=2){
		for(i=step; i<n; i++){
			tmp=a[i];
			j=i;
			// 类似插入排序
			while((j-step>=0) && (tmp<=a[j-step])){
				a[j]=a[j-step];
				j-=step;
			}
			a[j]=tmp;
		}
	}
}

不稳定排序，时间复杂度为o($n^{1.3}$)

2.4 归并排序

假设现在有两个有序数组存放在数组a当中，其中第一个从下标low-mid，第二个mid+1-high

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void merge(int a[], int low, int mid, int high){
	int i,j,k;
	int *c;
	c=new int [high-low+1];
	i=low;
	j=mid+1;
	k=0;
	
	while((i<=mid)&&(j<=high)){
		if(a[i]<=a[j]){
			c[k]=a[i];
			i=i+1;
		}
		else{
			c[k]=a[j];
			j=j+1;
		}
		k=k+1;
	}
	
	while(i<=mid){
		c[k]=a[i];
		i=i+1;
		k=k+1;
	}
	
	while(j<=high){
		c[k]=a[j];
		j=j+1;
		k=k+1;
	}
	
	for(i=0; i<high-low+1; i++){
		a[i+low]=c[i];
	}
	delete[] c;
}

每个元素可以看成是长度为1的有序序列，两两归并，形成长度为2的有序序列，再两两归并，反复操作

1
2
3
4
5
6
7
8
9
10
11
12
void mergeSort(int a[], int n){
	mergeSort(a,0,n-1);
}

void mergeSort(int a[], int low, int high){
	int mid;
	if(low>=high) return;
	mid=(low+high)/2;
	mergeSort(a,low,mid);
	mergeSort(a,mid+1,high);
	merge(a,low,mid,high);
}

稳定排序
时间复杂度为o($nlog_2 n$)

2.5 快速排序

选择一个元素作为“标杆”，小于它的元素移到前面，大于它的元素移到后面，对标杆前后两个字序列分别排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void quickSort(int a[], int n){
	quickSort(a,0,n-1);
}

void quickSort(int a[], int start, int end){
	int i,j,hole;
	int temp;
	if(end<=start) return;
	temp=a[start];
	hole=start;
	i=start;
	j=end;
	while(i<j){
		while((j>i) && (a[j]>=temp)) j--;
		if(j==i) break;
		a[hole]=a[j];
		hole=j;
		while((i<j) && (a[i]<temp)) i++;
		if(j==i) break;
		a[hole]=a[i];
		hole=i;
	}
	a[hole]=temp;
	quickSort(a,start,hole-1);
	quickSort(a,hole+1,end);
}

搜索一趟的时间复杂度为o(n);
若每一次标杆都是中间位置，时间复杂度为$o(nlog_2n)$
若最不幸，时间复杂度为$o(n^2)$

所以如果需要改进，可以取中间位置为标杆，或者是在首、尾、中间三个位置中找到中间值，将其作为标杆，但是在排序前，要将标杆元素换到首位置上

这种排序是不稳定排序

2.6 选择排序

从左到右给每个位置选择合适的元素
在下标0-n-1选择最小值，放到位置0；
在下标1-n-1选择最小值，放到位置1；
以此类推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void selectSort(int a[],int n){
	int i,j,minIndex;
	int tmp;
	for(i=0;i<n;i++){
		minIndex=i;
		for(j=i+1;j<n;j++){
			if(a[j]<a[minIndex]) minIndex=j;
		}
		if(minIndex==i) continue;
		temp=a[i];
		a[i]=a[minIndex];
		a[minIndex]=temp;
	}
}

时间复杂度为$o(n^2)$
不稳定排序

2.7 堆排序

大顶堆：完全二叉树中，任意一个结点的值比左右子节点值都大
小顶堆：完全二叉树中，任意一个结点的值比左右结点值都小
大小顶堆都称为堆

操作：将原数组序列看作是一棵完全二叉树顺序存储，调整为最大堆，摘取大顶，换到待处理元素的最后位置。继续调整新的根，变成大顶堆，得次大元素……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void heapSort(int a[], int n){
	int i,j;
	int temp;
	//首次建立大顶堆
	for(i=(n-1)/2;i>=0;i--) adjust(a,n,i);
	for(j=n-1;j>=1;j--){
		temp=a[0];
		a[0]=a[j];
		a[j]=temp;
		adjust(a,j,0);
	}
}

void adjust(int a[], int n, int i){
	int maxChild;
	int temp;
	while(true){
		maxChild=2*i+1;//左子下标
		if(maxChild>n-1) return;
		if(maxChild+1<=n-1){
			if(a[maxChild+1]>=a[maxChild]) maxChild++;
		}
		if(a[i]>a[maxChild]) return;
		temp=a[i];
		a[i]=a[maxChild];
		a[maxChild]=temp;
		i=maxChild;
	}
}

时间复杂度为$o(nlogn)$
是不稳定排序

2.9 基数排序

  • 多关键字排序：主关键字+次关键字
  • 基数排序：基于多关键字排序思想，解决单一关键字排序问题，即把单一关键字的不同位数视作多关键字进行排序
  • 分为最高位优先法（MSD）和最低位优先法（LSD）。最高位优先法的排序分的子序列个数与数字大小有关，比较复杂，一般选用最低位优先法
  • 若元素最大位数为m，算法的复杂度是o(mn)

2.10 总结

![[7-内排序综合对比.png]]

3. 外排序

3.1 外排序

外排序：元素个数太多，无法一次性载入内存，需要在内外存间进行数字交换。
方法：
预处理：N个记录分批读入内存，通过内排序算法形成有序片段
归并：把这些有序片段归并为有序文件

3.2 预处理

按照内存容量尽可能多地读入数据，在内存进行排序。

3.3 归并

最简单：二路归并，需要四条磁带。无需序列放在2条磁带，排序后进入另外两条磁带。

k路归并需要k+1个磁带即可

假设有三条磁带和34个已排序片段，初始如何分配两条磁带上的片段数目？
若已排序片段是斐波那契数，分解成它的前两项。

3.4 置换选择

可以让在只能容纳p个记录的内存中生成平均长度为2p的初始已排序片段

![[7-置换选择.png]]

时间消耗为o(m)，但是如果内存中元素按最小化堆存储，时间消耗为$o(log_2m)$

http://chenjiayi0505.github.io/2026/07/02/数据结构 第七章 排序/
作者
Jiayi Chen
发布于
2026年7月2日
更新于
2026年6月17日
许可协议