【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析

本文涉及的产品
全局流量管理 GTM,标准版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
云解析 DNS,旗舰版 1个月
简介: 【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析

前言:

       接上篇,排序算法除了选择排序(希尔排序)和插入排序(堆排序)之外,还用交换排序(冒泡排序、快速排序)和归并排序已经非比较排序,本篇来深层解析这些排序算法

一、交换排序

       1.1、冒泡排序

       冒泡排序,这个再熟悉不过了,学校中老师讲的第一个排序就是冒泡排序;直接看代码

代码如下:

//冒泡排序
void BubbleSort(int* arr, int n)
{
  int exchange = 0;
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n - i - 1; j++)
    {
      if (arr[j] > arr[j + 1])
      {
        exchange = 1;
        Swap(&arr[j], &arr[j + 1]);
      }
    }
    if (exchange == 0)
    {
      break;
    }
  }
}

       时间复杂度:O(n^2);空间复杂度O(1)。

       1.2、快速排序

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

实现快速排序主要框架如下:

//快速排序
void QuickSort(int* a, int left, int right)
{
  if (left >= right) {
    return;
  }
  //_QuickSort⽤于按照基准值将区间[left,right)中的元素进⾏划分
  int meet = _QuickSort(a, left, right);
  QuickSort(a, left, meet - 1);
  QuickSort(a, meet + 1, right);
}

下面的不同方法指的是找基准值的方法不同而已。

1.2.1、hoare版本

思路:

       1.  创建左右指针,却基准值

       2.  从左到右找出比基准值大的数据,从右到左找出比基准值小的数据,左右指针数据交换,进入下一次循环

这里可能有一些问题,

       1.跳出循环后,right位置的值一定不大于key?

       当left > right时,即right走到了left的左侧,而left走过的位置值都不大于key,因此right此时指向的数据一定不大于key

       2.为什么left或者right指定的数据与key值相等也要交换?

       这里如果,数组中大量的数据都相等,不进行交换的话,就无法进行有效的分割数组。

代码实现:

//快速排序
int _QuickSort1(int* arr, int left, int right)
{
  int key = arr[left];
  int mid = left;
  left++;
  while (left <= right)
  {
    //左边找大
    while (left<=right && arr[left] < key)
    {
      left++;
    }
    //右边找小
    while (left <= right && arr[right] > key)
    {
      right--;
    }
    if (left <= right)
    {
      Swap(&arr[left], &arr[right]);
      left++;
      right--;
    }
  }
  Swap(&arr[mid], &arr[right]);
  return right;
}

1.2.2、挖坑法

思路:

       创建左右指针;首先从右向左找出比基准值小的数据,找到后立即放入左边 "坑" 中,当前位置变为新的 "坑",然后从左往右找出比基准值大的数据,找到后立即放入右边坑中,当前位置变为新的 "坑",结束循环后将最开始存储的分界值放入当前的 "坑"中,返回当前"坑"下标。

代码实现如下:

int _QuickSort2(int* arr, int left, int right)
{
  int tmp = arr[left];
  int hole = left;
  left++;
  while (left < right)
  {
    //从右边开始找
    while (left < right && arr[right] > tmp)
    {
      right--;
    }
    arr[hole] = arr[right];
    hole = right;
    while (left < right && arr[left] < tmp)
    {
      left++;
    }
    arr[hole] = arr[left];
    hole = left;
  }
  arr[hole] = tmp;
  return hole;
}

1.2.3、lomuto指针法

思路:

       创建前后指针,从左往右找比基准值小的进行交换,使得小的都排在基准值的左边。

代码实现:

int _QuickSort(int* arr, int left, int right)
{
  int prev = left, pcur = left + 1;
  int key = left;
  while (pcur <= right)
  {
    if (arr[pcur] < arr[key] && ++prev != pcur)
    {
      Swap(&arr[prev], &arr[pcur]);
    }
    pcur++;
  }
  Swap(&arr[key], &arr[prev]);
  return prev;
}

二、归并排序

思路:

       归并排序,是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个典型的应用。将已有序的子序列合并,得到完全有序的序列;即先让每一个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路合并。

代码实现:

//归并排序
void _MergeSort(int* arr, int left, int right,int* tmp)
{
  if (left >= right)
  {
    return;
  }
 
  int mid = (left + right) / 2;
  _MergeSort(arr, left, mid, tmp);
  _MergeSort(arr, mid+1, right, tmp);
 
 
  //合并数组
  int begin1 = left, end1 = mid;
  int begin2 = mid + 1, end2 = right;
  int index = left;
  while (begin1 <= end1 && begin2 <= end2)
  {
    if (arr[begin1] < arr[begin2])
    {
      tmp[index++] = arr[begin1++];
    }
    else {
      tmp[index++] = arr[begin2++];
    }
  }
  while (begin1 <= end1)
  {
    tmp[index++] = arr[begin1++];
  }
  while (begin2 <= end2)
  {
    tmp[index++] = arr[begin2++];
  }
  //将tmp数据拷贝回arr中
  for (int i = left; i <= right; i++)
  {
    arr[i] = tmp[i];
  }
}
void MergeSort(int* arr, int n)
{
  int* tmp = (int*)malloc(sizeof(int) * n);
 
  _MergeSort(arr, 0, n - 1, tmp);
 
  free(tmp);
}

三、非比较排序

非比较排序,就是不进行比较数据来进行排序。

       计数排序

1>  统计相同元素出现次数

2>  根据统计的结果将序列回收到原来的序列中

这里又会存在一些问题,比如如果数据是负数,那该怎样开辟空间?

       这里,我们开辟空间大小为数组数据最大值和最小值之差。

然后在将统计结果返回到原来数组当中时,让数组下标加上原数组最小值即可。

//计数排序
void CountSort(int* arr, int n)
{
  int max = arr[0];
  int min = arr[0];
  for (int i = 0; i < n; i++)
  {
    if (arr[i] > max)
    {
      max = arr[i];
    }
    if (arr[i] < min)
    {
      min = arr[i];
    }
  }
 
  //开辟空间
  int range = max - min + 1;
  int* tmp = (int*)calloc(sizeof(int),range);
  if (tmp == NULL)
  {
    perror("calloc fail");
    return;
  }
 
  for (int i = 0; i < n; i++)
  {
    tmp[arr[i] - min]++;
  }
  int j = 0;
  for (int i = 0; i < range; i++)
  {
    while (tmp[i]--)
    {
      arr[j++] = i + min;
    }
  }
}

各种排序算法的算法复杂度和稳定性分析

到这里,排序算法就结束了,希望你能有所收获

感谢各位大佬支持并指出问题,

                       如果本篇内容对你有帮助,可以一键三连支持以下,感谢支持!!!

相关文章
|
23天前
|
算法 前端开发 数据处理
小白学python-深入解析一位字符判定算法
小白学python-深入解析一位字符判定算法
44 0
|
16天前
|
存储 算法 Java
解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用
在Java中,Set接口以其独特的“无重复”特性脱颖而出。本文通过解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用。
35 3
|
18天前
|
搜索推荐 算法
插入排序算法的平均时间复杂度解析
【10月更文挑战第12天】 插入排序是一种简单直观的排序算法,通过不断将未排序元素插入到已排序部分的合适位置来完成排序。其平均时间复杂度为$O(n^2)$,适用于小规模或部分有序的数据。尽管效率不高,但在特定场景下仍具优势。
|
1天前
|
缓存 负载均衡 算法
Linux内核中的进程调度算法解析####
本文深入探讨了Linux操作系统核心组件之一——进程调度器,着重分析了其采用的CFS(完全公平调度器)算法。不同于传统摘要对研究背景、方法、结果和结论的概述,本文摘要将直接揭示CFS算法的核心优势及其在现代多核处理器环境下如何实现高效、公平的资源分配,同时简要提及该算法如何优化系统响应时间和吞吐量,为读者快速构建对Linux进程调度机制的认知框架。 ####
|
10天前
|
搜索推荐
冒泡排序算法
【10月更文挑战第19天】冒泡排序是一种基础的排序算法,虽然在实际应用中可能不是最优的选择,但对于理解排序算法的基本原理和过程具有重要意义。
|
24天前
|
机器学习/深度学习 算法 PyTorch
Pytorch-RMSprop算法解析
关注B站【肆十二】,观看更多实战教学视频。本期介绍深度学习中的RMSprop优化算法,通过调整每个参数的学习率来优化模型训练。示例代码使用PyTorch实现,详细解析了RMSprop的参数及其作用。适合初学者了解和实践。
33 1
|
24天前
|
算法 搜索推荐 Shell
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
15 1
|
24天前
|
算法 搜索推荐
数据结构与算法学习十一:冒泡排序、选择排序、插入排序
本文介绍了冒泡排序、选择排序和插入排序三种基础排序算法的原理、实现代码和测试结果。
14 0
数据结构与算法学习十一:冒泡排序、选择排序、插入排序
|
28天前
|
搜索推荐
冒泡排序(Bubble Sort)以及选择排序(Selection Sort)和快速排序(Quick Sort)详细解析
冒泡排序(Bubble Sort)以及选择排序(Selection Sort)和快速排序(Quick Sort)详细解析
13 1
|
18天前
|
前端开发 算法 JavaScript
无界SaaS模式深度解析:算力算法、链接力、数据确权制度
私域电商的无界SaaS模式涉及后端开发、前端开发、数据库设计、API接口、区块链技术、支付和身份验证系统等多个技术领域。本文通过简化框架和示例代码,指导如何将核心功能转化为技术实现,涵盖用户管理、企业店铺管理、数据流量管理等关键环节。

推荐镜像

更多