十大java算法

算法1:快速排序

快速排序是由Tony Hall开发的一种排序算法。平均来说,对n个项目进行排序需要进行ο (n log n)次比较。在最坏的情况下,需要进行ο (N2)比较,但这种情况并不常见。事实上,快速排序通常比其他ο (n log n)算法快得多,因为其内部循环可以在大多数架构上高效实现。

快速排序使用分治策略将一个列表分成两个子列表。

算法步骤:

1从序列中选择一个元素,称为“pivot”。

2对数列重新排序,小于基准值的元素全部放在基准前面,大于基准值的元素全部放在基准后面(相同的数字可以在两边)。在这个分区退出后,基准位于系列的中间。这称为分区操作。

3.递归排序小于参考值的元素子系列和大于参考值的元素子系列。

递归的底限是序列的大小为零或一,这意味着它已经被永远排序了。虽然一直是递归的,但是这个算法总会退出,因为在每次迭代中,都会把至少一个元素放在最后一个位置。

算法2:堆排序算法

Heapsort是指利用堆的数据结构设计的一种排序算法。Heap是一种近似完整的二叉树结构,同时满足heap的性质:即子节点的键值或索引总是小于(或大于)其父节点。

堆排序的平均时间复杂度为ο (NLOGN)。

算法步骤:

创建一个堆H[0..n-1]

交换堆的头(最大值)和尾。

3.将堆的大小减少1,调用shift_down(0)将新数组的顶部数据调整到相应的位置。

4.重复步骤2,直到堆的大小为1。

算法3:合并排序

归并排序(台湾省译:Merge sort)是一种基于归并运算的有效排序算法。这个算法是分而治之的一个非常典型的应用。

算法步骤:

1.申请一个大小为两个排序序列之和的空间,这个空间用来存放合并后的序列。

2.设置两个指针,初始位置分别是两个排序序列的起始位置。

3.比较两个指针指向的元素,选择一个相对较小的元素放入合并空间,将指针移动到下一个位置。

4.重复步骤3,直到指针到达序列的末尾。

5.将另一个序列的所有剩余元素。