C语言基本排序算法之插入排序与直接选择排序实现方法

本文将介绍C语言中两种常见的基本排序算法：插入排序和直接选择排序。我们将会详细阐述它们的实现方法，并提供示例代码来帮助理解和实践。

插入排序

插入排序是一种简单而常见的排序算法，它将待排序的数列分成已排序和未排序两部分，初始时已排序部分只包含一个元素，随着算法的运行，每次从未排序部分中取出第一个元素插入到已排序部分的合适位置，直到全部元素排序完毕。

具体实现方法如下：

void insertionSort(int arr[], int size) {
    int i, j, current;
    for (i = 1; i < size; i++) {
        current = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > current) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = current;
    }
}

插入排序是指在已排好序列中找到合适的位置插入当前元素，使得插入后的序列仍然有序。在实现上，我们使用了一个游标变量current来记录当前需要插入的元素，然后通过一个内层循环将已排序的元素逐个向后移位，直到找到前一个元素比current小（或已经到达序列起始位置），这时我们就知道current应该插入在这个元素后面。

下面是一个示例，演示了上述代码的运行过程：

原始数组: [25, 17, 31, 13, 2]

- 第一次排序之后: [17,25,31,13,2]
- 第二次排序之后: [17,25,31,13,2]
- 第三次排序之后: [13,17,25,31,2]
- 第四次排序之后: [2,13,17,25,31]

从上面的示例中可以看出，插入排序算法的时间复杂度为$O(n^2)$，因此在大规模数据排序时可能效率较低，但对于小规模数据排序时，插入排序是一个不错的选择。

直接选择排序

直接选择排序也是一种常见的排序算法，它的思路是将剩余未排序的最小值不断交换到剩余序列的最前端，直到所有元素按照从小到大的顺序排好。

具体实现方法如下：

void selectionSort(int arr[], int size) {
    int i, j, minIndex, temp;
    for (i = 0; i < size - 1; i++) {
        minIndex = i;
        for (j = i + 1; j < size; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

在实现中，我们首先通过一个外层循环来遍历整个数组，然后从当前未排序元素的剩余序列中寻找最小值，记下它的下标，最后将它和当前未排序序列中的第一个元素交换。这个交换操作相当于将当前未排序序列的最小值插入到已排序部分的末尾。

下面是一个示例，演示了上述代码的运行过程：

原始数组: [25, 17, 31, 13, 2]

- 第一次排序之后: [2, 17, 31, 13, 25]
- 第二次排序之后: [2, 13, 31, 17, 25]
- 第三次排序之后: [2, 13, 17, 31, 25]
- 第四次排序之后: [2, 13, 17, 25, 31]

直接选择排序算法的时间复杂度也为$O(n^2)$，但由于每次只需要做一次交换操作，因此在某些情况下它比插入排序的效率更高。

总结

插入排序和直接选择排序是两种常见的基本排序算法，它们的实现都相对简单，适用于小规模的数据排序。如果需要对大规模数据进行排序，可以考虑使用其他更为高效的排序算法，如快速排序、归并排序等。