这个插入排序算法不太明白

Question

public void sort(int[] data) {
        int temp;
        for(int i=1;i<data.length;i++){
            for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){
                SortUtil.swap(data,j,j-1);
            }
        }        
    }
我不太清楚 SortUtil.swap(data,j,j-1);这个句子的意思，请大家讲解一下，谢谢了！

Answer 1

这是java中的堆排序，首先看一下下面的例子你就会彻底明白了
堆排序：
　　package org.rut.util.algorithm.support;　　import org.rut.util.algorithm.SortUtil;　　/**　　* @author treeroot　　* @since 2006-2-2　　* @version 1.0　　*/　　public class HeapSort implements SortUtil.Sort　　{　　　/* (non-Javadoc)　　　* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])　　　*/　　　public void sort(int[] data) 　　　{　　　　MaxHeap h=new MaxHeap();　　　　h.init(data);　　　　for(int i=0;i h.remove();　　　　System.arraycopy(h.queue,1,data,0,data.length);　　　}　　　private static class MaxHeap　　　{ 　　　　void init(int[] data)　　　　{　　　　　this.queue=new int[data.length+1];　　　　　for(int i=0;i queue[++size]=data[i];　　　　　fixUp(size);　　　　}　　　}　　　private int size=0;　　　private int[] queue;　　　public int get() 　　　{　　　　return queue[1];　　　}　　　public void remove() 　　　{　　　　SortUtil.swap(queue,1,size--);　　　　fixDown(1);　　　}　　　//fixdown　　　private void fixDown(int k) 　　　{　　　　int j;　　　　while ((j = k << 1) <= size) 　　　　{　　　　　if (j < size && queue[j] j++; 　　　　　if (queue[k]>queue[j]) //不用交换　　　　　break;　　　　　SortUtil.swap(queue,j,k);　　　　　k = j;　　　　}　　　}　　　private void fixUp(int k) 　　　{　　　　while (k >1) 　　　　{　　　　　int j = k >>1;　　　　　if (queue[j]>queue[k])　　　　　break;　　　　　SortUtil.swap(queue,j,k);　　　　　k = j;　　　　}　　　}　　}

Answer 2

二楼的楼主的代码分明是插入排序么，而且标题也说明了，您怎么说这是堆排呢。关于SortUtil.swap(data,j,j-1);这个句子的意思就是要交换array中在j和j-1这两个位置的数据，估计是类似如下的代码：    public static <E> void swap(E[] array, int pos1, int pos2) {
        if (pos1 != pos2) {
            E tmp = array[pos1];
            array[pos1] = array[pos2];
            array[pos2] = tmp;
        }
    }

Answer 3

SortUtil.swap(data,j,j-1);的意思就是交换data[j]和data[j-1]两个元素的值
楼主所写的插入算法效率不是很高，因为每做一次交换动作至少移动3次数据，即3次执行赋值语句
请仔细观察一下，每次交换实质都是用data[i]和data[j]交换，所以没有必要进行交换，只需要进行移动操作
可以这样写：
public static void insertSort(int[] array)
{
    for (int i = 1;i < array.length;++i) {
int temp = array[i];
if (temp < array[i - 1]) {
    array[i] = array[i - 1];     int j =  i - 2;
    while ((j >= 0)&&(array[j] > temp)) {
array[j + 1] = array[j];
--j;
    }     array[j + 1] = temp;
}
    }
}
上面的算法时间复杂度要是楼主算法的时间复杂度的1/3，而且还可以减少由于频繁调用函数SortUtil.swap(data,j,j-1);所产生的开销（包括时间和空间）。

Answer 4

看源代码就清楚了：public static void swap(List<?> list, int i, int j) {
final List l = list;
l.set(i, l.set(j, l.get(i)));
    }
而E set(int index,E element)是用指定元素替换列表中指定位置的元素。
很明显，这个swap方法就是将i和j的值互换具体到你这个程序，就是如果data[j]<data[j-1]，就将data[j]和data[j-1]互换，这是典型的冒泡算法，最后将data数组中的值从小到大排序

Answer 5

SortUtil.swap(data,j,j-1);意思是交换数组data中第j个元素与第j-1个元素的位置