各种排序的原理

1.选择排序：

  首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换；

  再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换；

  重复上述操作，共进行n-1趟排序后，排序结束。

void Selesort(int *Array,int n)
{
     int i,j,k,tmp;
	 for(i=0;i<n-1;i++)
	 {
		 k=i;
		 for(j=i+1;j<n;j++)
			 if(Array[j]<Array[k]) k=j;
		 if(i!=k)
		 {
			 tmp=Array[i];
			 Array[i]=Array[k];
			 Array[k]=tmp;
		 }
	 }
}

2.快速排序：

快速排序是对冒泡排序的一种改进，其原理是分治法。

设要排的数组是a[0],a[1],...a[n-1],首先任选取一个数据，通常选取第一个数据作为关键数据，然后将所有比它小的

数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。

一趟快速排序的算法是：

(1)设置两个变量i,j，排序开始的时候：i=0，j=n-1

(2)以第一个数据作为关键数据赋值给key，即key=a[0]

(3)从j开始向前搜索，即由后开始向前搜索(j=j-1),找到第一个小于key的值a[j],并与a[i]交换

(4)从i开始向后搜索，即由前向后搜索(i=i+1),找到第一个大于key的值a[i],与a[j]交换

(5)重复(3)(4)(5)步，直到i=j;

void QuickSort(int *Array,int x,int y)
{
	int key=Array[x];
	int i=x,j=y;
	if(i>=j) return;
	while(i<j)
	{
	    while(i<j&&a[j]>=key) j--;
		Array[i]=Array[j];
		while(i<j&&Array[i]<=key) i++;
		Array[j]=Array[i];
	}
	Array[j]=key;
	QuickSort(Array,x,j-1);
	QuickSort(Array,j+1,y);
}

3.归并排序：
　　　

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子

序列是有序的。然后再把有序子序列合并为整体有序序列。归并操作的工作原理如下：

第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置

第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

重复步骤3直到某一指针达到序列尾，将另一序列剩下的所有元素直接复制到合并序列尾

// 原数组Array，临时空间数组tmp
void merge(int low,int mid,int high)
{
    int i=low,j=mid+1,k=low;
    while(i<=mid&&j<=high)
    {
        //此处为排序顺序的关键，用小于表示从小到大排序
        if(Array[i]<=Array[j]) tmp[k++]=Array[i++];
        else                   tmp[k++]=Array[j++];
    }
    while(i<=mid)  tmp[k++]=Array[i++];
    while(j<=high) tmp[k++]=Array[j++];
    for(i=low;i<=high;i++)   //写回原数组
        Array[i]=tmp[i];
}

/**全部排序的调用为mergeSort(0,4) */
void mergeSort(int a,int b) 
{
    if(a<b)
    {
         int mid=(a+b)/2;
         mergeSort(a,mid);
         mergeSort(mid+1,b);
         merge(a,mid,b);
    }
}