我注意到了很多对algo返回升序数组进行排序的教程。显然,这涉及到他们的搜索算法实现,该算法也以排序的升序数组作为输入。
排序/搜索的升序要求只是作为学习算法问题解决的标准吗?
为什么不实现一个搜索算法,让它接受升序或降序数组?
例如,输出降序数组的插入排序算法仍然是插入排序吗?换句话说,它们只是一般的方法,对其输出进行了小幅调整?
发布于 2021-09-15 03:12:40
排序算法只是一个通用的框架,供您处理。您可以根据需要按升序/降序、字典顺序(字符串)等方式对数组进行排序。它仍将被称为“插入排序”或“合并排序”或任何您正在使用的排序。
通常在教育平台上会显示升序,因为这是最常见或最基本的。没有其他原因。
你所说的搜索算法很可能是二进制搜索。你也可以在降序数组上执行二进制搜索!你只需要做一些细微的改变。你可以在这里了解到更多信息:https://en.wikipedia.org/wiki/Binary_search_algorithm还有一个降序的二进制搜索页面(和标准的一样快):https://www.geeksforgeeks.org/search-an-element-in-a-reverse-sorted-array/
发布于 2021-09-15 03:12:47
一般来说,从算法的角度来看,反向排序并不是非常有趣的。我们简单地用<
替换一些>
,这个问题显然与升序排序是对称的。
根据我的经验,一般来说,当人们说“按顺序”时,他们的意思是按升序排序。如果有人列出了数字5,6,7,我会说它们是按顺序排列的,如果他们列出的是7,6,5,我会说它们的顺序是相反的。
在代码方面,许多语言实现了一个比较器函数或接口来处理排序,因为排序的类型通常比具有明显排序逻辑的简单原语(数字、字符串)更复杂。因为只要你在一个有序的元素数组中有一个“左边的”和“右边的”的概念,算法仍然适用,所以通常写这样的东西(JS示例):
// Comparator function to sort in ascending order
function sortAscending(a, b) {
if (a > b) return 1; // return a positive number if a > b
if (a < b) return -1; // negative if b < a
return 0; // 0 if b == a
}
// Comparator function to sort in descending order
function sortDescending(a, b) {
return sortAscending(b, a); // look how easy it is to reverse
}
这些函数可以与(例如)内置的array#sort一起使用
[1,2,3].sort(sortDescending);
至于
为什么不实现一个搜索算法,让它接受升序或降序数组?
你当然可以。根据您的算法,您可能需要检查数组的顺序。这引入了性能和复杂性成本,这可能比让使用者按升序对数组排序更大。即使您的排序逻辑是一个完整的黑盒,您也可以反转结果列表。
https://stackoverflow.com/questions/69186611
复制相似问题