C语言数据结构快速排序的非递归、归并排序、归并排序的非递归、计数排序等的介绍

文章目录

• 前言
• 一、快速排序非递归
• 二、归并排序
• 三、归并排序非递归
• 四、计数排序
• 总结

前言

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]));
}

效果如下：

四、计数排序

计数排序定义

• 采用计数排序的相对映射。
• 先找到数据范围
• 根据数据范围开辟数组空间， 并全部初始化为0.
• 每个数据都相对映射到新数组的每个数据上，不断++。
• 最后将新数组的数据按照下标和值的关系写入原数组。

void CoutSort(int* a, int n)
{
// 找到范围
int max = a[0], min = a[0];
int i = 0;
for (i = 1; i < n; i++)
{
if (a[i] > max)
{
max = a[i];
}
if (a[i] < min)
{
min = a[i];
}
}
int range = max - min + 1;
// 开辟range个空间
int* Counta = (int*)malloc(sizeof(int*) * range);
if (Counta == NULL)
{
perror("CountSort calloc");
return;
}
memset(Counta, 0, sizeof(int)* range);
// 相对映射
for (i = 0; i < n; i++)
{
Counta[a[i] - min]++;
}
// 写入新数组
int j = 0;
for (i = 0; i < range; i++)
{
while (Counta[i]--)
{
a[j++] = i + min;
}
}
free(Counta);
Counta = NULL;
}

计数排序测试

void TestCoutSort()
{
int a[] = { 1, 3, 9, 6, 6, 3, 2, 4, 4, 5, 3, 2, 7, 8};
PrintArray(a, sizeof(a) / sizeof(a[0]));
CoutSort(a, sizeof(a) / sizeof(a[0]));
PrintArray(a, sizeof(a) / sizeof(a[0]));
}

效果如下：

总结

C语言数据结构快速排序的非递归、归并排序、归并排序的非递归、计数排序等的介绍