【C语言/数据结构】排序(快速排序及多种优化|递归及非递归版本)

简介: 【C语言/数据结构】排序(快速排序及多种优化|递归及非递归版本)

交换排序


快速排序

快排的过程图如下:



hoare版代码呈现

void QuickSort(int* a, int begin,int end)
{
  if (begin >= end)
  {
  return;
  }
  int left = begin, right =end;
  int keyi = begin;
  while (left < right)
  {
  //右边找小
  while (left < right && a[right] >= a[keyi])
  {
    right--;
  }
  //左边找大
  while (left < right && a[left] <= a[keyi])
  {
    left++;
  }
  Swap(&a[left], &a[right]);
  }
  Swap(&a[left], &a[keyi]);
  keyi = left;
  // [begin,keyi-1] keyi [keyi+1,end]
  QuickSort(a, begin, keyi - 1);
  QuickSort(a, keyi+1, end);
}


分析:快排过程就是左边找比key大的值,右边找比key小的值,找到后就交换。直到left与right相遇,就交换keyi和left对应的值。这是单趟的,后续过程重复,可以思考二叉树的递归过程,快排递归与其相似(见下图)。




下图中,划红线的地方是容易出错的地方。




理解了前面,这里解释一下为什么相遇位置比keyi位置的值要小?


因为右边先走。


相遇有2种情况


1. R遇L->R没有找到比key小,一直走,直到遇到L,相遇位置是L,比key小。

2.L遇R->R先走,找到小的停下来了,L找大,没有找到,遇到R停下来了,相遇位置是R,比key小。

如果左边做key,R先走。

如果右边做key,L先走。


快排优化

1.三数取中法选key

2.递归到小的子区间时,可以考虑使用插入排序

三数取中法

快排对于有序的数据,效率不是很高。



如上图,我们前面的快排是固定选key的,也就是左边第一幅图,效率很低。理想情况下,每一次都二分,这样效率就能提高。这时就用到三数取中法。


三数取中法指三个数里面取中间大小的数,然后将他与key交换位置,让这个中间大小的数作key。


完整代码如下:


int GetMidi(int* a, int begin, int end)
{
  int midi = (begin + end) / 2;
  //begin end midi三个数中选中位数
  if (a[begin] < a[midi])
  {
  if (a[midi] < a[end])
    return midi;
  else if (a[begin] > a[end])
    return begin;
  else
    return end;
  }
  else
  {
  if (a[midi] > a[end])
    return midi;
  else if (a[begin] < a[end])
    return begin;
  else
    return end;
  }
}
void QuickSort(int* a, int begin, int end)
{
  if (begin >= end)
  return;
  int midi = GetMidi(a, begin, end);
  Swap(&a[midi], &a[begin]);
  int left = begin, right = end;
  int keyi = begin;
  while (left < right)
  {
  //右边找小
  while (left < right && a[right] >= a[keyi])
  {
    right--;
  }
  //左边找大
  while (left < right && a[left] <= a[keyi])
  {
    left++;
  }
  Swap(&a[left], &a[right]);
  }
  Swap(&a[left], &a[keyi]);
  keyi = left;
  // [begin,keyi-1] keyi [keyi+1,end]
  QuickSort(a, begin, keyi - 1);
  QuickSort(a, keyi + 1, end);
}


小区间优化


假设在理想情况下,每次递归都像二叉树那样,递归到最后面几层时,假设还剩7个数,我们还得递归7次,这样明显不好。我们就可以在最后几层时,使用其他排序方法进行。这里使用插入排序。


完整代码如下:

void QuickSort(int* a, int begin, int end)
{
  if (begin >= end)
  return;
  if (end - begin + 1 <= 10)
  {
  InsertSort(a+begin, end - begin + 1);
  }
  else 
  {
  int midi = GetMidi(a, begin, end);
  Swap(&a[midi], &a[begin]);
  int left = begin, right = end;
  int keyi = begin;
  while (left < right)
  {
    //右边找小
    while (left < right && a[right] >= a[keyi])
    {
    right--;
    }
    //左边找大
    while (left < right && a[left] <= a[keyi])
    {
    left++;
    }
    Swap(&a[left], &a[right]);
  }
  Swap(&a[left], &a[keyi]);
  keyi = left;
  // [begin,keyi-1] keyi [keyi+1,end]
  QuickSort(a, begin, keyi - 1);
  QuickSort(a, keyi + 1, end);
  }
}


挖坑法


我们把不同方法的单趟排序重新弄成一个函数。


hoare版本:

//hoare版本 
int PartSort1(int* a, int begin, int end)
{
  int midi = GetMidi(a, begin, end);
  Swap(&a[midi], &a[begin]);
  int left = begin, right = end;
  int keyi = begin;
  while (left < right)
  {
  //右边找小
  while (left < right && a[right] >= a[keyi])
  {
    right--;
  }
  //左边找大
  while (left < right && a[left] <= a[keyi])
  {
    left++;
  }
  Swap(&a[left], &a[right]);
  }
  Swap(&a[left], &a[keyi]);
  return left;
}


挖坑法完整代码:


//挖坑法
int PartSort2(int* a, int begin, int end)
{
  int midi = GetMidi(a, begin, end);
  Swap(&a[midi], &a[begin]);
  int key = a[begin];
  int hole = begin;
  while (begin < end)
  {
  //右边找小,填到左边的坑
  while (begin < end && a[end] >= key)
  {
    end--;
  }
  a[hole] = a[end];
  hole = end;
  //左边找大,填到右边的坑
  while (begin < end && a[begin] <= key)
  {
    begin++;
  }
  a[hole] = a[begin];
  hole = begin;
  }
  a[hole] = key;
  return hole;
} 
void QuickSort(int* a, int begin, int end)
{
  if (begin >= end)
  return;
  int keyi = PartSort2(a, begin, end);
  QuickSort(a, begin, keyi - 1);
  QuickSort(a, keyi+1, end);
}

分析:挖坑法其实跟hoare版本比没啥提升,只不过更易理解,本质上没变。但不同的版本,单趟排序后的结果可能会不同。


前后指针版本



分析:


1.cur遇到比key大的值,cur++

2.cur遇到比key小的值,++prev,交换prev和cur位置的值,++cur

代码实现


//前后指针法
int PartSort3(int* a, int begin, int end)
{
  int midi = GetMidi(a, begin, end);
  Swap(&a[midi], &a[begin]);
  int keyi = begin;
  int prev = begin;
  int cur = prev + 1;
  while (cur <= end)
  {
  if (a[cur] < a[keyi] && ++prev!=cur)
    Swap(&a[prev], &a[cur]);
  ++cur;
  }
  Swap(&a[prev], &a[keyi]);
  keyi = prev;
  return keyi;
}


非递归版本快排

非递归版本的快排需要用到栈。下面给出需要的栈的函数:


void STInit(ST* pst)
{
  assert(pst);
  pst->a = NULL;
  pst->capacity = 0;
  pst->top = 0;
  //pst->top = -1;
}
void STDestroy(ST* pst)
{
  free(pst->a);
  pst->a = NULL;
  pst->capacity = pst->top = 0;
}
//栈顶插入删除
void STPush(ST* pst, STDataType x)
{
  assert(pst);
  if (pst->top == pst->capacity)
  {
  int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
  STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
  if (tmp == NULL)
  {
    perror("realloc fail");
    return;
  }
  pst->a = tmp;
  pst->capacity = newcapacity;
  }
  pst->a[pst->top] = x;
  pst->top++;
}
void STPop(ST* pst)
{
  assert(pst);
  assert(pst->top > 0);
  pst->top--;
}
STDataType STTop(ST* pst)
{
  assert(pst);
  assert(pst->top > 0);
  return  pst->a[pst->top - 1];
}
bool STEmpty(ST* pst)
{
  assert(pst);
  //if (pst->top == 0)
  //{
  //  return true;
  //}
  //else
  //{
  //  return  false;
  //}
  return pst->top == 0;
}


非递归代码实现:


void QuickSortNonR(int* a, int begin, int end)
{
  ST s;
  STInit(&s);
  STPush(&s, end);
  STPush(&s, begin);
  while (!STEmpty(&s))
  {
  int left = STTop(&s);
  STPop(&s);
  int right = STTop(&s);
  STPop(&s);
  int keyi = PartSort3(a, left, right);
  // [left,keyi-1] keyi [keyi+1,right]
 
  if (keyi+1 < right)
  {
    STPush(&s, right);
    STPush(&s, keyi+1);
  }
  if (left < keyi - 1)
  {
    STPush(&s, keyi - 1);
    STPush(&s, left);
  }
  }
  STDestroy(&s);
}



分析:栈是后进先出,这里用栈是模拟递归的过程。先模拟递归左边,像二叉树递归那样,先入右边的数,再入左边,这样出的时候就先出左边的,然后就可以模拟先往左边递归了。


目录
相关文章
|
17天前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
28 1
|
25天前
|
存储 算法 搜索推荐
【趣学C语言和数据结构100例】91-95
本文涵盖多个经典算法问题的C语言实现,包括堆排序、归并排序、从长整型变量中提取偶数位数、工人信息排序及无向图是否为树的判断。通过这些问题,读者可以深入了解排序算法、数据处理方法和图论基础知识,提升编程能力和算法理解。
41 4
|
25天前
|
存储 机器学习/深度学习 搜索推荐
【趣学C语言和数据结构100例】86-90
本文介绍并用C语言实现了五种经典排序算法:直接插入排序、折半插入排序、冒泡排序、快速排序和简单选择排序。每种算法都有其特点和适用场景,如直接插入排序适合小规模或基本有序的数据,快速排序则适用于大规模数据集,具有较高的效率。通过学习这些算法,读者可以加深对数据结构和算法设计的理解,提升解决实际问题的能力。
38 4
|
25天前
|
存储 算法 数据处理
【趣学C语言和数据结构100例】81-85
本文介绍了五个经典算法问题及其C语言实现,涵盖图论与树结构的基础知识。包括使用BFS求解单源最短路径、统计有向图中入度或出度为0的点数、统计无向无权图各顶点的度、折半查找及二叉排序树的查找。这些算法不仅理论意义重大,且在实际应用中极为广泛,有助于提升编程能力和数据结构理解。
35 4
|
25天前
|
算法 数据可视化 数据建模
【趣学C语言和数据结构100例】76-80
本文介绍了五种图论算法的C语言实现,涵盖二叉树的层次遍历及广度优先搜索(BFS)和深度优先搜索(DFS)的邻接表与邻接矩阵实现。层次遍历使用队列按层访问二叉树节点;BFS利用队列从源节点逐层遍历图节点,适用于最短路径等问题;DFS通过递归或栈深入图的分支,适合拓扑排序等场景。这些算法是数据结构和算法学习的基础,对提升编程能力和解决实际问题至关重要。
40 4
|
18天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
41 5
|
17天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
43 1
|
14天前
|
存储 C语言 开发者
【C语言】字符串操作函数详解
这些字符串操作函数在C语言中提供了强大的功能,帮助开发者有效地处理字符串数据。通过对每个函数的详细讲解、示例代码和表格说明,可以更好地理解如何使用这些函数进行各种字符串操作。如果在实际编程中遇到特定的字符串处理需求,可以参考这些函数和示例,灵活运用。
34 10
|
14天前
|
存储 程序员 C语言
【C语言】文件操作函数详解
C语言提供了一组标准库函数来处理文件操作,这些函数定义在 `<stdio.h>` 头文件中。文件操作包括文件的打开、读写、关闭以及文件属性的查询等。以下是常用文件操作函数的详细讲解,包括函数原型、参数说明、返回值说明、示例代码和表格汇总。
34 9
|
14天前
|
存储 Unix Serverless
【C语言】常用函数汇总表
本文总结了C语言中常用的函数,涵盖输入/输出、字符串操作、内存管理、数学运算、时间处理、文件操作及布尔类型等多个方面。每类函数均以表格形式列出其功能和使用示例,便于快速查阅和学习。通过综合示例代码,展示了这些函数的实际应用,帮助读者更好地理解和掌握C语言的基本功能和标准库函数的使用方法。感谢阅读,希望对你有所帮助!
29 8