插入排序思路:
1.默认第一个数已经排好序了,从第二个数开始,向已经排好序的数组里面插入
2.从已排好序的最后一位开始扫描,如果大于要插入的数,则将后面的数整体后移,继续向前扫描,直到不大于或者序号小于0,则插入此处
3.继续下一个数插入,直到所有数都插入到数组中
如何实现整体后移?
实际上是从最后一位开始,若大于要插入的数,则令最后一位数向后移动一位,腾出一个空间
代码实现:
int[] arr = { 1, 9, 2, 4, 6, 7, 3 }; //i=1,从第二个数开始 for(int i = 1; i < arr.Length; i++) { int temp = arr[i]; int here = 0; //j=i-1表示从前面已排好序的最后一位开始 for(int j=i-1;j>=0 && arr[j] > temp; j--) { //此时j+1=i,也就是让最后一位移动到第i位 arr[j + 1] = arr[j]; //记录下要插入的位置编号 if (j >= 1) { here = j - 1; } } //此时here等于小于要插入值的序号,那么here+1就是要插入的序号 arr[here+1] = temp; }