冒泡排序

时间复杂度为O(n^2)

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

插入排序

时间复杂度：O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void InsertSort(int arr[], int n) {
    int i, j, temp;  // temp 用于暂存待插入元素
    for (i = 1; i < n; i++) {    // 从第二个元素开始（数组下标从0开始）
        if (arr[i] < arr[i-1]) {  // 若当前元素小于前驱，需要插入
            temp = arr[i];        // 暂存待插入元素
            
            // 从后向前寻找插入位置（无需检查下标越界）
            for (j = i-1; j >= 0 && temp < arr[j]; j--) { 
                arr[j+1] = arr[j]; // 元素后移
            }
            
            arr[j+1] = temp;      // 插入到正确位置
        }
    }
}

堆排序

特点

  1. 完全二叉树
  2. 任意节点大于/小于等于其左右孩子称为大根堆/小根堆
  3. 根节点最大/最小
  4. 建堆需要从最后一个非叶子节点开始调整
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 BuildMaxHeap(ElemType A[], int len){
	for(int i=len/2; i>0; i--){	//从i=[n/2]~1，反复调整堆
		HeadAdjust(A, i, len);
	}
}
/*函数HeadAdjust将元素k为根的子树进行调整*/
void HeadAdjust(ElemType A[], int k, int len){
	A[0] = A[k];	//A[0]暂存子树的根节点
	for(i=2*k; i<=len; i*=2){	//沿key较大的子结点向下筛选
		if(i<len && A[i]<A[i+1]){
			i++;	//取key较大的子节点的下标
		}
		if(A[0] >= A[i]){
			break;	//筛选结束
		}else{
			A[k] = A[i];	//将A[i]调整到双亲结点上
			k = i;	//修改k值，以便继续向下筛选
		}
	}
	A[k] = A[0];	//被筛选结点的值放入最终位置
}
void HeapSort(ElemType A[], int len){
	BuildMaxHeap(A, len);	//初始建堆
	for(i = len; i>1; i--){	//n-1趟的交换和建堆过程
		Swap(A, i, 1);	//输出堆顶元素（和堆底元素交换）
		HeapAdjust(A, 1, i-1);	//调整，把剩余的i-1个元素整理成堆
	}
}

归并排序

基本原理

将初始序列看成单个的子序列，然后相邻的两个子序列按照由小到大归并排序，然后重复，直到所有的子序列都归并完成

性质

时间复杂度：O(nlog2n)
稳定性：稳定

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
ElemType *B = (ElemType *)malloc((n+1)*sizeof(ElemType));	//辅助数组B
void Merge(ElemType A[], int low, int mid, int high){
	//表A的两段A[low...mid]和A[mid+1...high]各自有序，将它们合并成一个有序表
	for(int k=low; k<=high; k++){
		B[k] = A[k];	//将A中所有元素复制到B中
	}
	for(i=low, j=mid+1, k=i; i<=mid && j<=high; k++){
		//从low到mid，j从mid+1到high，k是最终排序数组的下标
		if(B[i] <= B[j]){	//比较B左右两段的元素
			A[k] = B[i++];	//将较小值赋值给A，B左段下标加1，右段不动
		}else{
			A[k] = B[j++];	//将较小值赋值给A，B右段下标加1，左段不动
		}
	}
	while(i <= mid){	
		//若第一个表（左段）未检测完，复制
		A[k++] = B[i++];
	}
	while(j <= high){	
		//若第二个表（右段）未检测完，复制
		A[k++] = B[j++];
	}
}
viod MergeSort(ElemType A[], int low, int high){
	if(low < high){
		int mid = (low + high)/2;	//从中间划分两个子序列
		MergeSort(A, low, mid);	//对左侧子序列进行递归排序
		MergeSort(A, mid+1, high);	//对右侧子序列进行递归排序
		Merge(A, low, mid, high);	//归并
	}
}