快速排序：
平均时间复杂度：O(n*lgn), 最坏 O(n*n)，辅助空间 O(n*lgn)，不稳定
归并排序：
平均时间复杂度：O(n*lgn), 最坏 O(n*lgn)，辅助空间 O(n)，稳定
快速排序：
快速排序采用了分治法的思想，把大的问题分解为同类型的小问题。一般分如下步骤：
( 1 )选择一个中枢元素(有很多选法，我的实现里使用第一个元素为中枢的简单方法)
( 2 )以该中枢元素为基准点，将小于中枢的元素放在中枢后集合的前部分，比它大的在集
合后部分，待集合基本排序完成后(此时前部分元素小于后部分元素 ) ，把中枢元素放在合
适的位置。
( 3 ) 根据中枢元素最后确定的位置 ， 把数组分成三部分 ， 左边的 ， 右边的 ， 枢纽元素自己 ，
对左边的，右边的分别递归调用快速排序算法即可。
void swap(int array[],int i, int j)
{
static int counter = 1;
int temp;
temp = *(array+i);
*(array+i) = *(array+j);
*(array+j) = temp;
printf("%d%s\n", counter++, "次交换后，数组是:");
for(int n=0; n<10; n++)
{
if( n == i || n == j )
{
printf("%s%d%s%s","(",array[n],")","");
}
else
{
printf("%d%s",array[n],"");
}
}
printf("\n\n");
}
int partition(int array[],int left, int right)
{
//把左右小于key值的元素放到左边，剩下的key右边的则全部大于key
//p
int
p=array[left];
//Put
elements < p to the left side
//Put
elements >= p to the right side
int
i=left,j=left+1;
for(j=left+1;j<=right;j++)
{
if(array[j]
{
i++;
swap(array,i,j);
}
}
//Put p in
the middle slot which index is pivot
swap(array,i,left);
return
i;
}
void quicksort(int array[], int left, int right)
{
//Do nothing
if left <= right
if(left
{
int pivot=partition(array,left,right);
//Recursive quicksort the left parts and right parts
quicksort(array,left,pivot-1);
quicksort(array,pivot+1,right);
}
}
void q_sort(int array[], int size)
{
quicksort(array, 0, size-1);
}
归并排序：
基本原理：归并排序分两步操作：第一步将数组分解成更小的数组，直到数组只有一
个元素为止 ， 每次划分点为 ( len – 1 ) /2=mid, 将数组分成 [from,mid] 和 [mid+1,to],
第二步就是
将分解的数组两两合并 ， 合并后的数组是有序的 ， 直到合并成一个数组为止 ， 合并过程中会
用到一个临时数组 ， 用来存储合并后的结果 。 每次合并后 ， 将数组的数据传给原数组对应的位置。
void Merge(int *arr,int low,int middle,int high)
{
int
i=low;//index for left side
int j=middle+1; //index for right side
int *tempArr;//temp array to store sorted array
int tempIndex = 0; //temp index for temp
array
int elementNum = high-low+1;
//给合并是的临时数组分配空间
tempArr = (int
*)malloc(elementNum*sizeof(int));
if(!tempArr)
{
return;
}
//此时middle两边(0到middle)和(middle+1到high)都是有序的
while( i<=middle
&& j<=high )
{
tempArr[tempIndex++] =
(arr[i]<=arr[j]) ? arr[i++] : arr[j++];
}
// 下面处理可能情况
// 1.middle的右边已经全部被添加了temparr，左边有剩余
while(i<=middle)
{
tempArr[tempIndex++] =
arr[i++];
}
// 2.middle及左边已经全部被添加了temparr，右边有剩余
while(j<=high)
{
tempArr[tempIndex++] =
arr[j++];
}
tempIndex = 0;
for(i=low;i<=high; i++)
{
arr[i]=tempArr[tempIndex++];
}
}
void MergeSort(int arr[],int low,int high)
{
int mid;
if(low
{
//取中间元素
mid=(low+high)/2;
//分为两部分 分别排序
MergeSort(arr,low,mid);
MergeSort(arr,mid+1,high);
//排序后合并
Merge(arr,low,mid,high);
}
}
测试：
int _tmain(int argc, _TCHAR* argv[])
{
int arr[10] =
{39,22,62,81,23,39,79,15,92,25};
//快速排序
//q_sort(arr, 10);
//归并排序
MergeSort(arr,0,9);
printf("%s\n","排序结果是： ");
for(int i=0; i<10; i++)
{
printf("%d%s",arr[i],"");
}
printf("\n\n\n");
return 0;
}
