内部排序(一)

最近在实验室恰逢师兄师姐们的校招季，会有很多面试笔试题考一些基本的算法，其中较为常用的就是排序算法，当然这里指的仅仅是内部排序，处于复习的目的，回顾了一下在大二时候学习的一些排序方法，算是一个记录

 

内部排序大概来说有10种，分别是，选择排序，冒泡排序，插入排序，归并排序，冒泡排序，基数排序，堆排序，桶排序，计数排序，布尔排序，今天主要说一说最常用的前面五种算法，也是面试或者笔试中较为常用的

 

话不多少，代码奉上，基本的说明都在注释里面交代了

/*
Author:luchi
Date:2015/10/22
*/
#include<iostream>
using namespace std;

void printResult(int* a,int n,char* type){
	cout<<type<<":  ";
	for(int i=0;i<n;i++){
		cout<<a[i]<<" ";
	}
	cout<<endl;
}

/*Choose sorting
直接排序比较简单，扫描N-1趟，每趟选取一个最小的 
*/


void ChooseSorting(int *a ,int n) {
	
	for(int i=0;i<n-1;i++){
		
		for(int j=i+1;j<n;j++){
			if(a[j]<a[i]){
				int temp=a[i];
				a[i]=a[j];
				a[j]=temp;
				
			}
		}
		
	}
}


/*BubbleSort
冒泡排序是交换排序N-1趟，每一趟把最大的转到最后面 

*/




void BubbleSort(int*a,int n) {
	
	for(int i=1;i<=n-1;i++) {
		
		for(int j=0;j<=n-i-1;j++){
			
			if(a[j]>a[j+1]){
				int temp=a[j];
				a[j]=a[j+1];
				a[j+1]=temp;
			}
		}
	}
	
	
}

/*
InsertionSort 
*/ 
void InsertionSort(int* a,int n){
	
	for(int i=1;i<n;i++){
		
		int cur=a[i];
		
		int j;
		for(j=i-1;j>=0;j--){
			
			if(a[j]>cur)	{
				a[j+1]=a[j];
			}else break;
		}
		a[j+1]=cur;
	}
	printResult(a,10,"InsertionSort");
}

/*MergeSort
递归排序，讲一个数组分成两个部分，对这两个部分的数据进行排序，然后将两部分的
（此时已经是有序的）进行Merge操作，也就是重新合并成一个有序的数组

T(n)=2T(n/2)+O(n) 

递推可以知道时间复杂是Lg(n)*n 

*/

void Merge(int * a,int begin,int mid,int end){
	
	int *b=new int[end-begin+1];
	int left_begin=begin;
	int left_end=mid;
	int right_begin=mid+1;
	int right_end=end;
	int  pos=0;
	while(left_begin<=left_end && right_begin<=right_end){
		if(a[left_begin]<a[right_begin]){
			b[pos++]=a[left_begin];
			left_begin++;
		}else{
			b[pos++]=a[right_begin];
			right_begin++;
		}
	}
	if(left_begin>left_end){
		for(int i=right_begin;i<=right_end;i++){
			b[pos++]=a[i];
		}
	}else{
		for(int i=left_begin;i<=left_end;i++){
			b[pos++]=a[i];
		}
	}
	for(int i=begin;i<=end;i++){
		a[i]=b[i-begin];
	}
}
void MergeSort(int * a,int begin,int end){
	
	if(begin==end)return;
	int mid=(begin+end)/2;
	MergeSort(a,0,mid);
	MergeSort(a,mid+1,end);
	Merge(a,begin,mid,end);
	
}

/*quick_sort
快速排序属于较为重要的排序
基本思想就是对于一个数字，首先以第一个元素组为基准，
比他小的放在左边，比他大的放在右边
然后分别对左右两边再进行以上操作即可 
*/

void quickSort(int*a,int begin,int end){
	

	if(begin>=end)return;
	int seperator=a[begin];
	int count=0;
	for(int i=begin+1;i<=end;i++){
		if(a[i]<seperator){
			
			int temp=a[count+begin+1];
			a[count+begin+1]=a[i];
			a[i]=temp;
			count++;
			
		}
	}
	int temp=a[begin];
	a[begin]=a[begin+count];
	a[begin+count]=temp;
	quickSort(a,begin,begin+count-1);
	quickSort(a,begin+count+1,end);
}


int main(){
	int a[]={10,2,11,102,34,29,123,76,2,-7};
//	ChooseSorting(a,10);
//	BubbleSort(a,10);
//	InsertionSort(a,10);
//	MergeSort(a,0,9);
	quickSort(a,0,9);
	printResult(a,10,"QuickSort");
	return 0;
}

 今晚已经有点晚了，后面五种排序过些日子再弄出来