选择排序

直接选择排序

每一次从待排序的数据元素中选出最小（和最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完
时间复杂度：O(n²) 数据不敏感
比较次数n²
移动次数正序为0，反序为n
空间复杂度：O(1)
稳定性：不稳定

void SelectSort(int array[], int size) {
    for (int i = 0; i < size; i++) {
        // 无序 [0, size - 1 - i]
        // 有序 [size - i, size - 1]
        int maxIdx = 0;
        // 要查找整个无序区间的最大值的下标
        for (int j = 1; j <= size - 1 - i; j++) {
            if (array[j] >= array[maxIdx]) {
                maxIdx = j;
            }
        }
        // maxIdx 记录着无序区间部分最大的数的下标
        // 和无序区间的最后一个位置的数进行交换
        swap(array[maxIdx], array[size - 1 - i]);
    }
}

void SelectSortOP(int array[], int size) {
    int begin = 0;
    int end = size - 1;
    // 有序 [0, begin - 1]	  最小的数
    // 有序 [end + 1, size - 1] 最大的数
    // 无序 [begin, end]
    while (begin <= end) {
        int min = begin;
        int max = begin;
        for (int i = begin; i <= end; i++) {
            if (array[i] > array[max]) {
                max = i;
            }
            if (array[i] < array[min]) {
                min = i;
            }
        }
        // 最小的数放到无序区间的最开始
        // 最大的数放到无序区间的最末尾
        swap(array[min], array[begin]);
        if (max == begin) {
            max = min;
        }
        swap(array[max], array[end]);
        begin++;
        end--;
    }
}

堆排序

从最大（小）堆顶不断取走堆顶元素放到有序序列中，直到堆的元素被全部取完
时间复杂度：O(n * log n) 数据不敏感
空间复杂度：O(1)
稳定性：不稳定

void Heapify(int array[], int size, int index) {
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    if (left >= size) {
        return;
    }
    int max = left;
    if (right < size && array[right] > array[left]) {
        max = right;
    }
    if (array[index] >= array[max]) {
        return;
    }
    swap(array[max], array[index]);
    Heapify(array, size, max);
}

void CreateHeap(int array[], int size) {
    // 从最后一个非叶子结点，一直到 0，不断的向下调整
    for (int i = (size - 2) / 2; i >= 0; i--) {
        Heapify(array, size, i);
    }
}

void HeapSort(int array[], int size) {
    // 建大堆
    CreateHeap(array, size); // n
    // 无序 [0, size - 1 - i]
    // 有序 [size - i, size - 1]
    for (int i = 0; i < size; i++) { // n * log n
        // 交换最大的数和无序区间的最后一个数
        swap(array[0], array[size - 1 - i]);
        // 堆的性质被破坏了，要调整的是剩余无序部分的长度 size - 1 - i
        Heapify(array, size - 1 - i, 0); // log n
    }
}

建堆时间复杂度：
对满二叉树而言，第i层(根为第0层)有2ⁱ个节点
由于建堆过程自底向上，以交换作为主要操作，因此第i层任意节点在最不利情况下，需要经过(n−i)次交换操作才能完成以该节点为堆根节点的建堆过程
$T(n)=2^0(n−0)+2^1(n−1)+...+2^n(n−n)=\sum_{i=0}^n{(2^i(n-i))}$
$2T(n)=2^1(n-0)+2^2(n-1)+2^{n+1}(n-n)=\sum_{i=1}^{n+1}{(2^i(n-i))}$
$2T(n)-T(n)=2^{n+1}-2-n$
总节点数$1+2+4+...+2^n=2^{n+1}−1$
忽略减1取$N＝2^{n+1}$
$T(n)=2^{n+1}−2−n=N(1−\frac{log\,N}{N}−\frac2N)≈N$
堆排序时间复杂度：
调整堆顶n-1次，总共比较次数$2(log(n-1)+log(n-2)+...+log2)<2n(log n)$
因此，堆排序时间复杂度为O(n * log n)