C语言排序算法之插入排序

让我来详细讲解一下“C语言排序算法之插入排序”的完整攻略。

什么是插入排序？

插入排序是一种简单的排序算法，其原理是将一个数组分为两个部分，已排序和未排序。通过一次次取出未排序部分的首位元素，插入到已排序部分中正确的位置，最终实现整个数组的排序。

插入排序算法的步骤

插入排序的具体步骤如下：

1. 将待排序数组分成已排序和未排序两个部分，第一个元素默认为已排序部分，其余为未排序部分。
2. 依次从未排序部分中取出第一个元素。
3. 从已排序部分的末尾开始逆序遍历，将每个比取出元素大的元素向右移动一个位置，为新元素腾出一个位置。
4. 将取出元素插入到已排序部分的正确位置。
5. 重复步骤2~4，直到未排序部分的元素全部插入到已排序部分中。

插入排序的C语言实现

下面给出插入排序的C语言实现代码：

void insertion_sort(int arr[], int len){
    int i, j, key;
    // 从未排序部分的首位开始遍历
    for(i = 1; i < len; i++){
        key = arr[i];
        j = i - 1;
        // 在已排序部分中找到key的正确位置
        while(j >= 0 && arr[j] > key){
            arr[j + 1] = arr[j];
            j--;
        }
        // 将key插入到正确位置
        arr[j + 1] = key;
    }
}

示例说明

下面给出两个关于插入排序示例的说明。

示例一

对数组{4,3,2,10,12,1,5,6}进行插入排序。

1. 已排序部分：4；未排序部分：3,2,10,12,1,5,6。
2. 取出未排序部分的首位元素3。
3. 逆序遍历已排序部分，在4的位置上找到合适的位置插入3。
4. 已排序部分：3,4；未排序部分：2,10,12,1,5,6。
5. 取出未排序部分的首位元素2。
6. 逆序遍历已排序部分，在4的位置上找到合适的位置插入2。
7. 逆序遍历已排序部分，在3的位置上找到合适的位置插入2。
8. 已排序部分：2,3,4；未排序部分：10,12,1,5,6。
9. 重复步骤2~8，直到未排序部分的元素全部插入到已排序部分中。
10. 最终得到排好序的数组{1,2,3,4,5,6,10,12}。

示例二

对数组{1,2,3,4,5}进行插入排序。

1. 已排序部分：1；未排序部分：2,3,4,5。
2. 取出未排序部分的首位元素2。
3. 在1的位置上插入2。
4. 已排序部分：1,2；未排序部分：3,4,5。
5. 取出未排序部分的首位元素3。
6. 在2的位置上插入3。
7. 在1的位置上插入3。
8. 已排序部分：1,2,3；未排序部分：4,5。
9. 重复步骤2~8，直到未排序部分的元素全部插入到已排序部分中。
10. 最终得到排好序的数组{1,2,3,4,5}。

以上就是插入排序的完整攻略。希望能够对您有所帮助。