JakeLin

用户名：jake546

访问量：43185

签　名：

腾讯需要我！

等　　级
排　　名	40
经　　验	13199
参赛次数	3
文章发表	85
年　　龄	21
在职情况	学生
学　　校	华南农业大学
专　　业

　　自我简介：

幸福是奋斗出来的

TA的其他文章

JakeLin-1460题-2n皇后问题-题解(C/C++) - n皇后/2n皇后详解
浏览：810

JakeLin-1522题-我们的征途是星辰大海-题解(C++代码)
浏览：812

JakeLin-1545题-蓝桥杯算法提高VIP-现代诗如蚯蚓-题解(C++代码)-简易解法
浏览：307

你可能喜欢

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

A+B for Input-Output Practice (III) （C++代码）

JakeLin-几种排序算法代码小记（插入/选择/快速/归并/冒泡/更新中...）

　　作者: JakeLin　　　　发表时间：2020-04-06 15:21:56 浏览：376　|　评论：0　

```cpp
【已有无序数组a[n],n个元素，采用不同的排序算法对齐进行升序排序】

一、直接插入排序：
【思路】：将数组分为有序与无序两部分，初始：【第1位是有序序列，剩下的为无序序列】，将无序数组的第一个插入到有序数组中的合适位置，有序数组扩展一位，以此迭代，直至无序数组完
【具体做法】：从第二位开始，与之前有序数组逐一比较，若比前面的数字还小则交换位置，直至不能交换说明前面比它还小，则找到最终位置
int main(){
	for(int i=1;i<n;i++){
		int p=i;
		while(a[p]<a[p-1] && p>=1){
			swap(a[p],a[p-1]);
			p--;
		}
	}
}

二、简单选择排序：
【思路】：将数组分为有序与无序两部分，从无序数组中选择最小的一个，将它放到有序数组的最后一个
【具体做法】：从1~n找出最小的放到第1位，从2~n找出最小的放在第2位，以此类推，直至n-1为被确定
int main(){
	for(int i=0;i<n-1;i++){
		int minn = 0x3f3f3f3f;
		int index = i;
		for(int j=i;j<n;j++){
			if(a[j]<minn){
				minn = a[j];
				index = j;
			}
		}
		swap(a[i],a[index]);
	}
}

三、快速排序：
【思路】：每次从待排序数组中拿出一枢轴（可设为序列第1位），确定枢轴的位置，使得数轴左边的比它小，右边的比它大，在递归排序枢轴左区间与右区间，直至该区间只有一位数
【具体做法】：双指针的做法，设定两个指针在区间的最左和最右，并交替向中间移动。右区间需要比枢轴大，所以右指针所指若比枢轴大则继续移动，直至该值小于枢轴，则与左指针（此时枢轴位置）交换；左区间需要比枢轴小，所以左指针所指若比枢轴小则继续移动，直至该值大于枢轴，则与右指针（此时枢轴位置）交换，最终确定枢轴位置
void Qsort(int a[],int left,int right){
	if(left>=right) return; 
	int l = left;
	int r = right;
	while(l<r){
		while(a[r]>=a[l] && l<r){
			r--;
		}
		swap(a[r],a[l]);
		while(a[l]<=a[r] && l<r){
			l++;
		}
		swap(a[r],a[l]);
	}
	Qsort(a,left,l-1);
	Qsort(a,l+1,right);
}
int main(){
	Qsort(a,0,n-1);
}

四、归并排序
【思路】：采用分支思想，先分后置
分：从中间切割该序列，分为左右区间，左右区间继续切割，直至区间只有1位数值
治：将小序列进行归并，注意是【有序归并】，而不是简单连接
【具体做法】：
分：递归切割，如mergeSort所示，直至区间只有一个值
治：需申请一中间数组，比较两个小序列，各有其起始指针，比较其值大小，小的放入中间数组，再见指针右移，重新比较，以此类推，直至其中一序列全被放入数组中，再将另一序列剩下部分全丢进去，注意通过中间数组【更新原数组】
void merge(int *a,int l,int r,int p,int q,int *tmp){
	int left = l;
	int right = q;
	int cnt=0;
	while(l<=r && p<=q){
		if(a[l]<a[p]){
			tmp[cnt++]=a[l++];
		}else{
			tmp[cnt++]=a[p++];
		}
	}
	while(l<=r){
		tmp[cnt++] = a[l++];
	}
	while(p<=q){
		tmp[cnt++] = a[p++];
	}
	cnt=0;
	while(left<=right){
		a[left++] = tmp[cnt++];
	}
}
void mergeSort(int *a,int l,int r,int *tmp){
	if(l!=r){
		int m = (l+r)/2;
		mergeSort(a,l,m,tmp);
		mergeSort(a,m+1,r,tmp);
		merge(a,l,m,m+1,r,tmp);
	}
}
int main(){
	mergeSort(a,0,n-1,tmp);
	for(int i=0;i<n;i++){
		cout<<a[i]<<" ";
	}
}

五、冒泡排序
【思路】：将序列分为有序序列和无序序列两部分，有序序列位于后半部分，初始为空，每次将无序序列中最大的一个值上升到最后，成为有序序列最前面的一个，每次最大的值都向上（后）走，故称为冒泡。
【具体操作】：无需序列两两相比，大的那个放在后面，故可实现大的数值往上冒泡。
int main(){
	int p=1;  // 记录有序序列长度
	while(p<n){
		for(int i=0;i<n-p;i++){
			if(a[i]>a[i+1]){
				swap(a[i],a[i+1]);
			}
		} 		
		p++;
	}
}
	
六、折半插入排序,待更新...

七、堆排序,待更新...

八、结构体排序,待更新...

九、时空复杂度的比较,待更新...
```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

JakeLin

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

A+B for Input-Output Practice (III) （C++代码）

The 3n + 1 problem （C语言代码）

JakeLin-几种排序算法代码小记（插入/选择/快速/归并/冒泡/更新中...）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题12.3 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

【绝对值排序】（C++代码）

人见人爱A+B （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

WU-输入输出格式练习（C++代码）

1157题解

JakeLin

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

A+B for Input-Output Practice (III) （C++代码）

The 3n + 1 problem （C语言代码）

JakeLin-几种排序算法代码小记（插入/选择/快速/归并/冒泡/更新中...）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题12.3 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

【绝对值排序】 （C++代码）

人见人爱A+B （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

WU-输入输出格式练习 （C++代码）

1157题解

　　评论区

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

【绝对值排序】（C++代码）

WU-输入输出格式练习（C++代码）