关于插入排序算法的疑问

Question

为什么这个插入排序算法这里是p--?为什么a【p+1】＝t?

Answer 1

写在前面：你的第一个for循环和第二个for循环其实是并列的，并不是嵌套关系，所以要注意缩进，不然会有很大误导性
1：为什么p--?
解:因为你这是用插入排序实现升序，在第二个for循环中，对于每个取值i，a[i]之前的i个元素其实是已经排好序了，while的逻辑就是从第a[i-1]个元素往a[0]方向进行比较，找到第一个比a[i]自身小或者相等的元素，这里p就相当于一个指针的作用，将a[p]与a[i]比较，如果a[p]比a[i]大，当然要继续往前找（不然前面可能还有比a[i]大的元素，那不就不是升序排列了吗），所以p--。
2：为什么a[p+1]=t
解：while循环其中一个打破循环的条件是a[i] > =a[p], 此时a[p+1]这个位置其实可以认为已经空出来了，因为a[i]之前元素已经升序，所以a[p]之前不可能有比a[i]更小的元素，所以直接把a[i]放在位置p+1就可以了。

帮助：可以考虑一个例子，例如已经有一个序列，1、3、9，怎么往里面插入一个元素2 ？
拓展提问：while循环里面是否可以写为t<=a[p]？提示：排序的稳定性