java - 我的合并排序代码有什么问题?
问题描述
只是编写一些基本的合并排序代码,我无法弄清楚我的逻辑是否有问题。对我来说它应该可以正常工作。
因此,理想情况下,它应该按排序顺序打印出元素:1 2 8 11 17 19 25 50。
但是显示的输出是:8 2 11 1 17 19 25 50
我不明白这段代码有什么问题。我的逻辑有问题吗?
如果有人可以帮助我,那就太好了。对不起,如果这是一个非常愚蠢的问题要在这里问。
public class MergeSort
{
static final int arr[] = {8, 2, 19, 25, 11, 1, 17, 50};
static int sorted[] = new int[arr.length];
public static void main(String args[])
{
mergeSort(0, arr.length - 1);
display();
}
static void display()
{
for(int i=0; i<sorted.length; i++)
{
System.out.print(sorted[i] + " ");
}
}
static void mergeSort(int first, int last)
{
if(first < last)
{
int mid = (first + last)/2;
mergeSort(first, mid);
mergeSort(mid + 1, last);
merge(first, mid, last);
}
}
static void merge(int first, int mid, int last)
{
int ansIndex = 0;
int index1 = first;
int index2 = mid + 1;
while(index1 <= mid && index2 <= last)
if(arr[index1] < arr[index2])
{
sorted[ansIndex] = arr[index1];
index1++;
ansIndex++;
}
else if(arr[index2] < arr[index1])
{
sorted[ansIndex] = arr[index2];
index2++;
ansIndex++;
}
else
{
sorted[ansIndex] = arr[index1];
index1++; index2++; ansIndex++;
}
if(index1 <= mid)
while(index1 <= mid)
{
sorted[ansIndex] = arr[index1];
ansIndex++; index1++;
}
else if(index2 <= last)
while(index2 <= last)
{
sorted[ansIndex] = arr[index2];
index2++; ansIndex++;
}
}
}
解决方案
您的错误是使用相同的数组arr
并且sorted
在每一步都没有复制数据。
最简单的更正是将范围0..ansIndex
从范围复制sorted
到末尾的范围first..last
arr
merge
还display
应该显示arr
(sorted
只是临时缓冲区)
推荐阅读
- typescript - 使用 Typescript 和 React 三纤维的着色器
- angular - 使用 Angular 和 bootstrap 5 beta 找不到 VS 代码 CSS 类选择器
- eslint - 配置 Rider 以在解决方案工具窗口中的错误中显示 ESLint 错误/警告
- python - 有没有办法在熊猫中进行滚动排名?
- javascript - 如何从 require.context 获取完整路径?
- python - 在同一个 shell 中运行 python 文件
- angular - 无法使用打字稿在可观察的对象列表中使用过滤器
- apache-spark - 错误:运行 spark-submit 时缺少应用程序资源
- ruby-on-rails - 迁移到 Rails 6.1 后,使用 RSpec 不推荐使用 connection_config 警告
- python - python中简单RGB动画的问题