在哪个网站可以做试卷,多作者wordpress插件,网站建设新报价图片欣赏,wordpress手机h5主题文章目录 前言一、快速排序非递归二、归并排序五、归并排序非递归总结 前言
C语言数据结构快速排序的非递归、归并排序、归并排序的非递归等的介绍 一、快速排序非递归
快速排序非递归的定义
快速排序非递归#xff0c;需要使用栈来实现。将左右下标分别push到栈中。在栈为… 文章目录 前言一、快速排序非递归二、归并排序五、归并排序非递归总结 前言
C语言数据结构快速排序的非递归、归并排序、归并排序的非递归等的介绍 一、快速排序非递归
快速排序非递归的定义
快速排序非递归需要使用栈来实现。将左右下标分别push到栈中。在栈为空之前循环获取区间的中间值下标并同时将左右区间排序。判断若中间值下标keyi 1小于end则将此区间push到栈中。若begin 小于 中间值下标keyi则将此区间push到栈中。循环直到栈为空。
int PartSort3(int* a, int left, int right)
{int keyi left;int prev left;int cur left 1;while (cur right){/*if (a[cur] key){prev;Swap(a[cur], a[prev]);}cur;*/if (a[cur] a[keyi] prev ! cur)Swap(a[cur], a[prev]);cur;}Swap(a[prev], a[keyi]);return prev;
}// 快速排序非递归
void QuickSortNonR(int* a, int left, int right)
{int* tmp (int*)malloc(sizeof(int) * (right - left 1));ST st;STInit(st);STPush(st, right);STPush(st, left);while (!STEmpty(st)){int begin STTop(st);STPop(st);int end STTop(st);STPop(st);int keyi PartSort3(a, begin, end);if (keyi 1 end){STPush(st, end);STPush(st, keyi - 1);}if (begin keyi - 1){STPush(st, keyi - 1);STPush(st, begin);}}STDestroy(st);
}其中PartSort3函数是快速排序快慢指针的单趟排序。 快速排序非递归测试
void TestQuickSortNonR()
{int a[] { 9, 7, 6 ,4 ,8 ,3 ,5 ,1 ,2, 0 };PrintArray(a, sizeof(a) / sizeof(a[0]));QuickSortNonR(a, 0, sizeof(a) / sizeof(a[0]) - 1);PrintArray(a, sizeof(a) / sizeof(a[0]));
}效果如下
二、归并排序
归并排序定义
直接将区间拆分成左右区间。左右区间分别递归直到单个数字并在返回后归并左右区间到一个临时的数组中。然后将临时数组中的数字memcpy拷贝到原数组中。
// 归并排序
void _MergeSort(int* a, int left, int right, int* tmp)
{if (left right)return;int midi left (right - left) / 2;int begin1 left, end1 midi;int begin2 midi 1, end2 right;_MergeSort(a, begin1, end1, tmp);_MergeSort(a, begin2, end2, tmp);int i left;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[i] a[begin1];}else{tmp[i] a[begin2];}}while (begin1 end1){tmp[i] a[begin1];}while (begin2 end2){tmp[i] a[begin2];}memcpy(a left, tmp left, sizeof(int) * (right - left 1));}void MergeSort(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(MergeSort malloc);return;}int left 0;int right n - 1;_MergeSort(a, left, right, tmp);free(tmp);
} 归并排序测试
void TestMergeSort()
{int a[] { 9, 7, 6 , 6, 4,4 ,8 ,3 ,5 ,1 ,2, 0, 5 };PrintArray(a, sizeof(a) / sizeof(a[0]));MergeSort(a, sizeof(a) / sizeof(a[0]));PrintArray(a, sizeof(a) / sizeof(a[0]));
}效果如下
五、归并排序非递归
归并排序非递归定义
归并一部分拷贝一部分
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);int gap 1;while (gap n){int i 0;for (i 0; i n; i 2 * gap){int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 1;if (end1 n || begin2 n){break;}if (end2 n){end2 n - 1;}int j i;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[j] a[begin1];}else{tmp[j] a[begin2];}}while (begin1 end1){tmp[j] a[begin1];}while (begin2 end2){tmp[j] a[begin2];}memcpy(a i, tmp i, sizeof(int) * (end2 - i 1));}gap * 2;}free(tmp);tmp NULL;
}归并排序非递归测试
void TestMergeSortNonR()
{int a[] { 9, 7, 6 , 6, 4,4 ,8 ,3 ,5 ,1 ,2, 0, 5 };PrintArray(a, sizeof(a) / sizeof(a[0]));MergeSortNonR(a, sizeof(a) / sizeof(a[0]));PrintArray(a, sizeof(a) / sizeof(a[0]));
}效果如下 总结
C语言数据结构快速排序的非递归、归并排序、归并排序的非递归等的介绍
