数据结构——排序（选择排序）

目录

一、选择排序的总体概念

二、直接选择排序

三、堆排序

一、选择排序的总体概念

选择排序（Selection Sort）是一种简单的排序算法，其核心思想是通过不断地从待排序的数据集合中选择出特定元素（最小或最大元素），并将其放置在已排序序列的合适位置，逐步构建出一个有序序列。在这里主要讲直接选择排序和堆排序。

二、直接选择排序

• 基本概念：

  • 直接选择排序是一种简单的排序算法。它的基本思路是在待排序的序列中，依次找出最小（或最大）的元素，然后将其与序列的起始位置（或者当前未排序部分的起始位置）的元素交换，经过多次这样的操作，使得整个序列逐渐变得有序。

• 工作原理：

  • 第一趟排序，从整个数组（或序列）的元素中找出最小（假设是按升序排序）的元素，将它与数组的第一个元素交换位置。这样，第一个元素就成为了已排序部分的元素，而剩余的元素则构成了未排序部分。
  • 第二趟排序，在未排序部分的元素中再次找出最小的元素，将其与未排序部分的第一个元素（也就是整个数组的第二个元素）交换位置。此时，前两个元素就构成了已排序部分，未排序部分的元素数量减少一个。
  • 重复这个过程，直到所有的元素都被放入已排序部分，整个数组就完成了排序。

• 特点：

  • 简单易懂，代码实现相对容易。
• 它的时间复杂度在最好、最坏和平均情况下都是 O（n），其中 n  是数组的长度。这是因为对于每一个元素，都需要遍历剩余的未排序元素来找到最小（或最大）元素。因此，当数据量较大时，直接选择排序的效率较低。

• 主要步骤

• 确定排序范围和初始化：

  • int begin = 0, end = n - 1;定义了两个变量begin和end，分别表示当前未排序部分的起始和结束索引。初始时，整个数组都是未排序的，所以begin为 0，end为数组长度n - 1。
  • while (begin < end)这个循环会持续进行，直到未排序部分只剩下一个元素，即begin不小于end。

• 查找最小和最大元素索引：

  • int mini = begin, maxi = begin;初始化最小元素索引mini和最大元素索引maxi为当前未排序部分的起始索引begin。
  • for (int i = begin; i <= end; i++)这个循环遍历当前未排序部分的所有元素，查找最小和最大元素的索引。
  • if (a[i] < a[mini])如果当前元素小于当前最小元素，则更新mini为当前元素的索引。
  • if (a[i] > a[maxi])如果当前元素大于当前最大元素，则更新maxi为当前元素的索引。

• 交换最小元素和调整最大元素索引：

  • Swap(&a[begin], &a[mini]);将最小元素与当前未排序部分的起始元素交换位置，确保最小元素在正确的位置。
  • if (begin == maxi)如果在交换最小元素后，原来的最大元素索引与当前未排序部分的起始索引重合，说明最大元素被交换到了mini的位置，需要更新maxi为新的位置。
  • Swap(&a[maxi], &a[end]);将最大元素与当前未排序部分的末尾元素交换位置，确保最大元素也在正确的位置。

• 缩小未排序部分范围：

  • ++begin;将未排序部分的起始索引向后移动一位，因为现在起始位置的元素已经是有序的了。
  • --end;将未排序部分的结束索引向前移动一位，同理末尾位置的元素也已经是有序的了。

• 
  // 直接选择排序:一次做两次
  void SelectSort(int* a, int n)
  {int begin = 0, end = n - 1;while (begin < end){int mini = begin,maxi = begin;for (int i=begin;i<=end;i++){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi=i;}}Swap(&a[begin], &a[mini]);// 如果begin跟maxi重叠，需要修正一下maxi的位置if (begin == maxi){maxi = mini;}Swap(&a[maxi], &a[end]);++begin;--end;}
  }

  三、堆排序

• 基本概念：

  • 堆排序是一种基于二叉堆数据结构的排序算法。二叉堆是一种完全二叉树，它分为最大堆和最小堆。在最大堆中，每个节点的值都大于或等于它的子节点的值；在最小堆中，每个节点的值都小于或等于它的子节点的值。堆排序利用了堆的这种特性来进行排序。

• 工作原理：

  • 首先，将待排序的数组构建成一个最大堆（如果要进行升序排序）或者最小堆（如果要进行降序排序）。构建堆的过程是从最后一个非叶子节点开始，对每个非叶子节点进行调整，使得以该节点为根的子树满足堆的性质。
  • 然后，将堆顶元素（最大堆中的最大值或者最小堆中的最小值）与数组的最后一个元素交换，此时最大（小）值就被放置到了正确的位置。交换后，对新的堆顶元素进行调整，使其重新满足堆的性质。
  • 重复这个交换和调整的过程，直到整个数组都被排序。

• 特点：

  • 堆排序的时间复杂度为O(n*logn) ，在效率上比直接选择排序高，尤其在处理大量数据时优势明显。
  • 它是一种不稳定的排序算法，因为在交换元素的过程中可能会改变相同元素的相对顺序。
  • 堆排序的空间复杂度为O(1) ，它是一种原地排序算法，只需要常数级别的额外空间来进行排序操作。

• 主要步骤

• 构建大根堆：

  • for (int i = (n - 1 - 1) / 2; i >= 0; --i)这个循环从最后一个非叶子节点开始，依次对每个非叶子节点调用AdjustDwon函数进行调整，以构建大根堆。
  • AdjustDwon函数用于调整以某个节点为根的子树，使其满足大根堆的性质。在构建大根堆的过程中，从下往上、从右往左对非叶子节点进行调整，确保每个节点的值都大于等于其左右子节点的值。

• 排序过程：

  • int end = n - 1;初始化变量end为数组的最后一个索引，表示未排序部分的边界。
  • while (end > 0)这个循环在未排序部分不为空时持续进行。
  • Swap(&a[0], &a[end]);将堆顶元素（当前最大元素）与未排序部分的最后一个元素交换，这样最大元素就被放置到了正确的位置。
  • AdjustDwon(a, end, 0);对交换后的堆顶元素进行调整，使其重新满足大根堆的性质。调整的范围是从堆顶开始，长度为end，因为此时已将最大元素放置到了end位置，不需要再考虑它。
  • --end;减小未排序部分的范围，将已排序部分扩大一个元素。

    //堆排序
    void HeapSort(int* a, int n)
    {// 建堆  O(N)for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDwon(a, n, i);}// 排升序，建大堆还是小堆？建大堆// 如果建小堆，最小数在堆顶，再选剩下的数是重新建堆选数int end = n - 1;while (end > 0){//把最大值和最小值交换Swap(&a[0], &a[end]);AdjustDwon(a, end, 0);--end;}
    }