c++ - 为什么我的替代排序算法不起作用?
问题描述
我试图实现一个排序代码,所以我完全尝试了一些东西,而没有查看任何其他参考代码或任何东西。请告诉我为什么我的代码没有显示任何输出?它只是运行了一段时间,然后突然停止。
我想知道我哪里出错了。我想将任何数组作为输入,并按升序对其中的数字进行排序。所以我只是迭代了数组的吞吐量并比较了相邻的元素并交换了它们。然后我尝试使用它们的索引打印数字,但它没有在屏幕上打印任何内容。
#include <iostream>
using namespace std;
int main() {
int arr[6]={1,23,2,32,4,12};
int i=0;
while(i<6)
{
if(arr[i]>arr[i+1])
{
int x = arr[i];
arr[i]=arr[i+1];
arr[i+1]=x;
}
else
continue;
i++;
}
cout<<arr[0];
cout<<arr[1];
cout<<arr[2];
cout<<arr[3];
cout<<arr[4];
cout<<arr[5];
return 0;
}
我希望这些数字会按升序打印,但什么也没发生。还告诉我如何一次打印一个数组。谢谢
解决方案
您的排序算法不起作用,因为它只执行冒泡排序或插入排序的变体的一次。必须在循环周围再缠绕一个循环才能重复操作 N-1 次。
有多种方法可以解释为什么需要多次通过。这是一种解释。每当我们执行此步骤时:
if (arr[i] > arr[i+1])
{
int x = arr[i];
arr[i] = arr[i+1];
arr[i+1] = x;
}
我们将arr[i+1]
元素转移到arr[i]
位置。通过这样做,我们有效地跳过了arr[i+1]
元素。
这就是我的意思。假设arr[i]
称为x,arr[i+1]
称为y并arr[i+2]
称为z。我们从xyz开始,交换x和y来生成 yxz。但是在循环的下一次迭代中,我们比较了x和z并且忘记了y;x在数组中向前移动,向下推y。为什么这是个问题?因为y和z没有进行比较;并且这两个不一定按排序顺序!
假设我们有 { 3, 2, 0 }。我们比较 3 和 2,然后交换它们,得到 { 2, 3, 0}。然后我们继续比较 3 和 0:我们交换它们并得到 { 2, 0, 3 }。看到问题了吗?我们忽略了处理 2 和 0。这需要再次遍历数组。
有一系列算法通过重复扫描数组和交换项目来工作。我建议研究一下这个家族的常用算法:插入排序、选择排序和壳牌排序。还要看一下冒泡排序,以了解为什么它与与其密切相关的插入或选择排序相比是一种糟糕的算法。