排序算法合集

2023-12-24 17:39:11

1.插入排序

? ? ? ? 1.步骤

????????????????1.从第一个元素开始,该元素可以认为已经被排序
????????????????2.取下一个元素tem,从已排序的元素序列从后往前扫描
????????????????3.如果该元素大于tem,则将该元素移到下一位
????????????????4.重复步骤3,直到找到已排序元素中小于等于tem的元素
????????????????5.tem插入到该元素的后面,如果已排序所有元素都大于tem,则将tem插入到下标为0的位置
????????????????6.重复步骤2~5。

? ? ? ? 2.动图

? ? ? ? ? ? ? ??

????????3.思路

????????????????? ?在待排序的元素中,假设前n-1个元素已有序,
????????????????? ?现将第n个元素插入到前面已经排好的序列中,使得前n个元素有序。
????????????????? ?按照此法对所有元素进行插入,直到整个序列有序。


????????4.时间复杂度:? ??

????????????????? 最坏情况下为O(N^2)
????????????????? 最好情况下为O(N),此时待排序列为升序,或者说接近升序。

????????5.代码:

#include<bits/stdc++.h>
using namespace std;
void InsertSort(int *arr, int n) {
	for (int i = 2; i <= n ; ++i) {
		int end = i;
		while (end > 1) {
			if (arr[end] < arr[end-1]) {
				swap(arr[end],arr[end-1]);
				end--;
			} else {
				break;
			}
		}
	}
}
main() {
	int a[100],b,c;
	cin>>b;
	for(int i=1; i<=b; i++) {
		cin>>a[i];
	}
	InsertSort(a,b);
	for(int i=1; i<=b; i++) {
		cout<<a[i]<<"  ";
	}
}

2.选择排序

????????1.思路:??

每次从待排序列中选出一个最小值,然后放在序列的起始位置,直到全部待排数据排完即可。
实际上,我们可以一趟选出两个值,一个最大值一个最小值,然后将其放在序列开头和末尾,这样可以使选择排序的效率快一倍。

? ? ? ? 2.动图

????????3.?时间复杂度:

????????????????最坏情况:O(N^2)
?????????? 最好情况:O(N)

?

????????4.代码

#include<bits/stdc++.h>
using namespace std;
void SelectSort(int *arr, int n) {
	int begin = 1, end = n ;
	while (begin < end) {
		int maxi = begin;
		int mini = begin;
		for (int i = begin; i <= end; ++i) {
			if (arr[i] < arr[mini]) {
				mini = i;
			}
			if (arr[i] > arr[maxi]) {
				maxi = i;
			}
		}
		swap(arr[mini], arr[begin]);
		if (begin == maxi) {
			maxi = mini;
		}
		swap(arr[maxi], arr[end]);
		++begin;
		--end;
	}
}
main() {
	int a[100],b;
	cin>>b;
	for(int i=1; i<=b; i++) {
		cin>>a[i];
	}
	SelectSort(a,b);
	for(int i=1; i<=b; i++) {
		cout<<a[i]<<"   ";
	}
}

3.快速排序(我习惯叫“挖坑法”)

? ? ? ? 1.思路

????????????????1.选出一个数据(一般是最左边或是最右边的)存放在key变量中,在该数据位置形成一个坑
????????????????2、定义一个L和一个R,L从左向右走,R从右向左走。(若在最左边挖坑,则需要R先走;若在最右边挖坑,则需要L先走)

? ? ? ? 2.动图

????????

????????3.代码?

#include <iostream>
using namespace std;
void QuickSort(int *array, int low, int high) {
	if (low >= high) {	
		return ;
	}
	int i = low;	
	int j = high;	
	int key = array[low]; 
	while (i < j) {
		while (array[j] >= key && i < j) {	
			j--;	
		}
		array[i] = array[j];	
		while (array[i] <= key && i < j) {	
			i++;	//找不到则i加一
		}
		array[j] = array[i];	
	}
	array[i] = key;	
	QuickSort(array, low, i - 1);	
	QuickSort(array, i + 1, high);	
}
int main() {
	int array[10000], abb;
	cin >> abb;
	for (int i = 1; i <= abb; i++) {
		cin >> array[i];
	}
	cout << "原始序列:";
	for (int i = 1; i <= abb; i++) {
		cout << array[i] << " ";
	}
	cout << endl;
	QuickSort(array, 1, abb);
	cout << "快排序列:";
	for (int i = 1; i <= abb; i++) {
		cout << array[i] << " ";
	}
	return 0;
}

????????4.视频????????

全网最清晰快速排序,看完快排思想和代码全部通透,不通透你打我!

文章来源:https://blog.csdn.net/sjy100401/article/details/132790736
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。