插入排序Insert Sort

简介

Image from geeksforgeeks

在数组中，将无序部分依次插入有序部分，得到一个有序数组。

代码如下：

#include <iostream>
#include <vector>

using namespace std;

void InsertSort(vector<int>& nums){
	int len=nums.size();
	if(len==0 || len==1) return;
	int key=0;
	int j=0;
	for(int i=1;i<len;i++){
		key=nums[i];
		j=i;
		while((j>=1) && (nums[j-1]>key)){
			nums[j]=nums[j-1];
			j--;
		}
		nums[j]=key;
	}
}

int main(){
	int tmp;
	vector<int> arr;
	cout<<"Please type the array you wat to sort:"<<endl;
	while(cin>>tmp){
		arr.push_back(tmp);
	}
	InsertSort(arr);
	for(auto& x:arr){
		cout<<x<<" ";
	}
	return 0;
}

为了更好地了解排序的过程，在实现过程中可以添加一些排序过程，输出排序中数组的值。

void InsertSort(vector<int>& nums){
	int len=nums.size();
	if(len==0||len==1) return;
	int tmp=0;
	for(int i=1;i<len;i++){
		tmp=nums[i];
		int j=i;
		cout<<endl;
		cout<<"The "<<i<<"th round:"<<endl;
		while( (j>=1) && (tmp<nums[j-1]) ){
			nums[j]=nums[j-1];
			j--;
			for(auto& x:nums){
				cout<<x<<" ";
			}
			cout<<endl;
		}
		nums[j]=tmp;
		for(auto& x:nums){
			cout<<x<<" ";
		}
		cout<<endl;
		cout<<endl;
	}
}

比如我们输入1 5 2 4 3， 结果如下：

Please type the array you wat to sort:
1 5 2 4 3 ^X

The 1 round:
1 5 2 4 3


The 2 round:
1 5 5 4 3
1 2 5 4 3


The 3 round:
1 2 5 5 3
1 2 4 5 3


The 4 round:
1 2 4 5 5
1 2 4 4 5
1 2 3 4 5

Final anwers:
1 2 3 4 5

归并排序 Merge Sort

简介

Image from geeksforgeeks

“每次遇见了不会的排序时，一定不是自己脑子太笨了，肯定是规模太大了”——Prof.zly

归并排序采用分治思想，每次近乎二分，规模太大递归继续分，当只剩一个数时，就很容易比较，后递归合并结果。整个过程可以看作是递归搜索树的后序遍历过程。

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;


void merge(vector<int>& nums, int l, int m, int r){
	int len1=m-l+1, len2=r-m;
	vector<int> arr1(len1);
	vector<int> arr2(len2);
	int i=0,j=0;
	for(i=0;i<len1;i++){
		arr1[i]=nums[l+i];
	}
	for(j=0;j<len2;j++){
		arr2[j]=nums[m+1+j];
	}
	i=0;
	j=0;
	int len=r-l+1;
	int k=l;
	
	while(i<len1 && j<len2){
		if(arr1[i]<arr2[j]){
			nums[k]=arr1[i];
			i++;
		}
		else{
			nums[k]=arr2[j];
			j++;
		}
		k++;
	}
	
	while(i<len1){
		nums[k]=arr1[i];
		i++;
		k++;
	}
	while(j<len2){
		nums[k]=arr2[j];
		j++;
		k++;
	}
}

void mergesort(vector<int>& nums,int l,int r){//l->left, r-> right
	if(l>=r){
		return;
	}
	int m=floor((l+r)/2);//m-> middle
	mergesort(nums,l,m);
	mergesort(nums,m+1,r);
	merge(nums,l,m,r);
}

int main(){
	vector<int> arr;
	int tmp=0;
	cout<<"Please input the array you want to sort:"<<endl;
	while(cin>>tmp){
		arr.push_back(tmp);
	}	
	mergesort(arr,0,arr.size()-1);
	for(auto& x:arr){
		cout<<x<<" ";
	}
	return 0;
}