【选择排序】直接选择排序 与 堆排序

简介: 【选择排序】直接选择排序 与 堆排序

1. 排序的概念:

排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。


稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定。


内部排序:数据元素全部放在内存中的排序。


外部排序:数据元素太多不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序。


2.选择排序的基本思想

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

3.直接选择排序

在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素

若它不是这组元素中的最后一个(第一个)元素,则将它与这组元素中的最后一个(第一个)元素交换。

在剩余的array[i]--array[n-2] (array[i+1]--array[n-1])集合中,重复上述步骤,直到集合剩余1个元素

选择排序图解:这张动图是选择后面最小的数与前面做交换

当让我们还可以优化,如果是升序,每一次遍历分别选出最小的元素和最大的元素,分别与前面和后面数据做交换。

代码实现:

//交换函数
void Swap(int* p1, int* p2)
{
  int t = *p1;
  *p1 = *p2;
  *p2 = t;
}
// 选择排序 升序
void SelectSort(int* arr, int n)
{
  int begin = 0;
  int end = n - 1;
  while (begin < end)
  {
    int maxi = begin;
    int mini = begin;
    for (int i = begin; i <= end; i++)
    {
      if (arr[i] > arr[maxi])
      {
        maxi = i;
      }
      if (arr[i] < arr[mini])
      {
        mini = i;
      }
    }
    Swap(&arr[mini], &arr[begin]);
    if (begin == maxi)
    {
      maxi = mini;
    }
    Swap(&arr[maxi], &arr[end]);
    begin++;
    end--;
  }
}


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

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


4.堆排序

我们这里需要先了解堆的结构,如果不了解可以看我之前的文章【数据结构】这堆是什么。


当我们了解完堆的结构后,我们就可以开始学习堆排序了。


堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的

种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆,排降序建小堆。


  1. 首先要构建一个堆,
  2. 然后让堆顶元素与最后一个元素交换,把最后一个位置元素当作不在堆内。
  3. 然后通过向下调整法调整堆。循环就可以排序

图解:

建堆可以使用向上调整法建堆和向下调整法建堆,这两种方法在【数据结构】这堆是什么 中有详细讲解。向上调整法建堆时间复杂度为O(N*logN),但是向下调整法时间复杂度低,为O(N)。所以我们这里使用向下调整法建堆。


代码实现:

//向下调整法
void AdjustDown(int* arr, int n, int parent)
{
  int child = parent * 2 + 1;
  while (child < n)
  {
    if (child + 1 < n && arr[child + 1] > arr[child])
    {
      child++;
    }
    if (arr[parent] < arr[child])
    {
      Swap(&arr[parent], &arr[child]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}
//堆排序
void HeapSort(int* arr, int n)
{
  //建堆
  for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(arr, n, i);
  }
  //排序
  int end = n - 1;
  while (end > 0)
  {
    Swap(&arr[end], &arr[0]);
    AdjustDown(arr, end, 0);
    end--;
  }
}

堆排序的特性总结:

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


本篇文章结束,我们下一篇文章来学习一下:【交换排序】冒泡排序与快速排序。

相关文章
|
5月前
|
算法 搜索推荐 Java
选择排序就是这么容易
选择排序就是这么容易
31 0
|
6月前
|
算法 搜索推荐 Java
选择排序 - 堆排序
选择排序 - 堆排序
选择排序 - 堆排序
|
6月前
选择排序与堆排序
选择排序与堆排序
35 0
|
搜索推荐 算法
【排序算法(二)】选择排序(直接选择排序&&堆排序)
【排序算法(二)】选择排序(直接选择排序&&堆排序)
【排序算法(二)】选择排序(直接选择排序&&堆排序)
|
6月前
|
搜索推荐 算法
排序算法:选择排序(直接选择排序、堆排序)
排序算法:选择排序(直接选择排序、堆排序)
42 0
|
搜索推荐
16 选择排序
16 选择排序
30 0
|
机器学习/深度学习 搜索推荐 算法
选择排序的实现
选择排序的实现
98 1
|
人工智能 搜索推荐 算法
常见排序算法之选择排序——直接选择排序、堆排序
哈喽大家好,我是保护小周ღ,本期为大家带来的是常见排序算法中的选择排序,主要有直接选择排序以及——堆排序(有点难理解),包您一看就会,快来试试吧
139 0
常见排序算法之选择排序——直接选择排序、堆排序
|
算法 搜索推荐 测试技术
直接选择排序
直接选择排序
107 0
直接选择排序