一、简单选择排序

将初始序列看作一个无序序列，每一轮遍历都是在这个无序序列中找出最小的元素，换到初始序列的第一个位置，不断重复操作，直到所有的元素有序。

1. 算法思想

简单选择排序

2. 算法实现

void selectSort(int R[], int n){
    int k; // 保存最小的关键字
    int temp; // 暂存待交换的元素
    for(int i = 0; i < n; i++){
        k = i; // 取第一个元素作为默认的最小关键字
        // 从无序序列中挑选一个最小的关键字，重新作为 k 的值
        for(int j = i + 1; j < n; j++){
            if(R[k] > R[j]){
                k = j;
            }
        }
        // 将最小的关键字与 i 所指的位置的元素进行交换
        temp = R[i];
        R[i] = R[k]; // 一趟排序结束后，i 所指位置就保存了当前序列中最小的关键字
        R[k] = temp;
    }
}

每趟排序，总有一个元素落在其最终的位置上

二、堆排序

可以把堆看作一颗完全二叉树，并且满足：任何一个非叶结点的关键字不小于（或不大于）其左右子树的关键字。若父结点关键字大孩子关键字小，叫大根堆；否则成为小根堆；

1. 算法思想

堆排序

3. 算法实现

/**
* 实现数组R[low]到R[high]的范围内对在位置low上的结点进行调整
* 关键字存储设定为数组下标1开始
*/
void sift(int R[], int low, int high){
    int i = low, j = 2 * i; // R[j]是R[i]的左孩子结点 
    int temp = R[i];
    while(j <= high){
        if(j < high && R[j] < R[j+1]){ // 若右孩子较大，则把j指向右孩子
            ++j; // j 变为 2*i+1
        }
        if(temp < R[j]){ 
            R[i] = R[j]; // 将R[j]调整到双亲结点的位置上
            i = j;  // 修改 i 和 j 的值，以便继续向下调整
            j = 2 * i;
        }else{
            break; // 调整结束
        }
    }
    R[i]= temp; // 被调整结点的值放入最终位置
}
/* 堆排序函数 */
void heapSort（int R[], int n){
    int i;
    int temp;
    for(i = n/2; i >= 1; --i){
        sift(R, i, n); // 建立初始堆
    }
    for（i = n; i >= 2; --i){ // 进行 n-1 次循环，完成堆排序
       temp = R[1];
       R[1] = R[i];
       R[i] = temp; // 换出根结点的关键字，将其放入最终位置

       sift(R, 1, i-1); // 在减少了 1 个关键字的无序序列中进行调整
    }
}