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

概述本文章向大家介绍C语言 - 快速排序与归并排序，主要包括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;

}

总结

以上是内存溢出为你收集整理的C语言 - 快速排序与归并排序全部内容，希望文章能够帮你解决C语言 - 快速排序与归并排序所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。