526互联

[c/c++][考研复习笔记]排序篇学习笔记

发布时间 2023-07-23 18:13:30作者: J1nWan

考研排序复习笔记

  • 插入排序

#include<stdio.h>
#include<stdlib.h>

#define MaxSize 9
//折半插入排序 
void ZBInsertSort(int A[],int n){
	int i,j,high,low,mid;
	for(i=2;i<=n;i++){
		A[0] = A[i];
		low = 1;high = i-1;
		while(low<=high){
			mid=(low+high)/2;
			if(A[mid]>A[0]){
				high=mid-1;
			}
			else{
				low = mid+1;
			}
		}
		for(j = i-1;j>=high+1;--j){
			A[j+1] = A[j];
		}
		A[high+1] = A[0];
	}
}

//直接插入排序（带哨兵）
void InsertSort(int A[],int n){
	int i,j;
	for(i=2;i<=n;i++){
		if(A[i]<A[i-1]){
			A[0] = A[i];
			for(j =i-1;A[0]<A[j];j--){
				A[j+1] = A[j];
			}
			A[j+1] = A[0];
		}
	}
} 


//插入排序的复杂度都是O(n^2) 
int main(){
	int A[] = {0,49,38,65,97,76,13,27,49};
	for(int i = 1;i<MaxSize;i++){
		printf("%d ",A[i]);
	}
	ZBInsertSort(A,8);
	printf("\n");
	for(int i = 1;i<MaxSize;i++){
		printf("%d ",A[i]);
	}
	return 0;
}

image-20230723155126455

image-20230723155159496

空间复杂度：$O(1)$

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

相当于从A[2]一路顺序查找下去，是A[1]往后逐渐有序。

开始后A[1]----A[2]----是有序的

这部分可以使用折半查找

image-20230723155511552

复习折半查找的停止条件：low>high

  • A[0]>mid

    • 数在mid后面，low = mid + 1

  • A[0]<mid

    • 说明数在mid前面部分，high = mid - 1

  • 希尔排序（Shell Sort）

灵感来源：插入排序在基本有序的情况下表现很好

image-20230723155949398

所以希尔排序的思想是基于这种基本有序

image-20230723160104903

image-20230723160130500

image-20230723160146775

希尔排序代码实现

#include<stdio.h>
#include<stdlib.h>

#define MaxSize 9

//希尔排序 
//往后逐个对比 
void ShellSort(int A[],int n){
	int d,i,j;
	for(d = n/2;d>=1;d = d/2){
		for(i=d+1;i<=n;++i){
			if(A[i]<A[i-d]){
				A[0] = A[i];
				for(j=i-d;j>0 && A[0]<A[j];j-=d)
					A[j+d] = A[j];
				A[j+d] = A[0];
			}
		}
	}
}
//希尔排序
//一串捋直了再下一串 
void testShellSort(int A[],int n){
	int d,i,j;
	for(d = n/2;d>=1;d=d/2){ //步长变化 
		for(i=1;i<=d;i++){ //多少组 
			for(i=d+1;i<=n;i+=d){ //遍历每一组的所有数字 
				if(A[i] < A[i-d]){
					A[0] = A[i]; //小的放在A[0] 
					for(j=i-d;j>0 && A[0]<A[j];j-=d){
						A[j+d] = A[j];
					}
					A[j+d] = A[0];
				}
			}
		}
	}
} 
//插入排序的复杂度都是O(n^2) 
int main(){
	int A[] = {NULL,49,38,65,97,76,13,27,49};
	for(int i = 1;i<MaxSize;i++){
		printf("%d ",A[i]);
	}
	testShellSort(A,8);
	printf("\n");
	for(int i = 1;i<MaxSize;i++){
		printf("%d ",A[i]);
	}
	return 0;
}

以上第一种是：i++，逐个逐个比较各自的串

第二种是 只扫描A[0] -> A[1] ->A[2]->>>一个d，在每次扫描到一个串的时候完成这个串的排序

image-20230723160530162

image-20230723160705693

image-20230723160832947

$空间复杂度为O(1)$

$时间复杂度与选取的d挂钩$

当第一次选取d=1时，希尔排序 退化为 插入排序

稳定性分析：image-20230723161205093

稳定性：不稳定

且只使用于顺序表，不使用于链表

  • 冒泡排序（Bubble Sort）

基于交换的排序：根据序列中两个元素的关键字的比较结果来对换两个记录在序列中的位置

image-20230723161518835

image-20230723161636155

image-20230723161809053

当最后一趟没有任何交换时，说明已经有序了

#include<stdio.h>
#include<stdlib.h>
void swap(int &a,int &b){
	int temp;
	temp = a;
	a = b;
	b = temp;
}
//MM手写版 version.1 
void BubbleSort(int A[],int n){
	for(int i=1;i<=n-1;i++){  
		bool flag = false;
		for(int j=n-1;j>=i;j--){ //犯错1：int j=n-1;j=i;j-- 每次判断的时候都会重新定义j导致永远退不出循环！ 
			if(A[j]<A[j-1]){
				swap(A[j],A[j-1]);
				flag = true;
			}
		}
		if(flag == false){ //犯错2：if flag == false 太粗心！ 
			break;
		}
	}
}
// mm手写版与王道给的基本一致 
//王道版
void WD_BubbleSort(int A[],int n){
	for(int i=0;i<n-1;i++){			//交换的趟数 = n-1
		bool flag = false; //表示本趟冒泡是否发生交换的标志
		for(int j=n-1;j>i;j--){ //一趟冒泡
			if(A[j-1] > A[j]){   //若为逆，则交换
				swap(A[j-1],A[j]);
				flag = true;
			}
		}
		if(flag == false){ //本趟遍历之后如果没有发生交换，则已经有序
			break;
		}
	}
} 

int main(){
	int list[] = {49,38,65,97,76,13,27,49};
	
	for(int i = 0;i<=7;i++){
		printf("%d ",list[i]);
	}
	printf("\n");
	BubbleSort(list,8);
	for(int i = 0;i<=7;i++){
		printf("%d ",list[i]);
	}
	printf("\n");
	return 0;
}

image-20230723165228968

冒泡排序显然是稳定的

image-20230723165325388

且适用于链表

代码给的是从后往前冒，其实从前往后也是可以的所以要注意题目给的条件

易忘点：如果一趟排序过程未发生“交换”，则可以提前结束

  • 快速排序

如名字所言：确实是最厉害的

image-20230723165950452

image-20230723170009459

image-20230723170031075

image-20230723170055308

核心思想：

$high所指的>基准:high--$

$high所指 < 基准:放到low那里$

$low所指 < 基准:low++$

$low所指 > 基准:放到high那里$

终止条件: $low == high$

image-20230723170428935

于是划分为$$【<A】 | 【A】 | 【>A】$$

再分别在两边重复以上过程image-20230723170643800

#include<stdio.h>
#include<stdlib.h>

//Partition （分割） 
int Partition(int A[],int low,int high){
	int pivot = A[low];  //pivot:枢轴
	while(low < high){
		while(low<high && A[high] >=pivot) --high; //high前推找比pivot小的 
		A[low] = A[high];							 
		while(low<high && A[low] <=pivot) ++low;	//low后推找比pivot大的 
		A[high] = A[low];
	}
	A[low] = pivot;
	return low;
} 

void QuickSort(int A[],int low,int high){
	if(low<high){ //递归跳出的条件 
		int pivotpos = Partition(A,low,high); //划分 
		QuickSort(A,low,pivotpos-1);			//划分左子表 
		QuickSort(A,pivotpos+1,high); 			//划分右子表 
	}
} 

int main(){
	int list[] = {49,38,65,97,76,13,27,49};
	
	for(int i = 0;i<=7;i++){
		printf("%d ",list[i]);
	}
	printf("\n");
	QuickSort(list,0,7);
	for(int i = 0;i<=7;i++){
		printf("%d ",list[i]);
	}
	printf("\n");
	return 0;
}

image-20230723172958047

空间复杂度：

image-20230723173043560

其实分析起来

本质上就像一个二叉树

image-20230723173737768

最好/最坏情况分析：image-20230723173929571

image-20230723174131703

快速排序的稳定性：不稳定！image-20230723174233522image-20230723174253368image-20230723174310578

  • 简单选择排序

image-20230723174600817

从头到尾扫描 1 次image-20230723174802361然后交换位置

从头到尾扫描 2 次image-20230723174837082 然后交换位置

从头到尾扫描 3 次image-20230723174917223然后交换位置

$n个元素的简单排序需要处理n-1趟$

代码实现：

#include<stdio.h>
#include<stdlib.h>
void swap(int &a,int &b){
	int temp;
	temp = a;
	a = b;
	b = temp;
}
//MM手写版 version.1 
//王道版交换的是index，我交换的是数据 
void SelectSort(int A[],int n){
	for(int i=0;i<n;i++){ //需要排n-1次 *error：i<n-1就行了 因为n=8,最后一个元素实际下标是7 
		int min = A[i]; 
		for(int j=i;j<n;j++){ //逐行扫描 
			if(A[j]<min){
				swap(min,A[j]); 
			}
		}
		A[i] = min;
	} 
}

//王道版 简单选择排序
void WD_SelectSort(int A[],int n){
	for(int i=0;i<n-1;i++){   //一共排n-1趟 
		int min = i;			//记录最小元素位置 
		for(int j=i+1;j<n;j++)
			if(A[j]<A[min]) min=j;	//更新最小元素位置 
		if(min != i) swap(A[i],A[min]); 
	}
} 

int main(){
	int list[] = {49,38,65,97,76,13,27,49};
	
	for(int i = 0;i<=7;i++){
		printf("%d ",list[i]);
	}
	printf("\n");
	WD_SelectSort(list,8);
	for(int i = 0;i<=7;i++){
		printf("%d ",list[i]);
	}
	printf("\n");
	return 0;
}

image-20230723180328259

image-20230723180412474

可以使用链表来练练手！