algorithm

✏️Data Structures and Algorithms in JAVA.

Table of Contents

• Sort
  • O(n²)
  • O(nlogn)
  • O(n)
• Search

Sort

refer to LeetBook

O(n²)

算法	题解	时间复杂度	空间复杂度	稳定性
冒泡排序	Java	O(n2)	O(1)	稳定
选择排序	Java	O(n2)	O(1)	不稳定
插入排序	Java	O(n2)	O(1)	稳定

冒泡排序

冒泡排序有两种优化方式：

• 记录当前轮次是否发生过交换，没有发生过交换表示数组已经有序；
• 记录上次发生交换的位置，下一轮排序时只比较到此位置。

选择排序

选择排序可以演变为二元选择排序：

• 二元选择排序：一次遍历选出两个值——最大值和最小值；
• 二元选择排序剪枝优化：当某一轮遍历出现最大值和最小值相等，表示数组中剩余元素已经全部相等。

插入排序

插入排序有两种写法：

• 交换法：新数字通过不断交换找到自己合适的位置；
• 移动法：旧数字不断向后移动，直到新数字找到合适的位置。

相同点

• 时间复杂度都是 O(n²)，空间复杂度都是 O(1)。

不同点

• 选择排序是不稳定的，冒泡排序、插入排序是稳定的；
• 在这三个排序算法中，选择排序交换的次数是最少的；
• 在数组几乎有序的情况下，插入排序的时间复杂度接近线性级别。

O(nlogn)

算法	题解	时间复杂度	空间复杂度	稳定性
希尔排序	Java	O(n1.3)	O(1)	不稳定
堆排序	Java	O(nlogn)	O(1)	不稳定
快速排序	Java	O(nlogn)	O(logn)	不稳定
归并排序	Java	O(nlogn)	O(n)	稳定

希尔排序

• 希尔排序是一个承上启下的算法，通过交换间隔较远的元素，使得一次交换能消除一个以上的逆序对，打破了在空间复杂度为 O(1) 的情况下，时间复杂度 O(n²) 的魔咒。它启发出了后续一系列时间复杂度为 O(nlogn)，空间复杂度为 O(1) 的排序算法。
• 希尔排序本质上是插入排序的优化，先对间隔较大的元素进行插入排序，完成宏观调控，然后逐步缩小间隔，最后一轮一定是间隔为 1 的排序，也就是插入排序。间隔在希尔排序中被称为「增量」，增量序列不同，希尔排序的效率也不同。

堆排序

堆排序分为两步：初始化建堆、重建堆。排序过程是：

• 用数列构建出一个大顶堆，取出堆顶的数字；
• 调整剩余的数字，构建出新的大顶堆，再次取出堆顶的数字；
• 循环往复，完成整个排序。

快速排序

快速排序算法是面试中考察的重点，也是应用最广泛的排序算法。排序过程是：

• 从数组中取出一个数，称之为基数（pivot）；
• 遍历数组，将比基数大的数字放到它的右边，比基数小的数字放到它的左边。遍历完成后，数组被分成了左右两个区域；
• 将左右两个区域视为两个数组，重复前两个步骤，直到排序完成。

快速排序中最重要的是分区算法，最常用的分区算法是双指针分区算法，优点是一次交换可以完成两个数的分区。

归并排序

• 归并排序分为两步：二分拆数组、不断合并两个有序列表。
• 归并的优化主要在于减少临时空间的开辟。
• 不存在空间复杂度为 O(1) 的归并排序。

相同点

• 平均时间复杂度都在 O(n) 到 O(n²) 之间。

不同点

• 希尔排序、堆排序、快速排序是不稳定的，归并排序是稳定的。
• 希尔排序的平均复杂度界于 O(n) 到 O(n²) 之间，普遍认为它最好的时间复杂度为 O(n^1.3)，希尔排序的空间复杂度为 O(1)；堆排序的时间复杂度为 O(nlogn)，空间复杂度为 O(1)；快速排序的平均时间复杂度为 O(nlogn)，平均空间复杂度为 O(logn)；归并排序的时间复杂度是 O(nlogn)，空间复杂度是 O(n)。

O(n)

算法	题解	时间复杂度	空间复杂度	稳定性
计数排序	Java	O(n+k)	O(n+k)	稳定
基数排序	Java	O(d(n+k))	O(n+k)	稳定
桶排序	Java	O(n)	O(n)	稳定

Search

算法	题解	时间复杂度	空间复杂度
二分查找	Java	O(logn)	O(1)