一、概述
1、适用场景：对少量元素进行排序，当元素数量较多时，插入排序的效率低
2、算法过程的描述：现有n个无序的数，依次将第1，2，3……n个数插入到有序数列中，如下图所示：
二、算法导论代码
1、伪代码
注：伪代码中，数组下标从1开始，C++具体代码中，数组下标从0开始
2、伪代码的实现
#includeusing namespace std; bool insertion_sort(int array[], int array_length) { //按照从小到大排序 int key, i; for (int j = 1; j < array_length; ++j) { //j表示第j个将要插入到有序数列的数 key = array[j]; //使用key记录第j个数 i = j - 1; //使用i记录第j个数的前一个数的位置 while (i >= 0 && array[i] > key) { //只有 aj < a'j-1,才执行while循环(前j-1个数是有序的， a'0 ≤ a'1 …… ≤a'j-1) array[i + 1] = array[i]; //将a'0，a'1，a'2，…… a'j-1中大于aj的数向右移动一个位置 i = i - 1; //将i指向前一个数 } array[i + 1] = key; //如果执行了while循环，i+1表示第j个数将要插入的位置，将第j个数插入到有序数列中 } return true; } int main() { int array[10] = { 5,2,1,8,7,9,3,4,6,0 }; //初始化整型数组 insertion_sort(array, 10); //函数调用 for (int index = 0; index < 10; index++) //遍历数组 std::cout << array[index] << endl; return true; }
三、看伪代码前自己写的插入排序
#includeusing namespace std; bool insertion_sort(int array[], int array_length) { //和上述代码做比较，列出不足之处 for (int j = 1; j < array_length; ++j) { for (int i = j - 1; i >= 0; --i) { //当第j个数大于第j-1个数时，应该跳出循环，不应该继续循环，去比较第j个数和第j-2、j-3、……、0个数的值 if (array[i + 1] < array[i]) { //不跳出循环，增加了循环次数和比较次数 int temp = array[i + 1]; //每次满足比较条件后，都会进行数据交换，增加了交换次数 array[i + 1] = array[i]; array[i] = temp; } } } return true; } int main() { int array[10] = { 5,2,1,8,7,9,3,4,6,0 }; insertion_sort(array, 10); for (int index = 0; index < 10; index++) std::cout << array[index] << endl; return true; }
Original: https://www.cnblogs.com/asdzy/p/16500819.html
Author: 阿斯顿之意
Title: 2.1插入排序
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/683542/
转载文章受原作者版权保护。转载请注明原作者出处！