插入排序 有些地方想不明白 麻烦高手了！

Question

public static void charu(int a[])
{
int j;
for (int i = 1; i < a.length; i++)
{
int temp=a[i];
j=i-1;
while(j>=0&&a[j]<temp)
{
a[j+1]=a[j];这不是把数据都覆盖了嘛
j--;
}
a[j+1]=temp;//a[0]的值那 总也传不到a[0]里去
}
}
再有麻烦下把上面题目改下for循环
小弟学习时间不长，麻烦高手给细心讲讲

Answer 1

如果是要从小到大的顺序排序的话，这段代码有问题。while(j>=0&&a[j]<temp)应该是while(j>=0&&a[j]>temp)插入排序的思想是：将数组a[n]分成a[0..i-1]和a[i..n-1]两部分，其中a[0..i-1]是排序好的，不断的将a[j]属于a[i..n-1]插入a[0..i-1]，这样知道j=n-1。因为只有一个元素时数组是排序的，所以初始状态是从a[0]和a[1..n-1]两部分开始的。代码中外层for循环就是不断将a[j]属于a[i..n-1]的元素插入a[0..i-1]，内层while循环用于寻找a[j]的插入位置。a[j+1]=a[j]这句：待插入的元素是已经存入temp中，此时a[0..i-1]是排序的，要找到temp的插入位置，就从i-1向0方向找到第一个小于等于temp的元素位置，在此过程中将大于temp的元素依次后移一个位置。不存在数据覆盖，因为预留了一个temp所在的位置。改成for循环，把对应的while循环替换成下面for(j=i-1;j>=0&&a[j]>temp;j--)
    a[j+1]=a[j];

Answer 2

这是插入排序中的直接插入排序；
public static void charu(int a[])
{
int j;
for (int i = 1; i < a.length; i++)
{
int temp=a[i];//每趟将a[i]插入到它前面已排好的子序列中去。
j=i-1;
while(j>=0&&a[j]<temp)//前面较大的元素向后移动。
{
a[j+1]=a[j];这不是把数据都覆盖了嘛//不是前面较大的元素向后移动。j--;
}
a[j+1]=temp;//a[0]的值那 总也传不到a[0]里去//temp的值到达插入位置。
}
}
例如：32 26 87 72 26 17 8 40 
第一趟26 32 87 72 26 17 8 40 
第二趟 26 32 87 72 26 17 8 40 
第三趟：26 32 72 87 26 17 8 40 
第四趟：26 26 32 72 87 17 8 40
不再一一给出了。
其实for循环只是把j=i-1;
while(j>=0&&a[j]<temp)
改为for(j=i-1;j>-1&&a[j]>temp;j++)即可

Answer 3

楼主可以参考一下 注释也写比较清晰 加上2楼的分析 相信理解起来问题不大 for循环不用改package SuanFa;/**
 * 插入排序
 * @author xqh
 *
 */
public class InsertSort {
public static void main(String[] args) {
int[] arr = {2, 5, 6, 3, 1, 4};
InsertionSort(arr);//插入排序
for (int i : arr)
System.out.print(i + " ");//输出排序后的数组
}

/**
 * 插入排序算法（从小到大）
 * @param arr
 */
static void InsertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int itemToInsert = arr[i]; // 当前要插入的数
int j = i - 1;
while (j >= 0) {
if (itemToInsert < arr[j]) {
arr[j + 1] = arr[j]; // 覆盖后面的数，直到找到比当前要插入的数来得小的数
j--; // 下标往前移动
} else
break;
}
arr[j + 1] = itemToInsert; // 把当前要插入的数 放到合适的位置
}
}
}