在不移动数组元素的情况下使用下标对数组进行排序
Sorting an array using subscripts without moving array elements
我必须在 C 语言中使用合并排序对非负整数数组进行排序，但有一个问题 - 我无法移动实际的数组元素，就像我有 {3,5,6,7,0, 4,1,2}，所需的输出应该是
第一个元素在下标：4
0 3 5
1 5 2
2 6 3
3 7 -1
4 0 6
5 4 1
6 1 7
7 2 0
看到原始输入的顺序如何保持不变，但在比较数字时只有键被交换了吗？到目前为止，我的主要功能是：
void Merge(int *A,int *L,int leftCount,int *R,int rightCount)
{
int i,j,k;
// i - to mark the index of left sub-array (L)
// j - to mark the index of right sub-array (R)
// k - to mark the index of merged sub-array (A)
i = 0; j = 0; k =0;
while(i<leftCount && j< rightCount)
{
if(L[i] <= R[j])
{
//something important;
i++;
}
else
{
//something important;
j++;
}
}
i=0;
j=0;
while(i < leftCount) A[k++] = L[i++]; //merge all input sequences without swapping initial order
while(j < rightCount) A[k++] = R[j++];
}
// Recursive function to sort an array of integers.
void MergeSort(int *A,int n)
{
int mid,i,k, *L, *R;
if(n < 2)
{
return;
}
mid = n/2; // find the mid index.
// create left and right subarrays
// mid elements (from index 0 till mid-1) should be part of left sub-array
// and (n-mid) elements (from mid to n-1) will be part of right sub-array
L = (int*)malloc(mid*sizeof(int));
R = (int*)malloc((n- mid)*sizeof(int));
for(i = 0;i<mid;i++) L[i] = A[i]; // creating left subarray
for(i = mid;i<n;i++) R[i-mid] = A[i]; // creating right subarray
MergeSort(L,mid); // sorting the left subarray
MergeSort(R,n-mid); // sorting the right subarray
Merge(A,L,mid,R,n-mid); // Merging L and R into A as sorted list.
free(L);
free(R);
}
我知道当合并排序时只有单个元素时，我必须将递归树底部的所有元素的索引初始化为-1。然后我必须相应地更改这些索引，因为我比较左数组和右数组的数组元素。但这就是我卡住的地方。我的教授告诉 class 使用链表——但我很难想象如何实现链表来实现这种索引。我不希望我的作业被别人完成，我只是希望有人用伪代码解释我应该如何去做，然后我可以自己编写实际代码。但是我很迷茫，如果这个问题问得不好，我很抱歉，但我在这里是全新的品牌，我吓坏了:(
创建一个 linked 项目列表，其中每个列表项目都具有每个数组项目的值和索引。因此，除了 prev/next 之外，linked 列表中的每个项目都是一个具有结构成员 uint value; 和 uint index; 的结构。
通过迭代数组并为每个数组元素预填充 link-list，将新的 linked-list 项目附加到列表并设置值和索引每个 linked-list 项目添加到列表时的数组元素。
使用预先填充的 linked 列表作为实际数组值的 "proxy"，并将 linked 列表作为原始数组进行排序。 IE。不是基于 myArray[i] 排序，而是基于 currentLinkListItem.value .
排序
好的。让我们从一个简单的例子开始，一个包含 4 个要排序的元素的列表，让我们通过链接列表来了解您的函数需要做什么以及它是如何做的：
#->[3]->[1]->[4]->[2]->$
好的，这里 # 是您指向第一个元素的指针，在本例中为 [3]，它有一个指向第二个元素的指针，依此类推。我将使用 ->$ 作为空指针（不指向任何东西）和 ->* 作为“我不关心”指针（可能存在指针，但想在列表）
我们现在执行多次传递以将它们合并到一个排序列表中。
这是第一遍，所以我们将其视为有多个长度为 1:
的列表
#->* [3]->* [1]->* [4]->* [2]->*
实际上，这些现在仍然保持联系，但这是概念模型。
那么这个时候我们需要什么'know'？
- 列表#1 之前的列表末尾
- 引用列表 #1 的开头
- 引用列表 #2 的开头
- 引用列表 #2 后的项目
然后我们将两个子列表 (2) 和 (3) 合并到 (1) 的末尾，通过取列表头部的最小值，分离它，并将其修改为 (1)，移动到该列表中的下一个值（如果存在）
概念
//sublists length 1. we'll work on the first pair
#->* [3]->* [1]->* [4]->* [2]->*
//smallest element from sublists added to new sublist
#->* [3]->* [4]->* [2]->* //
[1]->*
//above repeated until sublists are both exhausted
#->* [4]->* [2]->*
[1]->[3]->*
//we now have a sorted sublist
#->* [1]->[3]->* [4]->* [2]->*
实际
//(1-4) are pointers to the list as per description above
#->[3]->[1]->[4]->[2]->$
| | | |
1 2 3 4
//set the end of the lists (2) and (3) to point to null, so
//when we reach this we know we have reached the end of the
//sublist (integrity remains because of pointers (1-4)
#->* [3]->$ [1]->$ [4]->[2]->$
| | | |
1 2 3 4
//the smallest (not null) of (2) and (3) is referenced by (1),
//update both pointers (1) and (2) or (3) to point to the next
//item
#->[1]->* [3]->$ $ [4]->[2]->$
| | | |
1 2 3 4
//repeat until both (2) and (3) point to null
#->[1]->[3]->* $ $ [4]->[2]->$
| | | |
1 2 3 4
我们现在有一个包含第一个子列表的链表。现在，我们跟踪 (1)，并继续从 (4) 开始的第二对子列表，重复该过程。
一旦(2)、(3)、(4)都为null，我们就完成了pass。我们现在已经对子列表进行了排序，并且又是一个单链表：
#->[1]->[3]->[2]->[4]->$ $ $ $
| | | |
1 2 3 4
现在我们做同样的事情，只是子列表的长度是原来的两倍。 （并重复）
当子列表长度 >= 链表长度时，列表被排序。
在此期间我们实际上没有移动任何数据，只是修改了链表中项目之间的链接。
这应该让您清楚地知道您需要从这里做什么。
我已将其扩展到一些实际代码中：
我用 python 编写了它，因此它满足了您对伪代码的需求，因为它不是您正在编写的语言的代码。
具有附加注释的相关函数：
def mergesort(unsorted):
#dummy start node, python doesn't have pointers, but we can use the reference in here in the same way
start = llist(None)
start.append(unsorted)
list_length = unsorted.length()
sublist_length = 1
#when there are no sublists left, we are sorted
while sublist_length < list_length:
last = start
sub_a = start.next
#while there are unsorted sublists left to merge
while sub_a:
#these cuts produce our sublists (sub_a and sub_b) of the correct length
#end is the unsorted content
sub_b = sub_a.cut(sublist_length)
end = sub_b.cut(sublist_length) if sub_b else None
#I've written this so is there are any values to merge, there will be at least one in sub_a
#This means I only need to check sub_a
while sub_a:
#sort the sublists based on the value of their first item
sub_a, sub_b = sub_a.order(sub_b)
#cut off the smallest value to add to the 'sorted' linked list
node = sub_a
sub_a = sub_a.cut(1)
last = last.append(node)
#because we cut the first item out of sub_a, it might be empty, so swap the references if so
#this ensures that sub_a is populated if we want to continue
if not sub_a:
sub_a, sub_b = sub_b, None
#set up the next iteration, pointing at the unsorted sublists remaining
sub_a = end
#double the siblist size for the next pass
sublist_length *=2
return start.next
说到链表：
typedef struct ValueNode
{
struct ValueNode* next;
int* value;
} ValueNode;
typedef struct ListNode
{
struct ListNode* next;
ValueNode* value;
} ListNode;
单链表就够了...
现在首先是合并算法：
ValueNode* merge(ValueNode* x, ValueNode* y)
{
// just assuming both are != NULL...
ValueNode dummy;
ValueNode* xy = &dummy;
while(x && y)
{
ValueNode** min = *x->value < *y->value ? &x : &y;
xy->next = *min;
*min = (*min)->next;
xy = xy->next;
}
// just append the rest of the lists - if any...
if(x)
{
xy->next = x;
}
else if(y)
{
xy->next = y;
}
return dummy.next;
}
假人只是为了不必在循环中检查是否为 NULL...
现在让我们使用它：
int array[] = { 3, 5, 6, 7, 0, 4, 1, 2 };
ListNode head;
ListNode* tmp = &head;
for(unsigned int i = 0; i < sizeof(array)/sizeof(*array); ++i)
{
// skipping the normally obligatory tests for result being 0...
ValueNode* node = (ValueNode*) malloc(sizeof(ValueNode));
node->value = array + i;
node->next = NULL;
tmp->next = (ListNode*) malloc(sizeof(ListNode));
tmp = tmp->next;
tmp->value = node;
}
tmp->next = NULL;
现在我们已经建立了一个列表列表，每个列表包含一个元素。现在我们将两个后续列表成对合并。需要注意的是：如果我们将两个列表合并为一个，保留它作为新的头部，然后将下一个列表合并到其中，等等，那么我们就实现了选择排序！因此，我们需要确保在合并所有其他数组之前，我们不会触及已经合并的数组。这就是为什么下一步看起来有点复杂...
while(head.next->next) // more than one single list element?
{
tmp = head.next;
while(tmp)
{
ListNode* next = tmp->next;
if(next)
{
// we keep the merged list in the current node:
tmp->value = merge(tmp->value, next->value);
// and remove the subsequent node from it:
tmp->next = next->next;
free(next);
}
// this is the important step:
// tmp contains an already merged list
// -> we need to go on with the NEXT pair!
tmp = tmp->next;
// additionally, if we have an odd number of lists,
// thus at the end no next any more, we set tmp to NULL,
// too, so we will leave the loop in both cases...
}
}
终于可以打印结果了；请注意，在您的外部链表中我们只剩下一个链表：
ValueNode* temp = head.next->value;
while(temp)
{
printf("%d\n", *temp->value);
temp = temp->next;
}
还缺少释放分配的内存 - 我会把它留给你...
我必须在 C 语言中使用合并排序对非负整数数组进行排序，但有一个问题 - 我无法移动实际的数组元素，就像我有 {3,5,6,7,0, 4,1,2}，所需的输出应该是
第一个元素在下标：4
0 3 5
1 5 2
2 6 3
3 7 -1
4 0 6
5 4 1
6 1 7
7 2 0
看到原始输入的顺序如何保持不变，但在比较数字时只有键被交换了吗？到目前为止，我的主要功能是：
void Merge(int *A,int *L,int leftCount,int *R,int rightCount)
{
int i,j,k;
// i - to mark the index of left sub-array (L)
// j - to mark the index of right sub-array (R)
// k - to mark the index of merged sub-array (A)
i = 0; j = 0; k =0;
while(i<leftCount && j< rightCount)
{
if(L[i] <= R[j])
{
//something important;
i++;
}
else
{
//something important;
j++;
}
}
i=0;
j=0;
while(i < leftCount) A[k++] = L[i++]; //merge all input sequences without swapping initial order
while(j < rightCount) A[k++] = R[j++];
}
// Recursive function to sort an array of integers.
void MergeSort(int *A,int n)
{
int mid,i,k, *L, *R;
if(n < 2)
{
return;
}
mid = n/2; // find the mid index.
// create left and right subarrays
// mid elements (from index 0 till mid-1) should be part of left sub-array
// and (n-mid) elements (from mid to n-1) will be part of right sub-array
L = (int*)malloc(mid*sizeof(int));
R = (int*)malloc((n- mid)*sizeof(int));
for(i = 0;i<mid;i++) L[i] = A[i]; // creating left subarray
for(i = mid;i<n;i++) R[i-mid] = A[i]; // creating right subarray
MergeSort(L,mid); // sorting the left subarray
MergeSort(R,n-mid); // sorting the right subarray
Merge(A,L,mid,R,n-mid); // Merging L and R into A as sorted list.
free(L);
free(R);
}
我知道当合并排序时只有单个元素时，我必须将递归树底部的所有元素的索引初始化为-1。然后我必须相应地更改这些索引，因为我比较左数组和右数组的数组元素。但这就是我卡住的地方。我的教授告诉 class 使用链表——但我很难想象如何实现链表来实现这种索引。我不希望我的作业被别人完成，我只是希望有人用伪代码解释我应该如何去做，然后我可以自己编写实际代码。但是我很迷茫，如果这个问题问得不好，我很抱歉，但我在这里是全新的品牌，我吓坏了:(
创建一个 linked 项目列表，其中每个列表项目都具有每个数组项目的值和索引。因此，除了 prev/next 之外，linked 列表中的每个项目都是一个具有结构成员 uint value; 和 uint index; 的结构。
通过迭代数组并为每个数组元素预填充 link-list，将新的 linked-list 项目附加到列表并设置值和索引每个 linked-list 项目添加到列表时的数组元素。
使用预先填充的 linked 列表作为实际数组值的 "proxy"，并将 linked 列表作为原始数组进行排序。 IE。不是基于 myArray[i] 排序，而是基于 currentLinkListItem.value .
好的。让我们从一个简单的例子开始，一个包含 4 个要排序的元素的列表，让我们通过链接列表来了解您的函数需要做什么以及它是如何做的：
#->[3]->[1]->[4]->[2]->$
好的，这里 # 是您指向第一个元素的指针，在本例中为 [3]，它有一个指向第二个元素的指针，依此类推。我将使用 ->$ 作为空指针（不指向任何东西）和 ->* 作为“我不关心”指针（可能存在指针，但想在列表）
我们现在执行多次传递以将它们合并到一个排序列表中。
这是第一遍，所以我们将其视为有多个长度为 1:
#->* [3]->* [1]->* [4]->* [2]->*
实际上，这些现在仍然保持联系，但这是概念模型。
那么这个时候我们需要什么'know'？
- 列表#1 之前的列表末尾
- 引用列表 #1 的开头
- 引用列表 #2 的开头
- 引用列表 #2 后的项目
然后我们将两个子列表 (2) 和 (3) 合并到 (1) 的末尾，通过取列表头部的最小值，分离它，并将其修改为 (1)，移动到该列表中的下一个值（如果存在）
概念
//sublists length 1. we'll work on the first pair
#->* [3]->* [1]->* [4]->* [2]->*
//smallest element from sublists added to new sublist
#->* [3]->* [4]->* [2]->* //
[1]->*
//above repeated until sublists are both exhausted
#->* [4]->* [2]->*
[1]->[3]->*
//we now have a sorted sublist
#->* [1]->[3]->* [4]->* [2]->*
实际
//(1-4) are pointers to the list as per description above
#->[3]->[1]->[4]->[2]->$
| | | |
1 2 3 4
//set the end of the lists (2) and (3) to point to null, so
//when we reach this we know we have reached the end of the
//sublist (integrity remains because of pointers (1-4)
#->* [3]->$ [1]->$ [4]->[2]->$
| | | |
1 2 3 4
//the smallest (not null) of (2) and (3) is referenced by (1),
//update both pointers (1) and (2) or (3) to point to the next
//item
#->[1]->* [3]->$ $ [4]->[2]->$
| | | |
1 2 3 4
//repeat until both (2) and (3) point to null
#->[1]->[3]->* $ $ [4]->[2]->$
| | | |
1 2 3 4
我们现在有一个包含第一个子列表的链表。现在，我们跟踪 (1)，并继续从 (4) 开始的第二对子列表，重复该过程。
一旦(2)、(3)、(4)都为null，我们就完成了pass。我们现在已经对子列表进行了排序，并且又是一个单链表：
#->[1]->[3]->[2]->[4]->$ $ $ $
| | | |
1 2 3 4
现在我们做同样的事情，只是子列表的长度是原来的两倍。 （并重复）
当子列表长度 >= 链表长度时，列表被排序。
在此期间我们实际上没有移动任何数据，只是修改了链表中项目之间的链接。
这应该让您清楚地知道您需要从这里做什么。
我已将其扩展到一些实际代码中：
我用 python 编写了它，因此它满足了您对伪代码的需求，因为它不是您正在编写的语言的代码。
具有附加注释的相关函数：
def mergesort(unsorted):
#dummy start node, python doesn't have pointers, but we can use the reference in here in the same way
start = llist(None)
start.append(unsorted)
list_length = unsorted.length()
sublist_length = 1
#when there are no sublists left, we are sorted
while sublist_length < list_length:
last = start
sub_a = start.next
#while there are unsorted sublists left to merge
while sub_a:
#these cuts produce our sublists (sub_a and sub_b) of the correct length
#end is the unsorted content
sub_b = sub_a.cut(sublist_length)
end = sub_b.cut(sublist_length) if sub_b else None
#I've written this so is there are any values to merge, there will be at least one in sub_a
#This means I only need to check sub_a
while sub_a:
#sort the sublists based on the value of their first item
sub_a, sub_b = sub_a.order(sub_b)
#cut off the smallest value to add to the 'sorted' linked list
node = sub_a
sub_a = sub_a.cut(1)
last = last.append(node)
#because we cut the first item out of sub_a, it might be empty, so swap the references if so
#this ensures that sub_a is populated if we want to continue
if not sub_a:
sub_a, sub_b = sub_b, None
#set up the next iteration, pointing at the unsorted sublists remaining
sub_a = end
#double the siblist size for the next pass
sublist_length *=2
return start.next
说到链表：
typedef struct ValueNode
{
struct ValueNode* next;
int* value;
} ValueNode;
typedef struct ListNode
{
struct ListNode* next;
ValueNode* value;
} ListNode;
单链表就够了...
现在首先是合并算法：
ValueNode* merge(ValueNode* x, ValueNode* y)
{
// just assuming both are != NULL...
ValueNode dummy;
ValueNode* xy = &dummy;
while(x && y)
{
ValueNode** min = *x->value < *y->value ? &x : &y;
xy->next = *min;
*min = (*min)->next;
xy = xy->next;
}
// just append the rest of the lists - if any...
if(x)
{
xy->next = x;
}
else if(y)
{
xy->next = y;
}
return dummy.next;
}
假人只是为了不必在循环中检查是否为 NULL...
现在让我们使用它：
int array[] = { 3, 5, 6, 7, 0, 4, 1, 2 };
ListNode head;
ListNode* tmp = &head;
for(unsigned int i = 0; i < sizeof(array)/sizeof(*array); ++i)
{
// skipping the normally obligatory tests for result being 0...
ValueNode* node = (ValueNode*) malloc(sizeof(ValueNode));
node->value = array + i;
node->next = NULL;
tmp->next = (ListNode*) malloc(sizeof(ListNode));
tmp = tmp->next;
tmp->value = node;
}
tmp->next = NULL;
现在我们已经建立了一个列表列表，每个列表包含一个元素。现在我们将两个后续列表成对合并。需要注意的是：如果我们将两个列表合并为一个，保留它作为新的头部，然后将下一个列表合并到其中，等等，那么我们就实现了选择排序！因此，我们需要确保在合并所有其他数组之前，我们不会触及已经合并的数组。这就是为什么下一步看起来有点复杂...
while(head.next->next) // more than one single list element?
{
tmp = head.next;
while(tmp)
{
ListNode* next = tmp->next;
if(next)
{
// we keep the merged list in the current node:
tmp->value = merge(tmp->value, next->value);
// and remove the subsequent node from it:
tmp->next = next->next;
free(next);
}
// this is the important step:
// tmp contains an already merged list
// -> we need to go on with the NEXT pair!
tmp = tmp->next;
// additionally, if we have an odd number of lists,
// thus at the end no next any more, we set tmp to NULL,
// too, so we will leave the loop in both cases...
}
}
终于可以打印结果了；请注意，在您的外部链表中我们只剩下一个链表：
ValueNode* temp = head.next->value;
while(temp)
{
printf("%d\n", *temp->value);
temp = temp->next;
}
还缺少释放分配的内存 - 我会把它留给你...