选择排序是一种简单直观的排序算法，属于比较类排序，内部是通过比较元素大小，决定每个位置应该存储哪个元素。
常见的算法如下：

1. 简单选择排序（SelectionSort）
2. 堆排序（HeapSort）

简单选择排序

简单选择排序（SelectionSort）原理比较简单，如下：

1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2. 再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。
3. 以此类推，直到所有元素均排序完毕。

代码实现

// objc 版本
- (void)selectionSort:(int[] )arr withLength:(int )length {
    //循环 length 次
    for (int i=0; i<length-1; i++) {
        //查找每个位置的合适的元素
        int findIndex = i;//默认第i个，即待排序列表 第一个元素 是最小（大）的元素
        //循环待排序列表，找到 最小（大）的元素
        for (int j=i+1; j<length-1; j++) {
            if (arr[j]<arr[findIndex]) {
                //找到更小的元素
                findIndex = j;
            }
        }
        //交换最小的元素，交换位置
        if (findIndex != i) {
            int tmp = arr[i];
            arr[i] = arr[findIndex];
            arr[findIndex] = tmp;
        }
    }
}

算法分析

最好时间复杂度：O(n²)。
最坏时间复杂度：O(n²)。
平均时间复杂度：O(n²)。
空间复杂度：O(1)
稳定性：稳定。

堆排序

堆排序（HeapSort）是一种树形选择排序方法，利用大顶堆、小顶堆（完全二叉树Complete Binary Tree）结构的顺序存储结构特性，每次从树中选择出最大节点。
基本流程如下：

1. 将无需序列构建成一个堆（heap，即完全二叉树），顶据升序降序需求选择大顶堆或小顶堆。
2. 将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端，重新调整结构，使其满足大顶堆、小顶堆特性。
3. 然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

那什么是完全二叉树？

完全二叉树

完全二叉树：（Complete Binary Tree），若设二叉树的深度为h，除第h层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边。

例如序列 array[0，...，n-1] ，生成的完全二叉树有下面几个特性。
1.针对任意节点i，节点之间索引规则：

 父节点：(i-1)/2 ，i != 0
 左孩子：2*i+1
 右孩子：2*i+2

2.节点顺序规则：

小顶堆：array[i] <= array[2*i + 1] 且 array[i] <= array[2*i + 2]
大顶堆：array[i] >= array[2*i + 1] 且 array[i] >= array[2*i + 2]

这里我们看一下完全二叉树的大顶堆版本。

大小顶堆

大顶堆即任意节点都要比两个子节点要大，升序的堆排序中会用到。
小顶堆即任意节点都要比两个子节点要大，降序的堆排序中会用到。
例如一个序列：

int arr[] = {9,4,5,6,8,1};

对应二叉树和完全二叉树结构如下：

代码实现

/// 从 index 节点开始，调整二叉树，成为大(小)顶堆。调整之后，可能会使子节点不满足大(小)顶堆，会继续调整子节点。
void heapSortAdjustHandle(int* array, int length, int index) {
    int parentIndex = index;
    while (true) {
        int parentValue = array[parentIndex];
        int maxValue = parentValue;
        int maxIndex = -1;
        // 1.和左子节点比较大小
        int leftChildIndex = 2*parentIndex + 1;
        if (leftChildIndex > length-1) break;
        int leftValue = array[leftChildIndex];
        if (leftValue > maxValue) {
            maxIndex = leftChildIndex;
            maxValue = leftValue;
        }
        // 2.和右子节点比较大小
        int rightChildIndex = 2*parentIndex + 2;
        if (rightChildIndex <= length-1) {
            int rightValue = array[rightChildIndex];
            if (rightValue > maxValue) {
                maxIndex = rightChildIndex;
                maxValue = rightValue;
            }
        }
        if (maxIndex <= -1) break;
        // 3.交换最大值
        array[parentIndex] = maxValue;
        array[maxIndex] = parentValue;
        // 4.继续调整子节点
        parentIndex = maxIndex;
    }
}
/// 堆排序
void heapSort(int* array, int length) {
    // 1.从第一个非子节点开始，调整节点顺序，构造大（小）顶堆
    for (int i=(length-1-1)/2.0; i>=0; i--) {
        heapSortAdjustHandle(array, length, i);
    }
    // 2.循环列表，依次取出顶部元素（最大、最小元素），并继续调整剩下的元素，满足大（小）顶堆
    for (int i=length-1; i>=0; i--) {
        // 2.1交换首尾元素，剔除顶部元素，即选择最大或最小的元素，放在尾部
        int lastValue = array[i];
        array[i] = array[0];
        array[0] = lastValue;
        // 2.2首部元素改变，在剩下的元素（除length-1之后的元素）内，继续调整首节点，满足大（小）顶堆。
        int rightBoundary = i-1;
        heapSortAdjustHandle(array, rightBoundary, 0);
    }
}

算法分析

最好时间复杂度：O(nlogn)。
最坏时间复杂度：O(nlogn)。
平均事件复杂度：O(nlogn)。
空间复杂度：O(1)。
稳定性：不稳定。