数据结构第六课 -------迭代排序(快速排序和归并排序)

简介: 数据结构第六课 -------迭代排序(快速排序和归并排序)

介绍

在上一篇博客中,我们使用快速排序的时候是使用递归的方式进行的,如上图所示,

但是如果我们把递归变成非递归的形式,该怎么进行呢

一般有以下方法

(1)循环 (2)借助栈

可以结合这个图进行非递归进行

这个思路图,这个图只是简单的介绍了0 ~4的栈的入栈和出栈情况

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)
  {
    TackcapacityAdd(pst);
    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--;
}
//空间扩容
void TackcapacityAdd(SLtack* pst)
{
  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;
}

需要借助一个数组tmp


归并排序的非递归

从归并排序的递归思路来,主要就是合并的思想,如果我们要把非递归的思路模拟递归的思路,就要明白归并的合并怎么开始

image.png

可以看出

思路:我们合并的开始是一个元素开始,第二次合并是两个元素,第三次就是4个,直到合并的长度变成了整个数组的长度,就结束

我们在两两合并的时候就是有可能会碰见落单的小数组,我们可以让其和合并过的前一个进行合并组成一个新合并的数组,

#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;
}
相关文章
|
2月前
|
算法 搜索推荐 Shell
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
24 1
|
2月前
|
算法 搜索推荐 Java
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
基数排序是一种稳定的排序算法,通过将数字按位数切割并分配到不同的桶中,以空间换时间的方式实现快速排序,但占用内存较大,不适合含有负数的数组。
28 0
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
|
2月前
|
存储 搜索推荐 算法
【用Java学习数据结构系列】七大排序要悄咪咪的学(直接插入,希尔,归并,选择,堆排,冒泡,快排)以及计数排序(非比较排序)
【用Java学习数据结构系列】七大排序要悄咪咪的学(直接插入,希尔,归并,选择,堆排,冒泡,快排)以及计数排序(非比较排序)
26 1
|
2月前
【初阶数据结构】打破递归束缚:掌握非递归版快速排序与归并排序
【初阶数据结构】打破递归束缚:掌握非递归版快速排序与归并排序
|
2月前
|
算法
蓝桥杯宝藏排序 | 数据结构 | 快速排序 归并排序
蓝桥杯宝藏排序 | 数据结构 | 快速排序 归并排序
|
27天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
123 9
|
18天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
23 1
|
6天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
28 5
|
21天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
24天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。