-2

这是一个插入排序算法

我理解将最大的 no 转发到下一个索引，但无法理解当它向前移动时，它的先前位置（索引）如何被刚刚比较的较小数字占据，例如在列表 [2,1] 2 移动到下一个索引列表 [ j+1]=列表[j]；但是 1 如何向后移动或移动到上一个索引

 //unsorted array   
int[] list = new int[] { 5, 2, 4, 6, 1 };   

// the key element being sorted   
int key;   
// 
//start looping starting from the second element  
for (int i = 1; i < list.Length; i++)   
{  
    key = list[i];//store the key 
    int j = i - 1;//get the previous index  
    //
    //loop until you meet a smaller number or 0 
    while (j >= 0 && list[j] > key)  
    { 
        //move the greater number forward  
        list[j + 1] = list[j];  
        // Decrementing  
        j--;   
    }  
    //set the key in the proper index  
    list[j + 1] = key; 
}
4

2 回答 2

1

这是在循环内的最后一行完成的。向前移动一个或多个（甚至零个）项目后，当前值被放置在正确的位置。

例如，如果您已将数组排序到最后一项，它看起来像这样：

2, 4, 5, 6, 1

值 1 被复制到key变量中，然后项被一一向前复制：

2, 4, 5, 6, -   <-  the empty slot here still contains 1, but it's unused
2, 4, 5, -, 6   <-  the empty slot here still contains 6, but it's unused
2, 4, -, 5, 6
2, -, 4, 5, 6
-, 2, 4, 5, 6

现在key变量中的值被放置在最后一项被复制的位置：

1, 2, 4, 5, 6

插入排序背后的理论是从一个数组中取出项目并插入到一个新数组中。您使用的实现仅使用单个数组，您可以将其视为已排序部分和未排序部分。已排序的部分从大小为零开始：

[][ 5, 2, 4, 6, 1 ]

对数组进行排序时，会从未排序的部分中挑选项目，并将其插入到已排序部分的正确位置。已排序部分增长，未排序部分缩小，直到未排序部分为空：

[ 5 ][ 2, 4, 6, 1 ]
[ 2, 5 ][ 4, 6, 1 ]
[ 2, 4, 5 ][ 6, 1 ]
[ 2, 4, 5, 6 ][ 1 ]
[ 1, 2, 4, 5, 6 ][]
于 2013-01-19T01:42:39.123 回答
0 
There are TWO lists/arrays
The declaration at the top...

int[] list = new int[] { 5, 2, 4, 6, 1 };

Says to make a list/array of integer format called X 
X being whatever name you give it...

In this case the lists/arrays are list/array I[] and list/array J[]

So it (most likely) could be READING from one list/array maybe the I[] list/array
and assigning the SORTED values into the other list/array maybe the J[] list/array
于 2013-01-19T01:33:23.753 回答