数据结构：选择排序与堆排序原理及实现

选择排序

1 基本思想

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

2 直接选择排序

在元素集合 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, end = n - 1; // 数组下标范围为 [0, n-1]
    // 初始化最大值和最小值的下标
    int mini = begin;
    int maxi = begin;
    // 遍历数组寻找最大值和最小值
    for (int i = begin + 1; i <= end; i++) {
        // i 从 begin+1 开始，因为第一个元素已经初始化为 mini 和 maxi
        // 寻找最大值下标
        if (a[i] > a[maxi]) {
            maxi = i;
        }
        // 寻找最小值下标
        if (a[i] < a[mini]) {
            mini = i;
        }
    }
    // 交换最小值到最左边
    Swap(&a[begin], &a[mini]);
    // 交换最大值到最右边
    Swap(&a[end], &a[maxi]);
}

接下来是多趟排序的实现：

// 交换函数
  {
     tmp = *a;
    *a = *b;
    *b = tmp;
}


  {
     begin = , end = n - ;
     (begin < end) {
         mini = begin, maxi = begin;
        
         ( i = begin + ; i <= end; i++) {
             (a[i] > a[maxi]) {
                maxi = i;
            }
             (a[i] < a[mini]) {
                mini = i;
            }
        }
        
        Swap(&a[begin], &a[mini]);
        
        Swap(&a[end], &a[maxi]);
        
        begin++;
        end--;
    }
}