排序篇(二)----选择排序

简介: 排序篇(二)----选择排序

排序篇(二)----选择排序

1.直接选择排序

基本思想:

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

直接选择排序:

  • 在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素
  • 若它不是这组元素中的最后一个(第一个)元素,则将它与这组元素中的最后一个(第一个)元素交换
  • 在剩余的array[i]–array[n-2](array[i+1]–array[n-1])集合中,重复上述步骤,直到集合剩余1个元素
//选择排序
void SelectSort(int* a, int n)
{
  int begin = 0;
  int end = n - 1;
  while (begin < end)
  {
    int max = begin;
    int min = begin;
    for (int i = begin + 1; i <= end; i++)
    {
      if (a[i] < a[min])
      {
        min = i;
      }
      if (a[i] > a[max])
      {
        max = i;
      }
    }
    Swap(&a[begin], &a[min]);
    if (begin == max)
    {
      max = min;
    }
    Swap(&a[end], &a[max]);
    begin++;
    end--;
  }
}

代码解析:

代码中的变量begin和end分别表示待排序序列的起始和结束位置。在每一轮排序中,首先将begin位置设置为当前的最小值和最大值的索引。然后从begin+1到end的范围内遍历,找到最小值的索引min和最大值的索引max。

接下来,通过调用Swap函数交换begin位置和min位置的元素,将最小值放到待排序序列的起始位置。如果begin位置和max位置相同,说明最大值被交换到了min位置,需要将max更新为min。

最后,通过调用Swap函数交换end位置和max位置的元素,将最大值放到待排序序列的末尾。然后更新begin和end,继续下一轮排序,直到begin不小于end,排序完成。

直接选择排序的特性总结:

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

2.堆排序

要理解堆排序,首先就要先理解堆是一种什么样的结构,详情见: 堆的实现

堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆,排降序建小堆。

//堆排序
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[child] > a[parent])
    {
      Swap(&a[child], &a[parent]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
      break;
  }
}
void HeapSort(int* a, int n)
{
  //向上调整建堆  o(n*log n)
  //for (int i = 1; i < n; i++)
  //{
  //  AdjustUp(a, i);
  //}
  //升序(建大堆)  降序(建小堆)
  //o(n)向下调整建堆
  for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(a, n, i);
  }
  //o(n* log n)
  int end = n - 1;
  while (end > 0)
  {
    Swap(&a[0], &a[end]);
    AdjustDown(a, end, 0);
    end--;
  }
}

代码解析:

AdjustDown函数用于向下调整堆,它接受三个参数:待调整的堆数组a、堆的大小n和当前需要调整的节点parent。在每一次调整中,首先计算出当前节点的左孩子节点的索引child,然后进行循环判断。

在循环中,首先判断右孩子节点是否存在且比左孩子节点大,如果是,则将child更新为右孩子节点的索引,否则保持不变。然后判断当前节点的值是否小于最大的孩子节点的值,如果是,则交换当前节点和最大孩子节点的值,并更新parent和child的值,继续向下调整。如果当前节点的值大于等于最大孩子节点的值,则退出循环。

HeapSort函数用于实现堆排序算法。首先通过向下调整的方式建立一个大顶堆,具体实现是从最后一个非叶子节点开始,依次向上调整,直到根节点。然后,通过循环交换堆顶元素和堆的最后一个元素,并对剩余的元素进行向下调整,重复这个过程直到整个序列有序。

堆排序的特性总结:

  1. 堆排序使用堆来选数,效率就高了很多。
  2. 时间复杂度:O(N*logN)
  3. 空间复杂度:O(1)
  4. 稳定性:不稳定
目录
相关文章
|
7月前
|
算法 搜索推荐
排序——选择排序
排序——选择排序
75 0
|
7月前
|
搜索推荐 算法 Shell
排序——插入排序
排序——插入排序
49 0
|
存储 搜索推荐 测试技术
排序篇(一)----插入排序
排序篇(一)----插入排序
51 0
|
算法 搜索推荐
排序——冒泡排序
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。
|
搜索推荐
排序(2)之选择排序
继插入排序后,今天小编就给大家另一个模块,选择排序的学习,那么话不多说,我们直接进入正题。
122 0
|
存储 搜索推荐 测试技术
排序(1)之插入排序
从今天小编就开始给大家介绍排序的内容,对于排序内容我们一共分,插入,选择,交换,归并这几个大类,那么今天小编给大家带来的就是插入排序
105 0
|
算法 搜索推荐 API
算法排序3——选择排序
算法排序3——选择排序
114 0
算法排序3——选择排序
|
索引
掌握常见的几种排序-选择排序
选择排序是一种简单的排序,时间复杂度是O(n^2),在未排序的数组中找到最小的那个数字,然后将其放到起始位置,从剩下未排序的数据中继续寻找最小的元素,将其放到已排序的末尾,以此类推,直到所有元素排序结束为止。
122 0
掌握常见的几种排序-选择排序
|
算法 搜索推荐 Java
排序:选择排序(算法)
排序就是算法。   选择排序(Selection sort)是一种简单直观的排序算法。 选择排序是不稳定的排序方法。   eg:序列[9,9, 1]第一次就将第一个[9]与[1]交换,导致第一个9挪动到第二个9后面 Note:一般面试的时候才会用到选择、冒泡排序。
279 0
排序:选择排序(算法)
|
算法
排序——快速排序
排序——快速排序
125 0
排序——快速排序