初探几种排序算法

                                                                                     多种排序算法的总结(不包括复杂度的详细推算）

稳定排序与不稳定排序

   稳定排序：相同元素在排序中的相对位置不改变。

   不稳定排序：相同元素在排序中的相对位置改变。

内部排序与外部排序：

内部排序：待排的记录与内容都放在计算机的随机存储器中进行的排序过程

外部排序：一般指待排序记录的数量很大，以致内存中一次不能完全容纳全部的记录，在排序过程中，需要对外存进行访问的排序过程。

排序算法的复杂度：

      在此我们一般只要考虑的就是时间复杂度，当然个别排序的空间复杂度也很大，如希尔排序。这里时间复杂度的计算方法和一般复杂度计算方法类似。

按照排序的过程中所依据的不同可以分类为：

插入排序，交换排序，选择排序，归并排序，基数排序，二叉排序树排序

       插入排序：

                 利用有序表的插入操作进行排序

                 有序表的插入：将一个记录插入到已经安排好的有序表中，从而得到一个新的有序表。

                直接插入排序算法主要应用比较和移动两种操作。

void insertsort(int R[],int n){
	int i,j,temp;
	for(i=1;i<n;i++)
	{
		temp=R[i];
		j=i-1;
		while((j>=0)&&(temp<R[j]))
		{
			R[j+1]=r[j];
			j--;
		}
		R[j+1]=temp;//put single on first
	}</span>

希尔排序（有一种直接插入排序的改进）

 方法：先将待排序列分割成为若干的子序列分别进行直接插入排序；待整个序列中的记录基本有序后，在进行一次直接插入排序。

希尔排序的时间复杂度：

       O（nlog2n)和O（N平方）之间大约O（N的1.3次方）

void shellsort(int a[],int arrsize)
{
	int temp;
	int gap=arrsize/2;
	while(gap != 0){
		for(int i=gap;i<arrsize;i++){
			temp=a[i];
			for(int j=i;j>=gap;j-=gap){
				if(temp < a[j-gap])
					a[j]=a[j-gap];
				else
					break;
			}
			a[j] = temp;
		}
		gap = (int)(gap/2);
	}
}</span>

交换排序--冒泡排序

思想：通过不断比较相邻元素的大小，进行交换实现排序

void bubblesort(int a[],int n)
{
	int flag = 1;
	for(i=1;i<n;i++)
	{
		flag=0;
		for(int j=n-1;j>=i;j--)
			if(R[j]<R[j-1])
			{
				t  = R[j];
				R[j]=R[j-1];
				R[j-1]=t;
				flag=1;
			}
		if(flag==0)
			return ;
	}
}</span>

交换排序--快速排序

冒泡排序的一种改进算法

    思想：以首记录作为轴记录，从前，后向扫描序列，通过交换，实现大值记录后移，小值记录前移，最终将轴记录安置在一个适当的位置（小值记录在前，大值记录在后）

轴记录将原序列分割成两个部分，依次对前后两部分重新设定轴记录，继而分别在进行快速排序。直至整个序列有序。

快速排序----分割过程

快速排序是一个分治的算法

对于一个序列，取它的一个元素作为轴，把所有小与轴的元素放在它的左边，大于它的元素放在它的右边

分割算法：

     用临时变量对轴进行备份

取链噶个指针LOW 和HING ，他们的初始值就是序列的两端小表，在整个过程中保证LOW 不大于HIGH

移动两个指针

首先从HING 所知的位置向左搜索，找到第一个小与轴的元素，把这个元素放在LOW 的位置

在从LOW开始向右，找到第一个大与轴的元素，把它放在HING 的位置

重复上述过程，直到LOW=HIGH

把轴放在LOW 所指的位置

这样所有大于轴的元素北方在右边，所有小与轴的元素被放在左边。

void Fquick_sort(int *addr,int low,int high)
{
	int lowpos = low;
	int highpos= high;
	int povite = addr[low];
	if(lowpos >= highpos){
		return ;
	}
	while(lowpos < highpos){
		while((lowpos < highpos)&&(add[highpos]>=povite)){
			highpos--;
		}
		if(lowpos < highpos){
			addr[lowpos] = addr[highpos];
			lowpos++;
		}
		while((lowpos < highpos)&&(addr[lowpos]<=povite)){
			lowpos++;
		}
		if(lowpos < highpos){
			addr[highpos]=addr[lowpos];
			highpos--;
		}
	}
	addr[lowpos]=povit;
	Fquick_sort(addr,low,lowpos-1);
	Fquick_sort(addr,lowpos+1,high);
	return ;
}</span>

时间复杂度：平均O（nlog2n)

空间复杂度：O（N平方）

快速排序是一种不稳定的排序方法

简单选择排序：

        每一趟都选出一个最大或最小的元素，并放在适当的位置。

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

归并排序：

         思想：将两个有序的序列合并成一个有序的序列，所以如果只有两个元素，所以归并排序就是将一个序列不停拆分，直到拆成一个一个元素为止，然后再进行合并排序。

void merge(int *add,int len)
{
	int lenA = 0,lenB = 0,lenC = 0,lentmp = 0;
	int *arrC = NULL;
	if(len <= 1){
		return ;
	}
	arrC = (int *)malloc(len*sizeof(int));
	lentmp = len/2;
	merge(add,lentmp);
	merge(&add[lentmp],len-lentmp);
	lenA = 0;lenB = lentmp;
	lenC = 0;
	while((lenA != lentmp)&&(lenB != len)){
		if(add[lenA]<add[lenB]){
			arrC[lenC] = add[lenA];
			lenA++;
		}else{
			arrC[lenC] = add[lenB];
			lenB++;
		}
		lenC++;
	}
	if(lenA == lentemp){
		while(lenB < len){
			arrC[lenC++]=add[lenB++];
		}
	}else if(lenB == len){
		while(lenA < lentmp){
			arrC[lenC++]=add[lenA++];
		}
	}else{
		//printf("all ok !\n");
	memcpy(add,arrC,len*sizeof(int));
	free(arrC);</span>