【数据结构】-图解八大排序(思路+实现+总结)(2)

简介: 【数据结构】-图解八大排序(思路+实现+总结)(2)

五、选择排序


1、直接选择排序


  • 基本思想:


每一次遍历待排序的数据元素从中选出最小(或最大)的一个元素,存放在序列的起始(或者末尾)位置,直到全部待排序的数据元素排完


  • 动图展示:


image.gif


  • 实现代码:


// 选择排序
void SelectSort(int* a, int n)
{
  int begin = 0, end = n - 1;//记录下标
  while (begin < end)
  {
    int mini = begin;
    for (int i = begin; i <= end; i++)
    {
      //遍历找到最小数据并记录下标
      if (a[i] < a[mini])
        mini = i;
    }
    Swap(&a[begin], &a[mini]);//交换
    begin++;//缩小范围
  }
}


这里我们还可以对直接选择排序做一个优化:每次遍历待排序数据找出最大和最小的数据,分别排列到序列起始和末尾


  • 优化代码:


// 选择排序(优化版)
void SelectSort(int* a, int n)
{
  int begin = 0, end = n - 1;
  while (begin < end)
  {
    int maxi = begin, mini = begin;
    for (int i = begin; i <= end; i++)//遍历找到最大最小的下标
    {
      if (a[i] > a[maxi])
        maxi = i;
      if (a[i] < a[mini])
        mini = i;
    }
    Swap(&a[begin], &a[mini]);//交换
    //当最初始位置begin与对大数据下标重合的情况
    if (begin == maxi)//修正下标位置
      maxi = mini;
    Swap(&a[end], &a[maxi]);
    begin++;//缩小范围
    end--;
  }
}


  • 直接选择排序的特性总结:
  1. 直接选择排序思考非常好理解,但是效率不是很好。实际中很少使用
  2. 时间复杂度:O(N^2)
  3. 空间复杂度:O(1)
  4. 稳定性:不稳定


2、堆排序


堆排序是指利用堆(数据结构)进行选择数据的一种排序算法


基本思想:


原则:


先将原数组建成堆,需要注意的是排升序要建大堆,排降序建小堆

注:以大堆为例


建堆:


一个根节点与子节点数据如果不符合大堆结构,那么则对根节点数据进行向下调整,而向下调整的前提是左右子树也符合大堆结构,所以从堆尾数据的根节点位置开始向下调整建大堆


排序:


大堆堆顶数据一定是待排数据中最大的,将堆顶数据与堆尾数据交换,交换后将除堆尾数据看成新堆,对现堆顶数据进行向下调整成大堆,以此循环直至排列完毕

向下调整:


找到子节点中的较大数据节点比较,如果父节点数据比大子节点小则交换,直到不符合则停止向下交换,此时再次构成了一个大堆结构



具体堆排序详解:堆排序超详解


动图展示:大堆排序


image.gif


  • 实现代码:


void Adjustdown(int* a, int n,int parent)
{
  int child = parent * 2 + 1;
  while (child < n)
  {
    //找到数据大的子结点
    if (child + 1 < n && a[child + 1] > a[child])
    {
      child++;
    }
    //父节点数据小于子节点就交换
    if (a[parent] < a[child])
    {
      Swap(&a[parent], &a[child]);
      //更新下标
      parent = child;
      child = parent * 2 + 1;
    }
    else//否则向下调整完毕
      break;
  }
}
// 堆排序(升序)建大堆
void HeapSort(int* a, int n)
{
  int i;
  //建大堆
  for (i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    Adjustdown(a, n, i);
  }
  //交换调整
  for (i = n - 1; i >= 0; i--)
  {
    Swap(&a[0], &a[i]);//与当前堆尾数据交换
    Adjustdown(a, i, 0);//对交换后堆顶数据进行向下调整
  }
}


  • 直接选择排序的特性总结:
  1. 堆排序使用堆来选数,效率就高了很多。
  2. 时间复杂度:O(N*logN)
  3. 空间复杂度:O(1)
  4. 稳定性:不稳定


六、交换排序


1、冒泡排序


  • 基本思想:


每次遍历待排序数组,对相邻数据进行比较,不符合排序要求则交换


  • 动图展示:


image.gif


实现代码


// 冒泡排序
void BubbleSort(int* a, int n)
{
  int i, j;
  for (i = 0; i < n - 1; i++)//遍历趟数
  {
    for (j = 0; j < n - 1 - i; j++)//比较次数
    {
      if (a[j] > a[j + 1])//升序
        Swap(&a[j], &a[j + 1]);//交换
    }
  }
}


  • 冒泡排序的特性总结:
  1. 冒泡排序是一种非常容易理解的排序
  2. 时间复杂度:O(N^2)
  3. 空间复杂度:O(1)
  4. 稳定性:稳定


2、快速排序


  • 基本思想为:


任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列

左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值 然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止


按基准值划分左右的方式有:

1)hoare

注:基本操作过程如图示


ee4836fac83a4d3e94d02487ef14ab90.gif

  • 实现代码:


// 按基准划分hoare版本
int PartSort1(int* a, int left, int right)
{
  int mid = GetMidIndex(a, left, right);//三数取中(优化取基准值,后面会解释)
  Swap(&a[mid], &a[left]);//使得中间值永远在最左,便于决定谁先走
  int key = left;
  while (left < right)
  {
    //Key设在左边,先从右边寻找小于a[key]的
    while (left < right && a[right] >= a[key])
    {
      right--;
    }
    //再从左边寻找大于a[key]的
    while (left < right && a[left] <= a[key])
    {
      left++;
    }
    //找到后交换
    Swap(&a[left], &a[right]);
  }
  //最后相遇时将key与相遇点交换
  Swap(&a[key], &a[left]);
  return left;//返回相遇点下标
}


key的位置与左右下标谁先走的关系:

注:对于排升序来说


一般来说在三数取中后得到中等值key,我们让该值与待排序数组的最左边起始位置交换,使得key永远在最左边,并且之后会让右下标先走找小于key的值,找到后再让左下标走找大于key的值,都找到则交换,相遇后再将key与相遇位置的值交换


右下标先走的话,对于两下标相遇的的情况只有两种:


右下标走着走着遇到左下标,此时左下标的值一定是小于key的值(交换后左下标是原来右下标的小于key的值)


左下标走着走着遇到右下标,此时右下标的值一定是小于key的是(右下标找小于key的值)


所以这样保证了最后下标相遇与key交换后,key左边区间一定小于key,右边区间一定大于key


相关文章
05_用一个栈实现另一个栈的排序
05_用一个栈实现另一个栈的排序
|
2月前
|
C语言
数据结构——排序【上】
数据结构——排序【上】
19 2
|
2月前
|
搜索推荐 算法 测试技术
【数据结构】排序
【数据结构】排序
|
3月前
|
搜索推荐
【数据结构常见七大排序(三)上】—交换排序篇【冒泡排序】And【快速排序】
【数据结构常见七大排序(三)上】—交换排序篇【冒泡排序】And【快速排序】
【数据结构常见七大排序(三)上】—交换排序篇【冒泡排序】And【快速排序】
|
3月前
|
搜索推荐
【数据结构常见七大排序(二)】—选择排序篇【直接选择排序】And【堆排序】
【数据结构常见七大排序(二)】—选择排序篇【直接选择排序】And【堆排序】
|
3月前
|
搜索推荐 测试技术
【数据结构常见七大排序(一)】—插入排序篇【直接插入排序】And【希尔排序】
【数据结构常见七大排序(一)】—插入排序篇【直接插入排序】And【希尔排序】
|
5月前
|
存储 搜索推荐 算法
C语言数据结构算法,常用10种排序实战
插入排序(Insertion Sort) 希尔排序(Shell Sort) 选择排序(Selection Sort) 冒泡排序(Bubble Sort) 归并排序(Merge Sort) 快速排序(Quick Sort) 堆排序(Heap Sort) 基数排序(Radix Sort)
50 1
C语言数据结构算法,常用10种排序实战
|
4月前
|
搜索推荐 算法
【排序】数据结构——排序算法概念及代码详解(插入、冒泡、快速、希尔)
【排序】数据结构——排序算法概念及代码详解(插入、冒泡、快速、希尔)
TU^
|
4月前
|
搜索推荐 算法 测试技术
数据结构~~排序
数据结构~~排序
TU^
28 1
|
4月前
|
搜索推荐 算法 测试技术
数据结构——排序
数据结构——排序
28 1