希尔排序与选择排序

导语

希尔排序，又称为缩小增量排序，实质是一种分组的插入排序，但在时间效率上较前述排序算法有很大改进，因DL.Shell于1959年提出而得名。

算法思想
先将整个待排记录序列按步长分割成若干子序列分别进项直接插入排序，带整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

void shellSort(int *a, int length) {
    for (int gap = length / 2; gap > 0; gap /= 2) { //缩小步长
        for (int i = gap; i < length; i++) {
            for (int j = i - gap; j >= 0 && a[j] > a[j + gap] ; j -= gap) {
                swap(a[j], a[j + 1]);
            }
        }
    }
}

选择排序，和直接插入排序类似，只不过是将序列中最小的元素找出，放置到有序区末尾。

void selectSort(int *a, int length) {
    int minIndex = 0;
    for (int i = 0; i < length; i++) {
        minIndex = i;
        for (int j = i + 1; j < length; j++) {
            if (a[j] < a[minIndex]) { //找出最小元素的位置
                minIndex = j;
            }
        }
        swap(a[i], a[minIndex]); //将最小元素放置到有序区的末尾
    }
}