33｜直接插入排序：为什么数据越有序，排序速度越快？

带哨兵的直接插入排序，思想就是利用数组中的第一个位置暂存待插入的元素而不使用临时变量，这样有一个好处是防止数组下标越界：即如果没有哨兵，for循环就会多一次判断数组下表有没有越界，所以使用数组下表能一定程度上提高效率。 以下为修改后代码 //直接插入排序（从小到大） template<typename T>//T代表数组元素类型 void InsertSort(T myarray[], int length) //myarray：要排序的数组元素，length：数组中元素数量 { if (length <= 1) //不超过1个元素的数组，没必要排序 return; for (int i = 2; i <= length; ++i) //从第2个元素（下标为2，因为第一个位置被当做哨兵位置了）开始比较 { if (myarray[i] < myarray[i - 1]) { myarray[0] = myarray[i]; //暂存myarray[i]值，防止后续移动元素时值被覆盖 int j; for (j = i - 1; myarray[j] > myarray[0]; --j) //检查所有前面排好序的元素，由于myarray[j]不可能比myarray[0]小，所以这里无需对数组下标进行额外判断 { myarray[j + 1] = myarray[j]; //所有大于temp的元素都向后移动 } //end for j myarray[j + 1] = myarray[0]; //复制数据到插入位置，注意j因为被减了1，这里加回来 } //end if } //end for i return; }