【数据结构】插入排序、冒泡排序、堆排序、快速排序、基数排序、归并排序简略解析

发布于2021-06-07 22:44 阅读(630) 评论(0) 点赞(22) 收藏(1)

临近考研、面试，抽了几个平时不太会写的排序算法重新温习了一下，下面做个总结，亦或者说用一句话概括一下简略思想吧。

排序算法简要解析

插入排序
冒泡排序
堆排序
快速排序
基数排序
归并排序
Code:
运行截图：

插入排序

假设前 $i - 1$ 个元素已经有序，那么很容易通过 $O (n)$ 的算法应该插入的位置，使得前i个元素有序，所以复杂度为： $O(n^2)$

冒泡排序

假设前 $i$ 个元素已经是已知序列中的前 $i$ 小元素，并且已经有序，那么将后面 $n - i$ 个元素中的最小值(第 $i + 1$ 小元素)通过交换置换到 $i + 1$ 的位置即可。

堆排序

前置知识：

首先要知道堆其实是一种二叉树的树形数据结构，在保证一个节点的权值比两个孩子节点都要大(小)的情况下，成为大(小)根堆。
可以利用完全二叉树的性质，直接用数组来模拟树形结构，那么对于编号 $[0, n - 1]$ 的数组来说， $i$ 的左孩子即为: $\times 2+1$ ,右孩子即为 $\times2+2$ ,对于编号 $[1, n]$ 的数组来说，左孩子即为: $\times 2$ ,右孩子即为 $\times2+1$ ，父节点编号也可以自行推出。

基础思路：

初始化堆

此时可以建立与树形dp相关的思路，保证子树都满足节点值大于左右孩子值。
所以此时由下向上进行树形dp，每次对于一个新来的元素 $x$ ，都可以找到 $x$ 会被替换到什么位置。
从最后一个非叶子节点开始，每次都将这个节点插入到其子树的某个位置中，因为满足 $d p$ 的性质:子树都满足大(小)根堆的性质，那么一旦发现这个数比左右孩子都大(小)，停止就可以了。

堆调整(AdjustHeap)

堆调整就是初始化堆时，对于第x个数，应该插入到什么位置。
复杂度: $O (l o g n)$

堆排序

首先初始化堆，利用堆调整函数
初始化堆完成后，最大(小)值应该是根元素，将此时根元素和最后一个叶子节点元素互换位置，将剩下的 $n - 1$ 个元素组成一个新的堆，由于这个新的堆保留着初始化堆的性质，交换第一个与第 $n$ 个元素之后，就相当于根元素发生了变化需要重新进行一次堆调整 $(A d j u s t H e a p)$ .
执行 $n - 1$ 次之后，数组就有序了

快速排序

选择一个基值，分别需要一个左、右指针，将左边大于基值的都放在基值右边，将右边大于基值的都放在基值左边。这样一来，基值的位置就确定了，由基值继续进行分治，所以复杂度是 $O (n l o g n)$ ，最坏复杂度 $O(n^2) →$ 取决于基值的选择。

基数排序

这个排序时间上应该是最优的，如果基数选择合理。一般取 $log_{10}(a_i)$ ，所以复杂度是 $nlog_{10}(a_i)$ 。

思路是基于桶排的，首先先从个位数开始进行排序，然后十位数、百位数 $\dots$ 最高位数，这样只需要借助一个外来的辅助空间即可完成排序。

因为需要借助辅助空间，所以空间复杂度和时间复杂度均为 $o (n * k)$

归并排序

分治思想即可，假设 $[l, m i d]$ 与 $[m i d + 1, r]$ 均有序，所以可以借助额外的辅助空间进行两个区间的有序链表合并，所以时空复杂度均为 $O (n l o g n)$

Code:

/*** keep hungry and calm CoolGuang!  ***/
//#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e18+7;
const int maxn = 1e6+7;
const int mod= 1e9+7;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll m,p;

class test{
	public :
		test(int _N){
			n = _N;
			for(int i=1;i<=n;i++) s[i] = i;
			printf("test constructed\n");
		}
		~test(){
			printf("test destroyed\n");
		}
		void write(){
			for(int k=1;k<=n;k++)
				printf("%d ",s[k]);
			printf("\n");
		}
		void SrandBack(){random_shuffle(s+1,s+1+n);}
		void InsertSort(){
			for(int i=1;i<=n;i++){//前i-1个已经有序
				int k = i-1,t = s[i];
				while(k>=1&&s[k]>t){
					s[k+1] = s[k];
					k--;
				}
				s[k+1] = t;
			}
		}
		void BubbleSort(){
			for(int i=1;i<=n;i++){
				for(int k=n-1;k>=i;k--){
					if(s[k+1]<s[k]) swap(s[k],s[k+1]);
				}
			}
		}

		void AdjustHeap(int len,int pos){
			int tmp = s[pos];
			for(int i=2*pos;i<=len;i=2*i){
				if(i+1<=len && s[i+1]>s[i]) i++;
				if(s[i]>tmp){
					s[pos] = s[i];
					pos = i;
				}else break;
			}
			s[pos] = tmp;
		}
		void HeapSort(){
			///Restore Heap
			for(int i=n/2;i>=1;i--) AdjustHeap(n,i);
			///HeapSort
			for(int i=n;i>=2;i--){
				swap(s[i],s[1]);
				AdjustHeap(i-1,1);
			}
		}
		void work(int L,int R){
			if(L>=R) return;
			int tmp = s[(L+R)/2];
			int l = L,r = R;
			while(l<r){
				while(l<r && s[r]>tmp) r--;
				while(l<r && s[l]<tmp) l++;
				if(l<=r){
					swap(s[l],s[r]);
					l++;
					r--;
				}
			}
			work(l,R);
			work(L,r);
		}
		void QuickSort(){work(1,n);}	
		void Merge(int l,int r){
			if(l>=r) return;
			int mid = (l+r)/2;
			Merge(l,mid);
			Merge(mid+1,r);
			int L = l,R = mid+1;
			int cnt = 0;
			while(L<=mid && R<=r){
				if(s[L]  <= s[R]) cp[++cnt] = s[L++];
				else cp[++cnt] = s[R++];
			}
			if(L<=mid) for(int k=L;k<=mid;k++) cp[++cnt] = s[k];
			if(R<=r) for(int k=R;k<=r;k++) cp[++cnt] = s[k];
			for(int k=1;k<=cnt;k++) s[l+k-1] = cp[k];
		}
		void MergeSort(){Merge(1,n);}
		void RadixSort(){
			int maxlen = 0,mx = 0;
			for(int k=1;k<=n;k++) mx = max(mx,s[k]);
			while(mx){maxlen++;mx/=10;}
			int base = 1;
			while(maxlen--){
				int cnt = 0;
				for(int k=0;k<=9;k++) c[k][0] = 0;
				for(int k=1;k<=n;k++){
					int idx =(s[k]/base)%10;
					c[idx][++c[idx][0]] = s[k];
				}
				for(int k=0;k<=9;k++){
					for(int i=1;i<=c[k][0];i++)
						s[++cnt] = c[k][i];
				}
				base *= 10;
			}
		}
	private:
		int s[1005],cp[1005],n;
		int c[1005][10];//Radix
};
int main(){
  auto p = make_shared<test>(10);
  printf("-------InsertSort--------\n");
  p->SrandBack();
	p->write();
	p->InsertSort();
	p->write();
	printf("-------BubbleSort--------\n");
	p->SrandBack();
	p->write();
	p->BubbleSort();
	p->write();
	printf("-------HeapSort--------\n");
	p->SrandBack();
	p->write();
	p->HeapSort();
	p->write();
	printf("-------QuickSort--------\n");
	p->SrandBack();
	p->write();
	p->QuickSort();
	p->write();
	printf("-------MergeSort--------\n");
	p->SrandBack();
	p->write();
	p->MergeSort();
	p->write();
	printf("-------RadixSort--------\n");
	p->SrandBack();
	p->write();
	p->RadixSort();
	p->write();
  return 0;

}