【非递归】手搓快速排序

简介: 【非递归】手搓快速排序

前言:

快速排序已经带大家实现过了,我们用到的方法是递归法,你知道吗,用循环也可以实现快速排序,来看看吧。

注:

这篇博客属于数据结构内容,建议学习完C语言的小伙伴食用~


目录

🐯1.快排回顾

🦁2.非递归思想

🐮3.实现



1.快排回顾


还记得递归版的快速排序是怎么实现的吗?

默认使用前后指针法:

7963524f7152b42094d3fadd784ad9cc_e606e402b8844ad38d7003d3f314f27b.gif

代码实现:

//快排(前后指针法)
void QuickSort3(int* a, int left, int right)
{
  if (left >= right)
    return;
  //三数取中
  int midi = GetMidi(a, left, right);
  if (midi != left)
      Swap(&a[midi], &a[left]);
  int keyi = left;
  int key = a[left];
  int prev = left;
  int cur = left + 1;
  while (cur <= right)
  {
    if (a[cur] < key && ++prev != cur)
      Swap(&a[cur], &a[prev]);
    cur++;
  }
  Swap(&a[keyi], &a[prev]);//与下标为keyi的交换
  keyi = prev;
  //递归
  QuickSort3(a, left, keyi - 1);
  QuickSort3(a, keyi + 1, right);
}

在代码末尾进行了递归操作,那么非递归如何实现呢?


2.非递归思想


要想用非递归实现排序,我们首先要观察递归是如何实现的:

不变的是一趟中数字的交换逻辑,

变化的是需要进行 调整的区间

我们从变化的入手:

20522d165e4e678506bff0b4c6cabede_ce1b38db58dd4ed18dbf439eeeb198f7.png

可以看到,调整的区间在变化(紫色标号);

也就是说,我们可以在循环中 存储要调整的区间 ,用到时再取出来;

这个有先入后出的特点,可以选择栈来实现。

那么如何模拟返回条件呢?

递归版是一个数字的时候就返回,那么非递归版就可以是子区间有一个值或者没有值就不把区间入栈。


思路总结:

里面取一段区间,单趟排序;

• 单趟分割子区间入栈;

• 子区间只有一个值或者不存在就不入栈


3.实现


void QuickSortNotR(int* a, int left, int right)
{
  Stack ST;
  StackInit(&ST);
  StackPush(&ST, right); // 先入右,再入左,才能先出左,再出右。
  StackPush(&ST, left);
  while (!StackEmpty(&ST))
  {
        // 取出区间
    int begin = StackTop(&ST);
    StackPop(&ST);
    int end = StackTop(&ST);
    StackPop(&ST);
        // PartSort3返回是快速排序的keyi值
    int keyi = PartSort3(a, begin, end);
    //[begin,keyi-1] keyi [keyi+1,end]
        //满足非一零就出栈
    if (keyi + 1 < end)
    {
      StackPush(&ST, end);
      StackPush(&ST, keyi + 1);
    }
    if (begin < keyi - 1)
    {
      StackPush(&ST, keyi - 1);
      StackPush(&ST, begin);
    }
  }
  StackDestroy(&ST);
}

总结:

这篇博客内容比较简单,就是仿照递归版本实现了非递归的快速排序。

目录
相关文章
|
6月前
|
搜索推荐
手撕各种排序(中)
手撕各种排序(中)
65 0
|
6月前
|
安全 Java C语言
手撕各种排序(上)
手撕各种排序
50 0
|
6月前
|
算法 搜索推荐 索引
手撕各种排序(下)
手撕各种排序(下)
59 0
|
11月前
|
搜索推荐 算法
手撕排序算法4:归并排序及其非递归版本(下)
手撕排序算法4:归并排序及其非递归版本(下)
|
11月前
|
搜索推荐 算法
手撕排序算法4:归并排序及其非递归版本(上)
手撕排序算法4:归并排序及其非递归版本(上)
|
11月前
|
搜索推荐 算法 C语言
手撕排序算法5:快速排序非递归版本和计数排序
手撕排序算法5:快速排序非递归版本和计数排序
|
11月前
|
搜索推荐 算法
手撕排序算法2:堆排序和直接选择排序(下)
手撕排序算法2:堆排序和直接选择排序(下)
|
11月前
|
算法 搜索推荐 测试技术
手撕排序算法2:堆排序和直接选择排序(上)
手撕排序算法2:堆排序和直接选择排序(上)
|
算法 搜索推荐
【数据结构】手撕归并排序(含非递归)
【数据结构】手撕归并排序(含非递归)
56 0
|
算法 搜索推荐
【数据结构与算法篇】手撕八大排序算法之交换排序
【数据结构与算法篇】手撕八大排序算法之交换排序
79 0