数据结构之排序【冒泡排序和快速排序之一的实现及分析】内含动态演示图

简介: 数据结构之排序【冒泡排序和快速排序之一的实现及分析】内含动态演示图

引言:

今天分享一下一点小事迹,自从从学校回到家里,我已经好久没睡上一个好觉了,因为真的冷,莫名被窝总是感觉很冷,然后穿着袜袜的脚也是冰凉,所以每次早晨要起床的时候总是感觉非常的冷,更牛的是我昨天直接被冷醒了,可能是因为学校的床没有那么大,所以不容易把热量散发掉,所以每次在学校都睡的非常的香,所以今天我决定睡在地板上(当然是床和衣柜之间的地板),这样我就可以实现小床睡觉了(明天的这个时候,准时汇报具体睡觉情况),并且现在是北京时间 2022/12/25/22:25 ,我还有一篇期末论文没有写,我毅然决然的选择先搞定这个,其它的再说吧!

天大寒,砚冰坚,手指不可屈伸,码字还是不易,所以引言就这样吧!今天我们学习一下冒泡排序和快速排序,当然重点是快速排序(冒泡排序效率低,所以我们学一下思想就行)


1.冒泡排序

for循环和while循环代码实现并且进行它们之间的比较对比

动图演示:

28.gif像排序这种类型的东西,以后我们可以不要直接来就靠我们的记忆去写,可以先按照基本原理来

比如,此时我们就是想要把一个数组中的最大的那个数放到数组的最后一个位置处,应该怎样写,

怎样通过多躺来控制单趟,怎样控制次数和边界

然后此时的这个for循环代表多躺,用来控制我的单趟(所以我的单趟是思想,多躺是和单趟相似的)


void BubbleSort(int* arr, int n)
{
  int j;
  for (j = 0; j < n - 1; j++)
  {
    int exchange = 0;
    int i;
    for (i = 0; i < n - 1 - j; i++)//遍历
    {
      if (arr[i] > arr[i + 1])//每个数比较,大的数往后走
      {
        Swap(&arr[i], &arr[i + 1]);
        exchange = 1;
      }
    }
    if (exchange == 0)//此时就是防止数组已经是有序的,然后还进行比较,所以我们为了防止,就可以这样写,交换了就不满足这个条件,就正常比较,没有交换就满足这个条件,就跳出循环
    {
      break;
    }
  }
}

所以只要是有思想代码怎么写都是可以的,单趟(目的:为了让最大值到达数组的最后一个位置)

多躺:控制单趟和边界的处理

void BubbleSort(int* arr, int n)
{
  int end = n;
  while (end > 0)
  {
    int i;
    for (i = 0; i < n - 1; i++)
    {
      if (arr[i] > arr[i + 1])
      {
        Swap(&arr[i], &arr[i + 1]);
      }
    }
    //写完单趟,然后我为了控制次数,可以用上述的for循环,也可以直接用while循环,只要把比较的次数给控制好了,怎样写都行
    end--;//反正就是n次而已
  }
}

所以总的来说对比两种循环,多躺就是用来控制单趟的边界的(就是控制什么时候要继续,什么时候停下来,然后循环几次之类的问题)


2.重点:快速排序

2.1 快速排序(方法很多(主要涉及递归和非递归),复杂)

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


将区间按照基准值划分为左右两半部分的常见方式有: 1.挖坑法


上述的原理:1. 第一步就是要找一个key(关键值),6 5 1 2 7 9 3 4 10 8 => 此时就把arr[0]作为我的key(也就是把这个key作为一个pivot(坑)),然后把比key大的放在key的右边,比key小的放在key的左边


2.2 挖坑法的具体原理:我们把arr[0]的值给拿走了,此时key处就是一个坑(就是空位置的意思) ,


然后我就去遍历key右边的数组元素,比较,把比key小的数给放到arr[0]位置处,然后把我们刚刚找


到的那个比key小的元素的位置重新赋值为坑(因为此时这个元素已经是没用的了,这个位置就可以


相当于是空),然后再去遍历key左边的数组元素,把key左边比key大的数放到新的坑的位置,然后


把刚刚key左边找到比key大的元素的位置重新赋值为坑,然后重复这个步骤,此时我就实现单趟排序


把比key大的放在key的右边,比key小的放在key的左边,并且将key放在正确的位置处 => 5 1 2 4 3


6 9 7 10 8 变成这样就是我的单趟的目的 (虽然说是单趟但是实际是一个循环),只是后面还会涉


及到递归而已


具体动图演示:


image.gif然后我们以下面的图示来进行进一步的理解:


30.png


33.png


34.png

右边按照同样的操作进行,即可把排序完成(即我的分治递归)

2.3 代码实现(注释详解每一步)

//void QuickSort(int* arr, int n)
//为了使用我的分治递归现在我的这个函数的作用就不单单是一个值了,是一段数组中的值,所以就不可以按照上面这样写,应该要写成下面的形式
void QuickSort(int* arr, int left, int right)
{
  if (left >= right)//递归的停止条件(就是当我的区间只有一个值或不存在)大于表示只有一个值,等于表示区间不存在
  {
    return;
  }
  //int begin = 0;//就是最左边的意思
  //int end = n - 1;//就是最右边的意思
  //此时为了实现分治递归,我们就要把上面的begin和end写成下面的这个样子
  int begin = left;
  int end = right;
  int pivot = begin;//按照原理,此时的这个pivot可以给最左边的位置或者最右边的位置
  int key = arr[begin];//按照原理,此时的这个pivot可以给最左边的位置或者最右边的位置
  while (begin < end)//因为待会会进行begin++ end--的操作,所以当它们相等之后,我就已经实现了把比key大的放在key的右边,比key小的放在key的左边,所以只要begin!=end 这个循环就要继续
  {
    //右边找小,放到左边(在key的右边找,自然是从最右边开始)
    while (begin < end && arr[end] >= key)
    {
      end--;
    }
    //程序来到这里说明我找到比key小的元素了(然后此时按照原理:就是把找到的这个值放到key的pivot位置,然后重新把这个找到的元素的位置赋值成pivot(便于待会把左边的元素放过来))
    arr[pivot] = arr[end];
    pivot = end;
    //此时我的左边的坑被右边的元素占据了,所以现在就要在左边找比key大的数据放到右边的坑中,然后左边再形成一个坑
    while (begin < end && arr[begin] <= key)
    {
      begin++;
    }
    //程序来到这个位置说明我找到比key大的元素了,然后把它放到右边的坑中就行,顺便把自己原来的位置重新赋值为坑,使左边又有一个新的坑,便于待会后面比key小的值放进来
    arr[pivot] = arr[begin];
    pivot = begin;
  }
  //此时程序来到这个位置就是说明:begin和end相遇了(此时就可以把我的key的位置直接放到最后的这个pivot中)
  pivot = begin;//此时就是找最后一个坑的位置
  arr[pivot] = key;//然后把key放到这个坑里面去
  //此时这边我们为了可以使用我的分治递归,按照原理就是要把这个数组分成三部分:
  //[left,right]
  //                                                [pivot]
  //                                                   |                                     
  //[left,pivot-1][pivot][pivot+1,right] =>  5 1 2 4 3 6 9 7 10 8
  //因为此时只要左子区间有序了,右子区间有序了,我的整个数组就有序了,所以此时就是把左子区间和右子区间都拿去递归就行了
  QuickSort(arr, left, pivot - 1);
  QuickSort(arr, pivot + 1, right);
}

3.快排测试

35.png


相关文章
|
1月前
|
算法 搜索推荐 Shell
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
20 1
|
1月前
|
算法 搜索推荐 Java
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
基数排序是一种稳定的排序算法,通过将数字按位数切割并分配到不同的桶中,以空间换时间的方式实现快速排序,但占用内存较大,不适合含有负数的数组。
23 0
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
|
1月前
|
算法 搜索推荐
数据结构与算法学习十一:冒泡排序、选择排序、插入排序
本文介绍了冒泡排序、选择排序和插入排序三种基础排序算法的原理、实现代码和测试结果。
17 0
数据结构与算法学习十一:冒泡排序、选择排序、插入排序
|
1月前
|
存储 搜索推荐 算法
【用Java学习数据结构系列】七大排序要悄咪咪的学(直接插入,希尔,归并,选择,堆排,冒泡,快排)以及计数排序(非比较排序)
【用Java学习数据结构系列】七大排序要悄咪咪的学(直接插入,希尔,归并,选择,堆排,冒泡,快排)以及计数排序(非比较排序)
22 1
|
1月前
|
算法
蓝桥杯宝藏排序 | 数据结构 | 快速排序 归并排序
蓝桥杯宝藏排序 | 数据结构 | 快速排序 归并排序
|
16天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
90 9
|
7天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
15 1
|
9天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
12天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
14天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
42 4