C语言 - 快速排序与归并排序

本篇文章将采用递归的方式来实现：

1.【快速排序】

2.【归并排序】

************************************************************************************************************************************

一：快速排序

1> 一次排序原理图，后续采用递归分别对两侧进行排序

?2> 源码

#include

#include

using namespace std;

int QuickSort1(int *a,int low,int high)

{

int pivotekey;

a[0] = a[low]; //数组的第一个数据放在前哨站中

pivotekey = a[low]; //数组的第一个数据作为排序的中心值/轴值

while (low < high)

{

while (low < high && a[high] >= pivotekey)

{

high--;

}

a[low] = a[high];

while (low < high && a[low] <= pivotekey)

{

low++;

}

a[high] = a[low]; //因为刚开始第一个节点的值，也就是前哨站中的值，在一趟结束之后要将其赋值给后来空出来的位置

}

a[low] = a[0];

return low;

}

void QuickSort(int *a,int high)

{

int pivotekey;

if (low < high)

{

pivotekey = QuickSort1(a,low,high);

QuickSort(a,pivotekey - 1);

QuickSort(a,pivotekey + 1,high);

}

}

int main()

{

int a[31];

for (int i = 1; i < 31; i++)

{

a[i] = rand() % 100;

}

cout << "***" << endl;

QuickSort(a,1,30);

for (int i = 1; i < 31; i++)

{

cout << a[i] << " ";

}

cout << "***" << endl;

return 0;

}

二：归并排序

1> 源码（二路归并递归实现）

#include

#include

using namespace std;

void Merge(int *p1,int *p2,int u,int v,int t)

{

int i,j,k;

for (i = u,j = v + 1,k = u; i <= v&&j <= t; k++)

{

if (p1[i] < p1[j])

{

p2[k] = p1[i];

i++;

}

else

{

p2[k] = p1[j];

j++;

}

}

while (i<=v)

{

p2[k++] = p1[i++];

}

while (j <= t)

{

p2[k++] = p1[j++];

}

}

void MSort(int *p1,int *p3,int start,int end)

{

int middle;

int p2[30] = { 0 };

if (start == end)

{

p3[start] = p1[start];

}

else

{

middle = (start + end) / 2;

MSort(p1,p2,start,middle);

MSort(p1,middle+1,end);

Merge(p2,p3,middle,end);

}

}

int main()

{

int a[30] = { 0 };

srand(unsigned(time(NULL)));

for (int i = 0; i < 30; i++)

{

a[i] = rand() % 1000;

}

int b[30] = {0};

MSort(a,b,29);

for (int i = 0; i < 30; i++)

{

cout << b[i] << " ";

}

cout << endl;

return 0;

}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!