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

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

介绍

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

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

一般有以下方法

(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;
}
相关文章
|
12天前
|
搜索推荐
【数据结构常见七大排序(三)上】—交换排序篇【冒泡排序】And【快速排序】
【数据结构常见七大排序(三)上】—交换排序篇【冒泡排序】And【快速排序】
【数据结构常见七大排序(三)上】—交换排序篇【冒泡排序】And【快速排序】
|
12天前
|
搜索推荐
【数据结构常见七大排序(二)】—选择排序篇【直接选择排序】And【堆排序】
【数据结构常见七大排序(二)】—选择排序篇【直接选择排序】And【堆排序】
|
12天前
|
搜索推荐 测试技术
【数据结构常见七大排序(一)】—插入排序篇【直接插入排序】And【希尔排序】
【数据结构常见七大排序(一)】—插入排序篇【直接插入排序】And【希尔排序】
|
1月前
|
搜索推荐 算法
【排序】数据结构——排序算法概念及代码详解(插入、冒泡、快速、希尔)
【排序】数据结构——排序算法概念及代码详解(插入、冒泡、快速、希尔)
|
27天前
|
算法 Java 调度
Java数据结构与算法:拓扑排序
Java数据结构与算法:拓扑排序
|
28天前
|
算法 C语言
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
|
4天前
|
存储 前端开发 DataX
【数据结构】栈和队列
数据结构中的栈和队列
10 1
【数据结构】栈和队列
|
4天前
【数据结构OJ题】用栈实现队列
力扣题目——用栈实现队列
10 0
【数据结构OJ题】用栈实现队列
|
4天前
【数据结构OJ题】用队列实现栈
力扣题目——用队列实现栈
15 0
【数据结构OJ题】用队列实现栈
|
22天前
|
存储 缓存 算法
堆和栈的区别及应用场景
堆和栈的区别及应用场景