排序总结(跑路人笔记2)

简介: 排序总结(跑路人笔记)

快速排序

快速排序整体的综合性能和使用场景都是比较好的,所以才敢叫快速排序

时间复杂度:O(N*logN)

空间复杂度:O(logN)

稳定性:不稳定

一个被大佬选择并加入到函数库的排序,属于是老棒老棒的排序了.


想讲述一下快速排序的思想吧.


快速排序是通过在数组中选出一个基准值(一般选第一个或最后一个)将基准值放在一个左边的数都比基准值小(大)右边的数都比基准数大(小)然后通过基准值又将数组分开成两个然后再进行上述操作.


例: 4 1 3 2 5 8 7 9 以4为基准值经过了一次快速排序后就可以将4放到1 3 2 4 5 8 7 9(注:不同实现方法的顺序是不同的博主的注重点是将4左边数比4小右边比数大的情况.)


这种排序主干有三种实现方法.分hoare版本 挖坑法 前后指针版本



hoare版本实现

思路就是上面的思路,我们先来通过hoare版本来实现一下.

int PartSort1(int* a, int left, int right)
{
  //整体思路是先让right先走找到一个比a[keyi]小的数然后等待left找到比a[keyi]大的数
  //然后交换即可.
  int keyi = left;//不能给零,因为每次递归的时候我们都要通过不同的left来操作.
  while (left < right)
  {
    if (a[right] < a[keyi])//先让right先走为了保证left和right听的位
    {
      while (left < right)
      {
        if (a[left] > a[keyi])
        {
          Swap(&a[left], &a[right]);
          break;//记得break因为我们要先right走.
        }
        left++;
      }
    }
    right--;
  }
  Swap(&a[left], &a[keyi]);//最后记得把keyi的换位完成
  return left;
}
void QuickSort(int* a, int left, int right)
{
  if (left > right)
  {
    return;
  }
  int keyi = PartSort1(a, left, right);
  QuickSort(a, left, keyi - 1);
  QuickSort(a, keyi + 1, right);
}

其中PartSort1是我们排序的主干部分,也就是一次排序的经过,然后下面的QuickSort这个函数就是为了给我们的PartSort1提供要排序的空间.


先简单的讲一下QuickSort函数吧,这个函数的作用是为了给PartSort1函数提供要排序的空间然后PartSort1返回基准值的下标我们的QuickSort函数再通过返回的基准值的下标再次将要排序的空间给PartSort1函数,然后PartSort1再进行排序.


可以看懂代码注释的不用看下面部分了


让我们讲一下PartSort1的实现思路吧:


1这个思路属于是有点难理解而且还有部分细节需要注意的,因为他是快排发明者的思路(大佬的思路懂得懂得=.=).


先让right先走(一定是right先走)直到right找到a[right] < a[keyi]的情况这样我们就让right停下让left来走寻找直到left找到a[left] > a[keyi]的情况找到后我们就可以交换left和right的值了,再让left停下让right走.一直这样循环直到left>=right就跳出循环.这时left和right相遇的位置就是我们需要将keyi安放的位置所以最后将keyi和left(或right)的值交换就好.


注意:上面必须right先走不然没法保证left和right相遇的位置可以安放keyi


如果害没理解下面我将用例子来讲解过程.


就用:4,1,5,2,3,7,6,9,8以keyi取左边值做例子.


image.png


这样我们的基准值(keyi对应的数组值)左边都是比它小的值了,右边都是比基准值大的值了.


然后通过递归不断的将基准值的左区间和右区间传给PartSort1这样不断更新基准值就可以得到一个有序的序列了.




挖坑法

上面的hoare法有一点难理解,所以就诞生了更易理解的挖坑法.


需要实现的功能一样但是实现思路不同罢了(其实也差不多=.=).


看看代码


int PartSort2(int* a, int left, int right)
{
  //坑法可以不用让right先走了,更加便于理解=.=
  //下面的思路以升序为例
  //整体思路:用一个变量保存keyi的位置的变量并把keyi的位置当做坑位,当right(以此为例)
  //的找到比a[keyi]大的值的时候直接塞到坑的位置,然后让right当做坑,用left来找....
  int keyi = left;
  int tmp = a[keyi];
  int pit = leyi;//上面tmp保存那个值就先用那个地方当坑使.
  while (left < right)
  {
  if (a[right] < a[keyi])
  {
    a[pit] = a[right];
    pit = right;//右边搞完了,走左边
    while (left < right)
    {
    if (a[left] > a[keyi])
    {
      a[pit] = a[left];
      pit = left;
      break;//break记得弄因为我们这时又把坑位给到了left的位置应该走right了
    }
    left++;
    }
  }
  right--;
  }
  a[left] = tmp;
  return left;
}



能看懂代码注释就不用看下面的内容了.


例:4,1,5,2,3,7,6,9,8还是以左边为基准值同时也用左边当坑.


用图来看看吧:


image.png


不同的方法得到的排序结果不同但最后的排序结果相同.

相关文章
|
存储 安全 Java
集合很简单?开什么玩笑?肝了一周,全是精华,万字讲解,面试再不怕集合问题了
ArrayList 是容量可变的⾮线程安全列表,使⽤数组实现,集合扩容时会创建更⼤的数组,把原有数组复制到新数组。⽀持对元素的快速随机访问,但插⼊与删除速度很慢。ArrayList 实现了 RandomAcess 标记接⼝,如果⼀个类实现了该接⼝,那么表示使⽤索引遍历⽐迭代器更快。
112 0
集合很简单?开什么玩笑?肝了一周,全是精华,万字讲解,面试再不怕集合问题了
|
搜索推荐 算法
排序总结(跑路人笔记1)
排序总结(跑路人笔记)
排序总结(跑路人笔记1)
|
机器学习/深度学习 人工智能 测试技术
记录一些错题(跑路人笔记)
记录一些错题(跑路人笔记)
记录一些错题(跑路人笔记)
算法刷题第五天(跑路人笔记)<双指针>
算法刷题第五天(跑路人笔记)<双指针>
算法刷题第五天(跑路人笔记)<双指针>
|
自然语言处理 C语言 C++
C++入门<一> (跑路人笔记1)
C++入门<一> (跑路人笔记)
C++入门<一> (跑路人笔记1)
|
编译器 C语言 C++
C++入门<一> (跑路人笔记2)
C++入门<一> (跑路人笔记)
C++入门<一> (跑路人笔记2)