# 数据结构第六课 -------迭代排序（快速排序和归并排序）

## 介绍

(1)循环 (2)借助栈

typedef int TackDataType;
typedef struct SLtack
{
TackDataType* TData;
int Top;//标识栈顶位置
int Capacity;
}SLtack;
//初始化
void TackInit(SLtack* pst)
{
assert(pst);
pst->TData = NULL;
pst->Top = 0;//栈顶元素的下一个
pst->Capacity = 0;
}
//释放
void TackDestroy(SLtack* pst)
{
assert(pst);
free(pst->TData);
pst->TData = NULL;
pst->Top = 0;
pst->Capacity = 0;
}
//插入数据
void TackPushData(SLtack* pst, TackDataType elemest)
{
assert(pst);
//判断容量
if (pst->Capacity == pst->Top)
{
printf("扩容成功\n");

}
assert(pst->Capacity != pst->Top);
pst->TData[pst->Top] = elemest;
pst->Top++;

}
//删除数据
void TackPopData(SLtack* pst)
{
assert(pst);
if(pst->Top)
pst->Top--;
}
//空间扩容
{
assert(pst);
//扩容
pst->Capacity = (pst->Capacity == 0 ? 4 : pst->Capacity * 2);
TackDataType* tmp = realloc(pst->TData, sizeof(TackDataType) * pst->Capacity);
if (tmp == NULL)
{
perror("realloc");
return;
}
pst->TData = tmp;

}
//找出栈顶
TackDataType TackTop(SLtack* pst)
{
assert(pst);
return *(pst->TData + (pst->Top - 1));
}
//判断栈是否为空
bool Empty(SLtack* pst)
{
assert(pst);
return pst->Top == 0;
}

//栈的长度
int TackSize(SLtack* pst)
{
assert(pst);
return pst->Top;
}
int TriNum(int* a, int begin, int end)
{
int mid = (begin - end) / 2 + end;
if (begin > end)
{
if (end > mid)
{
return end;
}
else if (begin < mid)
{
return begin;
}
return mid;
}
else
{
if (begin > mid)
{
return begin;
}
else if (end < mid)
{
return end;
}
else
return mid;
}
}
void excheng(int* a, int* b)
{
int c = *a;
*a = *b;
*b = c;
}
int main()
{
srand(time(NULL));
int N = 100;
int* arr = (int*)malloc(sizeof(int) * N);
int i = 0;
for (i = 0; i < N; i++)
{
arr[i] = rand();
}
//创建一个栈
SLtack* tack = (SLtack*)malloc(sizeof(SLtack));
//初始化
TackInit(tack);
int begin = 0;
int end = N - 1;
//插入
TackPushData(tack, begin);
TackPushData(tack, end);
while (!Empty(tack))
{
//找出栈顶
TackDataType end1 = TackTop(tack);
//删除
TackPopData(tack);
//找出栈顶
TackDataType begin1 = TackTop(tack);
//删除
TackPopData(tack);
//快速排序
int key = TriNum(arr, begin1, end1);
excheng(&arr[key], &arr[(begin1)]);
key = begin1;
int prev = begin1;
int cur = begin1 + 1;
while (cur <= end1)
{
//cur 比较
if (arr[cur] < arr[key] && ++prev != cur)//增加++prev != cur可以有效解决相同位置进行交换
{
excheng(&arr[cur], &arr[prev]);
}
cur++;
}
excheng(&arr[key], &arr[prev]);
if (begin1 < prev - 1)
{
TackPushData(tack, begin1);
TackPushData(tack, prev - 1);
}
if (prev + 1 < end1)
{
TackPushData(tack, prev + 1);
TackPushData(tack, end1);
}
}
free(arr);
TackDestroy(tack);
return 0;
}


## 归并排序

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>
void _Mergesort(int* arr, int begin, int end, int *tmp)
{
if (begin >= end)
return;
//分割
int mid = (end + begin) / 2;
_Mergesort(arr, begin, mid, tmp);
_Mergesort(arr, mid + 1, end, tmp);
//合并
int cur1 = begin;
int cur2 = mid + 1;
int i = 0;
while (cur1 <= mid && cur2 <= end)
{
if (arr[cur1] >= arr[cur2])
{
tmp[i++] = arr[cur2++];
}
else
{
tmp[i++] = arr[cur1++];
}

}
if (cur1 > mid)
{
while (cur2 <= end)
{
tmp[i++] = arr[cur2++];
}
}
if (cur2 > end)
{
while (cur1 <= mid)
{
tmp[i++] = arr[cur1++];
}
}
memcpy(arr + begin, tmp, sizeof(int) * i);
}
void Mergesort(int* arr, int begin, int end)
{
//创建一个数组
int* tmp = (int*)malloc(sizeof(int) * (end - begin + 1));
if (tmp == NULL)
{
perror("malloc");
return;
}
_Mergesort(arr, begin, end, tmp);

free(tmp);
}
int main()
{
srand(time(NULL));
int N = 10000;
int* arr = (int*)malloc(sizeof(int) * N);
int i = 0;
for (i = 0; i < N; i++)
{
arr[i] = rand();
}
//归并排序
Mergesort(arr, 0, N - 1);
free(arr);
return 0;
}


## 归并排序的非递归

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>
void merge(int* arr, int begin1, int end1, int begin2, int end2,int *tmp)
{
//合并
int i = 0;
int x = begin1;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] >= arr[begin2])
{
tmp[i++] = arr[begin2++];
}
else
{
tmp[i++] = arr[begin1++];
}

}
if (begin1 > end1)
{
while (begin2 <= end2)
{
tmp[i++] = arr[begin2++];
}
}
if (begin2 > end2)
{
while (begin1 <= end1)
{
tmp[i++] = arr[begin1++];
}
}
memcpy(arr + x, tmp, sizeof(int) * i);
}
void _Mergesort(int* arr, int begin, int end, int *tmp)
{
int t = 1;//每次元素的个数
while (t <= (end + 1)/ 2)//遍历的次数
{
int i = 0;//代表开始的下标
//每次遍历一遍
while ((i + 2 * t -1)<= end)
{
merge(arr, i, i + t - 1, i + t, i+2 * t - 1, tmp);
i = i + 2 * t;
}
//判断是否还有部分没有合并
if (i <= end)
{
merge(arr, i - 2 * t, i - 1, i, end, tmp);
}
t *= 2;

}

}
void Mergesort(int* arr, int begin, int end)
{
//创建一个数组
int* tmp = (int*)malloc(sizeof(int) * (end - begin + 1));
if (tmp == NULL)
{
perror("malloc");
return;
}
_Mergesort(arr, begin, end, tmp);

free(tmp);
}
int main()
{
srand(time(NULL));
int N = 33;
int* arr = (int*)malloc(sizeof(int) * N);
int i = 0;
for (i = 0; i < N; i++)
{
arr[i] = rand();
}
int diyth[] = { 6,5,8,4,1,2,8,9,5 };
//归并排序
Mergesort(arr, 0, N - 1);
for (i = 0; i < N; i++)
{
printf("%d\n", arr[i]);
}
free(arr);
return 0;
}


|
12天前
|

【数据结构常见七大排序（三）上】—交换排序篇【冒泡排序】And【快速排序】
【数据结构常见七大排序（三）上】—交换排序篇【冒泡排序】And【快速排序】
11 1
|
12天前
|

【数据结构常见七大排序（二）】—选择排序篇【直接选择排序】And【堆排序】
【数据结构常见七大排序（二）】—选择排序篇【直接选择排序】And【堆排序】
8 1
|
12天前
|

【数据结构常见七大排序（一）】—插入排序篇【直接插入排序】And【希尔排序】
【数据结构常见七大排序（一）】—插入排序篇【直接插入排序】And【希尔排序】
11 1
|
1月前
|

【排序】数据结构——排序算法概念及代码详解（插入、冒泡、快速、希尔）
【排序】数据结构——排序算法概念及代码详解（插入、冒泡、快速、希尔）
22 1
|
27天前
|

Java数据结构与算法：拓扑排序
Java数据结构与算法：拓扑排序
14 0
|
28天前
|

【数据结构与算法 经典例题】使用栈实现队列（图文详解）
【数据结构与算法 经典例题】使用栈实现队列（图文详解）
34 0
|
4天前
|

【数据结构】栈和队列

10 1
|
4天前
【数据结构OJ题】用栈实现队列

10 0
|
4天前
【数据结构OJ题】用队列实现栈

15 0
|
22天前
|

26 2