数据结构算法笔记#5.1:排序(1)

这次来聊聊几个简单的排序算法：插入排序、希尔排序、选择排序、冒泡排序与地精排序。由于我本身不是很想深究这方面的内容，只是应付一下课业，所以就简单介绍一下。反正用处也不是特别大……

插入排序

//插入排序 O(n²)
template <class Type>
void InsertSort(Type arr[], int n) {
    int i, j;
    for (i = 1; i < n; i++) {
        Type temp = arr[i];  //当前处理数据
        //将该数据之前所有大于它的数据都后移一格,找出其正确位置并置入
        for (j = i - 1; j >= 0 && arr[j] > temp; j--) arr[j + 1] = arr[j];
        arr[j + 1] = temp;
    }
}

插入排序

对于插入排序，最好的情况是所有数据在表中已为升序排列，此时只需要进行 n-1 次比较， 0 次移动。而最差的情况即为数据在表中为降序排列。

在 清华大学版数据结构教材 中，数组的第 [0] 位起到哨兵作用，所以算法的代码实现与操作数分析可能与以上结果有 细微差别 。

希尔排序

希尔排序的实现过程与插入排序类似，或者说，就是加强版的插入排序。其基本思路是 将整个数据表分成m个子序列，对每个子序列分别进行插入排序 ，并逐步减少子序列数m，直到m=1为止。

//希尔排序 O(?)
template <class Type>
void ShellSort(Type arr[], int n) {
    int deltas[] = {5, 3, 1};
    for (int i = 0; i < 3; i++) ShellInsert(arr, n, deltas[i]);
}
template <class Type>
void ShellInsert(Type arr[], int n, int delta) {
    Type temp;
    int  i, j;
    for (i = delta; i < n; i++) {
        temp = arr[i];
        for (j = i - delta; (j >= i % delta) && arr[j] > temp; j -= delta) arr[j + delta] = arr[j];
        arr[j + delta] = temp;
    }
}

举个例子：

希尔排序的效率与希尔增量 deltas[] 的取值有关，一般情况下有几种典型求法，可以自行了解，这边不多赘述。

选择排序

顾名思义，选择排序便是每次从 当前位置之后 的数据中选择一个最小值，将其置于当前位置，最终使得序列升序排列：

//选择排序 O(n²)
template <class Type>
void SelectSort(Type arr[], int n) {
    for (int i = 0; i < n; i++) {
        int min_index = i;
        for (int j = i + 1; j < n; j++)
            if (arr[j] < arr[min_index]) min_index = j;
        swap(arr[i], arr[min_index]);
    }
}
template <class Type>
void swap(Type& a, Type& b) {
    Type temp = a;
    a = b;
    b = temp;
}

选择排序

冒泡排序

不会有人学到这里还不会冒泡排序吧？

//冒泡排序 O(n²)
template <class Type>
void BubbleSort(Type arr[], int n) {
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - i - 1; j++)
            if (arr[j] > arr[j + 1]) swap(arr[j], arr[j + 1]);
}

冒泡排序

地精排序

//地精排序 O(n²)
template <class Type>
void GnomeSort(Type arr[], int n) {
    int i = 0;
    while (i < n) {
        if (i == 0 || arr[i - 1] <= arr[i])  //走到原点或者当前数据符合升序
            i++;                             //无需处理,判断下一位数据
        else {
            swap(arr[i - 1], arr[i]);
            i--;  //否则向前冒泡
        }
    }
}