【数据结构】手撕八大排序算法(下)

简介: 2.6快速排序:快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,

2.6快速排序:

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。

快速排序有三种写法:

1.hoare版本

2.挖坑法

3.前后指针法

以及优化:

1.三数取中

2.6.1hoare版本(递归版本)

动图演示:

hoare版本思路:

单趟排序,key一般选最左边或者最右边

当key为最左边,右边找小,左边找大,然后交换继续,相遇停止,相遇的值跟key交换

当key为最右边相反

当左区间有序,右区间有序那整体就ok了,如果左右区间不有序,左右区间就是单趟的子问题

当区间只有一个值,就不排了,返回

问题:为什么是key为最左边时,右边先走,最右边做key时,左边先走

answer:左边做key,右边先走,可以保证相遇位置比key要小

此时有两种情况:

1.相遇,left是停着(一定>=key),right向后走,相遇的位置是left的位置

2.相遇,right是停着(一定<=key),left向前走,相遇的位置是right的位置

单趟有两个意义

1.分割出左右区间,左比key小,右比key大

2.key到了正确位置(排序后的最终位置)

key以后不用变了,到了正确位置

代码:

int Partsort1(int* a, int begin, int end)
{//hoare版本
  int mid = GetMidIndex(a, begin, end);
  Swap(&a[mid], &a[begin]);
  int left = begin;
  int 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;
  return keyi;
}
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 keyi=Partsort1(a, begin, end);
    //int keyi=Partsort2(a, begin, end);
    //int keyi = Partsort3(a, begin, end);
    QuickSort(a, begin, keyi - 1);
    QuickSort(a, keyi + 1, end);
  }
}

时间复杂度:O(NlogN)

2.6.2三数取中

每次排序都会将数组分为三个部分:

【left-key-1】【key】【keyi+1-right】

在理想情况下,我们每次进行完单趟排序后,key的左序列与右序列的长度都相同:

若每趟排序所选的key都正好是该序列的中间值,即单趟排序结束后key位于序列正中间,那么快速排序的时间复杂度就是O(NlogN)。

但事实上可能会遇到极端情况:就是我们每次取到的都是最大值或者最小值,那么快排的时间复杂度达到最低O(N^2)

可以看到,这种情况下,快速排序的时间复杂度退化为O(N^2)。其实,对快速排序效率影响最大的就是选取的key,若选取的key越接近中间位置,则则效率越高。

为了避免这种极端情况的发生,于是出现了三数取中:

 三数取中,当中的三数指的是:最左边的数、最右边的数以及中间位置的数。三数取中就是取这三个数当中,值的大小居中的那个数作为该趟排序的key。这就确保了我们所选取的数不会是序列中的最大或是最小值了。

代码:

int GetMidIndex(int* a, int begin, int end)
{
  int mid = (begin + end) / 2;
  if (a[begin] < a[mid])
  {
    if (a[mid] < a[end])
    {
      return mid;
    }
    else if (a[begin] > a[end])//a[mid]>a[end]的前提下
    {
      return begin;
    }
    else//a[mid]>a[end]&&a[begin] < a[end]的前提下
    {
      return end;
    }
  }
  else//a[begin] > a[mid]
  {
    if (a[end] < a[mid])
    {
      return mid;
    }
    else if (a[begin] > a[end])//a[end] > a[mid]
    {
      return end;
    }
    else//a[end] > a[mid]&&a[begin] < a[end]
    {
      return begin;
    }
  }
}

2.6.3挖坑法

动图演示:

思路:

将一开始的left保存起来,然后左边 空出来一个坑,右边先走,右找大,然后将右边的值的数据填进去,找到的位为坑,左边找小将右边的坑填进去,最后一定会在坑的位置相遇

代码:

int Partsort2(int* a, int begin, int end)
{//挖坑法
  int mid = GetMidIndex(a, begin, end);
  Swap(&a[mid], &a[begin]);
  int left = begin;
  int right = end;
  int keyi = a[left];
  int hole = left;
  while (left < right)
  {
    while (left < right && a[right] >= keyi)
    {
      right--;
    }
    a[hole] = a[right];
    hole = right;
    while (left < right && a[left] <= keyi)
    {
      left++;
    }
      a[hole]=a[left];
    hole = left;
  }
  a[hole] = keyi;
  keyi = left;
  return hole;
}
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 keyi=Partsort1(a, begin, end);
    int keyi=Partsort2(a, begin, end);
    //int keyi = Partsort3(a, begin, end);
    QuickSort(a, begin, keyi - 1);
    QuickSort(a, keyi + 1, end);
  }
}

时间复杂度:O(NlogN)


2.6.4前后指针法:

动图演示:

思路:

1、cur找比key小,找到后停下来
2、++prev, 交换prev位置和cur位置的值

代码:

int Partsort3(int* a, int begin, int end)
{
  int  prev = begin;
  int cur = begin + 1;
  int keyi = begin;
  while (cur<=end)
  {
    /*if (a[cur] < a[keyi])
    {
      Swap(&a[++prev], &a[cur]);
    }*/
    if (a[cur] < a[keyi]&&++prev!=cur)
    {
      Swap(&a[prev], &a[cur]);
    }
    cur++;
  }
  Swap(&a[prev], &a[keyi]);
  keyi = prev;
  return keyi;
}
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 keyi=Partsort1(a, begin, end);
    int keyi=Partsort2(a, begin, end);*/
    int keyi = Partsort3(a, begin, end);
    QuickSort(a, begin, keyi - 1);
    QuickSort(a, keyi + 1, end);
  }
}

时间复杂度:O(NlogN)


2.6.5非递归写法:

思路:

通过非递归的方式实现递归的情况的话,递归从底层是先排左边再排右边因此类推,因此写非递归我们从顶层到底层就需要反过来。

借助栈的内存结构让先入的后出,所以要先压begin再压end,取出来的话就是先出右再出左

再先排右边再排左边。

代码:

void QuickSortNonR(int* a, int begin, int end)
{//非递归
  ST st;
  StackInit(&st);
  StackPush(&st, begin);
  StackPush(&st, end);
  while (!StackEmpty(&st))
  {
    int right = StackTop(&st);
    StackPop(&st);
    int left = StackTop(&st);
    StackPop(&st);
    int keyi = Partsort3(a, left, right);//单趟排序
    if (keyi + 1 < right)
    {
      StackPush(&st, keyi+1);
      StackPush(&st, right);
    }
    if (left < keyi-1)
    {
      StackPush(&st, left);
      StackPush(&st, keyi - 1);
    }
  }
  StackDestory(&st);
}

2.7归并排序

2.7.1递归写法:

动图讲解:

思路:

将两端有序序列取各种较小的值比较排序成一个有序序列。

代码:

void _MergeSort(int* a, int begin, int end, int* tmp)
{
  if (begin >= end)
  {
    return;
  }
  int mid = (begin + end) / 2;
  _MergeSort(a, mid+1, end, tmp);
  _MergeSort(a, begin, mid, tmp);
  int begin1 = begin;
  int end1 = mid;
  int begin2 = mid+1;
  int end2 = end;
  int i = begin;
  while (begin1<=end1&&begin2<=end2)
  {
    if (a[begin1] < a[begin2])
    {
      tmp[i++] = a[begin1++];
    }
    else
    {
      tmp[i++] = a[begin2++];
    }
  }
  while (begin1 <= end1)
  {
    tmp[i++] = a[begin1++];
  }
  while (begin2 <= end2)
  {
    tmp[i++] = a[begin2++];
  }
  memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
void MergeSort(int* a, int n)
{
  int* tmp = (int*)malloc(sizeof(int) * n);
  if (tmp == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  _MergeSort(a, 0, n-1, tmp);
  free(tmp);
  tmp = NULL;
}
3.

2.7.2非递归写法:

极端情况:

越界有三种情况

1.end1越界 begin2越界end2越界

2.begin2越界end2越界

3.end2越界

整体拷贝的话会有覆盖丢失

代码:

void MergeSortNonrR(int* a, int n)
{
  int* tmp = (int*)malloc(sizeof(int) * n);
  if (tmp == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  int RangN = 1;
  while (RangN < n)
  {
    for (int i = 0; i < n; i += 2 * RangN)
    {
      int begin1 = i;
      int end1 = i + RangN - 1;
      int begin2 = i + RangN;
      int end2 = i + 2 * RangN - 1;
      int j = i;
      if (end1>=n)// 修正区间  ->拷贝数据 归并完了整体拷贝 or 归并每组拷贝
      {
        end1 = n - 1;
        begin2 = n;// 不存在区间
        end2 = n - 1;
      }
      else if (begin2 >= n)
      {
        begin2 = n;
        end2 = n - 1;
      }
      else if(end2>=n)
      {
        end2 = n - 1;
      }
      while (begin1 <= end1 && begin2 <= end2)
      {
        if (a[begin1] < a[begin2])
        {
          tmp[j++] = a[begin1++];
        }
        else
        {
          tmp[j++] = a[begin2++];
        }
      }
      while (begin1 <= end1)
      {
        tmp[j++] = a[begin1++];
      }
      while (begin2 <= end2)
      {
        tmp[j++] = a[begin2++];
      }
      memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
    }
    RangN *= 2;
  }
  free(tmp);
  tmp = NULL;
}

时间复杂度:O(NlogN) 空间复杂度:O(N)

2.8计数排序

思路:

绝对映射:count数组中下标为i的位置记录的是arr数组中数字i出现的次数。
相对映射:count数组中下标为i的位置记录的是arr数组中数字min+i出现的次数。

代码:

void CountSort(int* a, int n)
{
  int min = a[0];
  int max = a[0];
  for (int i = 1; i < n; i++)
  {
    if (a[i] > max)
    {
      max = a[i];
    }
    if (a[i] < min)
    {
      min = a[i];
    }
  }
  int range = max - min + 1;
  int* CoutA = (int*)calloc(range, sizeof(int));
  if (CoutA == NULL)
  {
    perror("calloc fail");
    exit(-1);
  }
  for (int i = 0; i < n; i++)
  {
    CoutA[a[i] - min]++;
  }
  int k = 0;
  for (int i = 0; i < range; i++)
  {
    while (CoutA[i]--)
    {
      a[k++] = i + min;
    }
  }
  free(CoutA);
}

时间复杂度:O(N+range)      空间复杂度:O(range)

相关文章
|
3月前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
102 1
|
4月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
131 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
24天前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
83 29
|
24天前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
88 25
|
24天前
|
存储 人工智能 算法
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
64 23
|
1月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
54 2
|
3月前
|
存储 算法 搜索推荐
Python 中数据结构和算法的关系
数据结构是算法的载体,算法是对数据结构的操作和运用。它们共同构成了计算机程序的核心,对于提高程序的质量和性能具有至关重要的作用
115 33
|
3月前
|
数据采集 存储 算法
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化?
|
3月前
|
算法
数据结构之路由表查找算法(深度优先搜索和宽度优先搜索)
在网络通信中,路由表用于指导数据包的传输路径。本文介绍了两种常用的路由表查找算法——深度优先算法(DFS)和宽度优先算法(BFS)。DFS使用栈实现,适合路径问题;BFS使用队列,保证找到最短路径。两者均能有效查找路由信息,但适用场景不同,需根据具体需求选择。文中还提供了这两种算法的核心代码及测试结果,验证了算法的有效性。
155 23
|
3月前
|
算法
数据结构之蜜蜂算法
蜜蜂算法是一种受蜜蜂觅食行为启发的优化算法,通过模拟蜜蜂的群体智能来解决优化问题。本文介绍了蜜蜂算法的基本原理、数据结构设计、核心代码实现及算法优缺点。算法通过迭代更新蜜蜂位置,逐步优化适应度,最终找到问题的最优解。代码实现了单链表结构,用于管理蜜蜂节点,并通过适应度计算、节点移动等操作实现算法的核心功能。蜜蜂算法具有全局寻优能力强、参数设置简单等优点,但也存在对初始化参数敏感、计算复杂度高等缺点。
93 20