Bubble Sort

每次考虑相邻两个元素，若前者大于后者，则交换两个元素的顺序，从而实现大的数往后走，从而实现从小到大的冒泡排序

void bubble(int arr[],int n)
		{
			int i,t,temp;
			for(i=n-1;i>0;i--)
			{
				for(t=0;t<i;t++)
				{
					if(arr[t]>arr[t+1])     //判断
					temp=arr[t];
					arr[t]=arr[t+1];
					arr[t+1]=temp;
				}
			}
		}

不难看出Bubble Sorting在最理想的情况下（即只有最大的元素一开始在一号位），需要进行一次冒泡操作即可完成整个排序，这时候时间复杂度为O(n)；最糟糕的情况下为O(n^2);平均也为O(n^2).

看得出来，适用于较小的数据排序，毕竟这玩意儿写得快也写得简单嘛

Inserting Sort

给定的一列数据，不妨分为两组，前一组是有序的，后一组是无序的，这两个组都是动态的，大小一直在变化，我们取出后组的第一个数据，从前组的最后一个元素开始，依次比较，直到前组的某个元素小于取出的这个元素为止，此时将这个取出的元素放在这个前组元素之后，即插入了一个数据到前组，从而完成排序。

void insert(int arr[],int n)
	 	{
	 		int i,t,k;
	 		for(i=1;i<n;i++)
	 		{
	 			k=arr[i];               //取出乱序的第一个元素
	 			t=i-1;                  
	 			while(t>=0&&arr[t]>k)   //从有序的最大元素开始比较
	 			{
	 				arr[t+1]=arr[t];    //把有序的元素向后移动
	 				t--;
	 			}
	 			arr[t+1]=k;             //插入
	 		}
	 	}

时间复杂度与冒泡相同

Selection Sort

和Inserting Sort类似，同样把数据假设分为两个组，从后组的第2个元素开始往后遍历，一旦这个元素大于后组第一个元素，则两个元素交换，从而把后组里最小的元素放在前组的最后面

void select(int arr[],int n)
	 	{
	 		int i,t;
	 		for(i=0;i<n-1;i++)
	 		for(t=i+1;t<n;t++)
	 		if(arr[t]<arr[i])
	 		swap(arr[t],arr[i]);
	 	}

时间复杂度很稳定的O(n^2)

Merge Sort

最典型的分治思想，先考虑这样一个问题，两个有序的数组，要合并为一个有序数组，可以用两个指针分别从头开始，如果第一个数组中的元素小于第二个数组，则第一个指针后移，否则第二个指针后移，直到一个指针到尾部，再把剩下的元素全部放入，即可完成排序。问题则转化为如何把一个数组分为两个有序的数组。

最显然的方式就是把这个数组二分，然后分别对两个小数组进行处理（二分到最后，必然全是单元素的数组，自然是有序的），由此递归处理。

void merge_combine(int arr[],int left,int mid,int right)
	  	{
	  		int *arr2=new int [right-left+1];  //创建一个和要排序的长度等长的数组
	  		int i=left;                         //标记起点
	  		int t=mid+1;                        //标记后半段的起点
	  		int k=0;                            //标记新数组的顺序
	  		
	  		while(i<=mid&&t<=right)
	  		{
	  			if(arr[i]<arr[t])
	  			arr2[k++]=arr[i++];             //把两段中较小者放入新数组
	  			else
	  			arr2[k++]=arr[t++];
	  		}
	  		
	  		while(i<=mid)
	  		arr2[k++]=arr[i++];                 //把剩下没放入的数都放入
	  		while(t<=right)
	  		arr2[k++]=arr[t++];
	  		
	  		for(i=left;i<=right;i++)            
                                                 //用新数组覆盖传入的数组，从而实现局部的排序
	  		arr[i]=arr2[i-left];
	  		
	  		delete arr2;                        //删除新数组的空间
	  	}
	  	
	  	void merge_sort(int arr[],int left,int right)
	  	{
	  		if(left<right)                        //如果数组还能二分，就继续二分
	  		{
	  			int mid;
	  			mid=(right+left)/2;
	  			merge_sort(arr,left,mid);        //对二分的第一个数组进行排序
	  			merge_sort(arr,mid+1,right);     //对二分的第二个数组进行排序
	  			merge_combine(arr,left,mid,right); //对排序好的子数组进行合并
	  		}
	  	}

归并的时间复杂度是O(nlogn) 递推关系为T(n)=2*T(n/2)+n

空间复杂度为O(n)

Quick Sort

快速排序是二分的思想；我们随机从数组中选择一个数，然后把比这个数小的放在这个数的左边，把比这个数大的放在这个数的右边，这样就完成了这一个数的排序，再递归的排序剩下的两部分，从而完成整体的排序。(如果有一个数位置错了，那不然有另一个数位置也不对)

void quicksort(int arr[],int begin,int end)
	 	{
	 		int i=begin;                        //标记左起点
	 		int j=end;                          //标记右起点
	 		if(i>=j)                            //如果就一个数那就返回
	 		return;
	 		int temp=arr[i];                    //标杆选择数组的第一个元素
	 		while(i!=j)
	 		{
	 			while(arr[j]>=temp&&j>i)        //找到右边一个小于标杆的数
	 			{
	 				j--;
	 			}
	 			while(arr[i]<=temp&&i<j)        //找到左边一个小于标杆的数
	 			{
	 				i++;
	 			}
	 			swap(arr[i],arr[j]);            //把两个站错的数字交换位置
	 		}
	 		swap(arr[i],arr[begin]);            //把标杆的位置放进去
	 		quicksort(arr,begin,i);             //对左边的区间继续排序
	 		quicksort(arr,i+1,end);             //对右边的区间继续排序
	 	}

快排如果每次都能恰好二分的话，时间复杂度能达到最理想的$O(nlogn)$，但是遇到最惨的时候，就会退化为O(n^2)，故快排主要是学二分的思想。