排序算法合集

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.视频????????