前言
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]));
}
效果如下：
