算法分析实验4分治法排序

【一】实验目的（小四黑体）

1．采用分治法实现序列排序；

2．理解分治法的思想。

【二】实验内容（小四黑体）

1．采用分治排序算法对序列排序；

2．编程实现合并排序和快速排序；

3．分析比较2种算法的时间复杂度；

【三】实验步骤（代码、结果）（小四黑体）

合并排序：

#include

#include

#include

void print(int a[],int n)

{

int i;

for(i=0; i{

printf(\"%d \

}

}

//分

void MergeSort(int a[],int start,int end)

{

if(start{

int mid=(start + end) / 2;

MergeSort(a,start,mid);

MergeSort(a,mid+1,end);

Merge(a,start,mid,end);

}

}

//合

void Merge(int a[], int start, int mid, int end)

{

//第一个数组长度

int n1 = mid - start + 1;

//第二个数组长度

int n2 = end - mid;

int left[n1], right[n2];

int i, j, k;

for (i = 0; i < n1; i++)

left[i] = a[start+i];

for (j = 0; j < n2; j++)

right[j] = a[mid+1+j];

i = j = 0;

k = start;

while (i < n1 && j < n2)

if (left[i] < right[j])

a[k++] = left[i++];

else

a[k++] = right[j++];

while (i < n1)

a[k++] = left[i++];

while (j < n2)

a[k++] = right[j++];

}

int main()

{

printf(\"学号：Z09315221，姓名：谭召\\n\");

int a[8] = { 5, 2, 4, 7, 1, 3, 2, 6 };

MergeSort(a,0,7);

printf(\"合并排序：\");

print(a,8);

return 0;

}

快速排序：

#include

#include

#include

void print(int a[],int n)

{

int i;

for(i=0; i{

printf(\"%d \

}

}

int Partition(int a[],int l,int r)

{

int p=a[l];

int i=l;

int j=r;

while(i{

while(ip) j--;

if(iwhile(iif(i}

a[i]=p;

return i;

}

void Quicksort(int a[],int l,int r)

{

if(l{

int s=Partition(a,l,r);

Quicksort(a,l,s-1);

Quicksort(a,s+1,r);

}

}

int main()

{

printf(\"学号：Z09315221，姓名：谭召\\n\");

int a[8] = { 5, 2, 4, 7, 1, 3, 2, 6 };

printf(\"快速排序：\");

Quicksort(a,0,7);

print(a,8);

return 0;

}

【四】实验结果分析（小四黑体）

合并排序的最好、最坏和平均时间复杂度都是O(nlogn)，而空间复杂度是O(n)，比较次数介于(nlogn)/2和(nlogn)-n+1，赋值操作的次数是(2nlogn)。因此可以看出，合并排序算法比较占用内存，但却是效率高且稳定的排序算法。而快速排序的平均时间复杂度为O(nlogn)，最糟糕时复杂度为O(n^2),但是快速排序算法不稳定。