可以';在c#中使用插入排序不能理解一点
本文关键字:能理解 不能 一点 插入排序 可以 | 更新日期: 2023-09-27 17:54:50
这是一种插入排序算法
我理解将最大的否转发到下一个索引,但不理解当它向前移动时,它的上一个位置(索引(是如何被刚才比较的较小数字占据的,例如在列表[2,1]2中,按列表[j+1]=list[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;
}
这是在循环的最后一行中完成的。向前移动一个或多个(甚至零个(项目后,当前值将放在正确的位置。
例如,如果您已经将数组排序到最后一项,并且它看起来像这样:
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 ][]
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