经典排序算法之插入排序

不得不说，排序，一个历史话题，目前已经有很多非常成熟的排序算法，虽然可能在 ACM 比赛中并不会让你具体实现一个排序算法，但是在面试当中，或者在和别人吹牛的过程中，口述，或者手撕一个排序算法。

插入排序

这个应该是 CLRS （算法导论）中介绍的第一个算法，其思想如下：

每次选择一个元素，并且将这个元素和整个数组中的所有元素进行比较，然后插入到合适的位置，图片演示如上，时间复杂度 O(n^2)，C++ 代码如下：

void insertion_sort(int arr[], int length)
{int i,j;for (i = 1; i < length; i++) {int tmp = arr[i];for (j = i; j > 0 && arr[j - 1] > tmp; j--) {arr[j] = arr[j - 1];}arr[j] = tmp;}
}

 今天的文章分享就到这里了，希望对大家的学习和工作有所帮助！