C语言实践:实现插入排序

开篇

本篇文章的题目来源是《编程珠玑》第11章【排序】的第一个小节。不知不觉，已经看到第11章了呀。

主体

想到排序，想必大家第一时间，想到的都会是下面的这种方式。

for i  = [1, n]for (j = i; j > 0 && x[j-1] > x[j]; j--)swap(j-1, j)

在上面的这段伪代码中，交换的逻辑被封装成了独立的swap方法，但其实把swap方法中用于交换的逻辑直接以内联的方式写到循环体内会更加有效率，于是就有了第二个小版本。

for i = [1, n]for (j = i; j > 0 && x[j-1] > x[j]; j--)t = x[j];x[j] = x[j-1];x[j-1] = t;

基于上面的逻辑，我们可以看到在代码中，我们总是给t赋予同样的值（x[i]的初始值）。所以，我们可以将两个含t的语句都移出循环体，这样可以进一步提升效率。

伪代码

for i = [1, n]t = x[i]for (j = i; j > 0 && x[j-1] > t; j--)x[j] = x[j-1]x[j] = t

其实上面这样的改动也是我之前没有想到的，也建议大家如果一时没有理解，便在纸上模拟一下这里比较的过程。这里附上我根据这里的伪代码实现的插入排序的具体逻辑。

#include <stdio.h>void isort3(int arr[], int n) {for (int i = 1; i < n; i++) {int t = arr[i];int j = i;while (j > 0 && arr[j - 1] > t) {arr[j] = arr[j - 1];j--;}arr[j] = t;}
}void printArr(int arr[], int n) {for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");
}int main() {int arr[] = { 12, 18, 9, 6, 32 };int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组: \n");printArr(arr, n);isort3(arr, n);printf("排序后数组: \n");printArr(arr, n);return 0;
}