C语言之直接插入排序算法的方法

C语言直接插入排序算法的方法

什么是直接插入排序

直接插入排序，是一种应用最广泛的排序算法之一，也是一种稳定的排序算法。它的基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的有序表。具体的过程是将待排序的元素插入到已经排好序的元素中，使插入后仍保持有序。

代码实现

下面是用C语言实现直接插入排序算法的代码：

void direct_insert_sort(int arr[], int len)
{
    if (len <= 1)
        return;
    for (int i = 1; i < len; i++) {
        // 取出要插入的数
        int temp = arr[i];
        int j;
        // 在 sorted[0:i-1] 中找到合适的位置进行插入
        for (j = i - 1; j >= 0; j--) {
            if (arr[j] > temp) {
                // 如果该位置的数比要插入的数大，则将该位置的数后移
                arr[j + 1] = arr[j];
            } else {
                // 否则退出循环，temp就是要插入的位置
                break;
            }
        }
        arr[j + 1] = temp;
    }
}

示例

假设我们要排序的数组如下：

2 4 1 3 5

第一个循环

排序时，先比较2和4，不需要进行排序。接下来比较4和1，将1插入到2 4中间的位置变为2 1 4，接下来比较4和3，3插入到2 1 4中间的位置变为2 1 3 4，最后比较4和5，不需要进行排序，得到排好序的数组：

2 1 3 4 5

第二个循环

先比较1和2，1已经在正确位置，不需要进行排序。然后比较3和1，3在正确位置，不需要排序。比较3和2，2插入到1 3中间的位置成为1 2 3，然后比较4和1，4插入到1 2 3中间的位置成为1 2 3 4，最后比较5和1 2 3 4都大，不需要进行排序，得到排好序的数组：

1 2 3 4 5

这就是直接插入排序的详细过程。