如何在不使用 Collection 方法的情况下对列表进行排序?
最佳答案
路线图
- > Wikipedia/Sorting algorithm
- 简单的二次算法
- > Bubble sort - 初学者友好
- > Selection sort - 非常直观
- > Insertion sort - 也很直观
- 基本的基于比较的排序
- > Merge sort - 稍微高级一些
- > Quick sort - 暂时跳过这个,稍后再看
- 基本非比较排序
- > Counting sort - 理解很重要
- 简单的二次算法
你的第一个排序算法
我认为计数排序是最好的入门算法。阅读并尝试理解它,然后按如下方式编写您自己的实现:
- 生成 0..9 之间的 1000 个随机数(使用
java.util.Random
填充int[]
) - 使用计数排序对它们进行排序。
一旦你这样做,你就会意识到当你可以利用数字的某些属性时排序是多么简单(在这种情况下,它们介于 0..9 之间)。
你的第二个排序算法
对于您的下一个实现,选择排序是一种很好的直观排序算法。这是一种比较排序,不对数字范围做任何假设。现实生活中很多人都用这个算法排序:
- 如果有一些可供选择的选择,我们会寻找最好的并首先挑选它。
- 现在最好的已经出来了,所以我们从其余的中寻找第二好的。
- 然后我们寻找第三好的......等等
剩下的旅程
您可能想要实现其他二次算法只是为了很好地掌握基础知识,但下一步将是学习递归,特别是分而治之算法。
如果不首先了解基本递归,您不会想直接进入归并排序/快速排序,因为它可能会让人不知所措。
进行通常的递归练习、阶乘、斐波那契等。如果您需要指导,请向 stackoverflow 寻求指导。甚至可能已经有关于学习递归的问题和很好的答案。
顺路旅行
您可能想要实现合并排序的合并部分,甚至在您完全理解递归之前。这是一个很有教育意义的练习:
- 给定一个有序数组 A 和一个有序数组 B,将两者合并为一个有序数组
- 利用 A 和 B 已经排序的事实
关于java - 不使用 Collection 方法对列表进行排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2844215/