一，冒泡排序

冒泡排序是一种基本的排序算法，它的思想是从序列的开头开始，比较相邻的两个元素，如果前一个元素大于后一个元素，则交换它们。这样一轮比较下来，最大的数就会沉到序列的末尾。然后再从序列开头重新开始进行比较和交换操作，直到所有元素都排好序为止。

以下是 golang 实现冒泡排序的示例代码：

在该代码中，我们使用了两层循环。外层循环控制总共需要进行多少轮排序，内层循环则负责每一轮中相邻两个元素之间的比较和交换。

每一轮排序过程中，我们通过内层循环将当前未排序部分中最大的数沉底。具体地说，在第 i 轮排序时（i 从 0 开始），我们需要比较相邻的 n−i−1 个元素，将它们中最大的数放到序列末尾。

时间复杂度：O(n2)

空间复杂度：O(1)

稳定性：稳定

二，选择排序

选择排序是一种简单的排序算法，它的思想是从待排序序列中选择最小（或最大）的元素，将其放到序列的起始位置，然后再从剩余未排序元素中继续寻找最小（或最大）的元素，依次类推，直到所有元素都排好序。

以下是 golang 实现选择排序的示例代码：

在该代码中，我们使用了两层循环。外层循环控制总共需要进行多少轮排序，内层循环则负责在剩余未排序部分中寻找最小值。

每一轮排序过程中，我们通过内层循环遍历未排序部分，并记录下其中最小值所在索引。然后将该最小值与当前位置上的数交换。这样，在经过 n−1 轮比较之后，整个数组就会被排好序。

时间复杂度：O(n2)

空间复杂度：O(1)

稳定性：不稳定

三， 插入排序

插入排序是一种简单的排序算法，它的思想是将待排序序列分成已排序和未排序两部分，每次从未排序部分中取出一个元素，在已排序部分中找到合适的位置插入该元素，直到所有元素都被插入完毕。

以下是 golang 实现插入排序的示例代码：

jtemp
arr[i]temp

时间复杂度：O(n2)

空间复杂度：O(1)

稳定性：稳定

四， 快速排序

快速排序是一种常用的基于比较的排序算法，它的核心思想是通过选取一个基准值将待排序序列分成两部分，左半部分中所有元素小于等于基准值，右半部分中所有元素大于等于基准值。然后递归地对左右两个子序列进行排序。

以下是 golang 实现快速排序的示例代码：

在该代码中，我们使用了递归实现快速排序，并且采用了 Lomuto 分区方法。具体实现步骤如下：

  1. 选取枢轴（pivot）：选择待排序序列的第一个元素作为枢轴。
  2. 划分操作：将待排序序列分成两个子序列，左子序列中所有元素都小于等于枢轴，右子序列中所有元素都大于等于枢轴。
  3. 递归操作：对左右两个子序列进行快速排序，直至排序完成。

在划分操作中，我们从数组的两端开始查找比枢轴小和比枢轴大的元素，并交换它们的位置。当左右指针相遇时，将枢轴与当前位置进行交换即可完成一次划分。

时间复杂度：O(nlogn)

空间复杂度：O(logn)

稳定性：不稳定

五，哈希查找

哈希查找（Hash Search）是一种基于哈希表的查找算法，它通过将关键字映射到不同的桶中进行查找。在哈希表中，每个桶对应一个链表或者红黑树等数据结构，用于存储具有相同哈希值的元素。

以下是 golang 实现哈希查找的示例代码：

在该代码中，我们使用了哈希表来实现哈希查找。具体步骤如下：

  1. 创建哈希表：初始化大小为 size 的数组 table。
  2. 计算哈希值：将关键字通过某种哈希函数计算出对应的桶位置 index。
  3. 插入元素：将新的键值对插入到 table[index] 对应的链表头部。
  4. 查找元素：从 table[index] 对应的链表头开始遍历，查找是否存在对应的键值对。
  5. 删除元素：查找待删除节点的前一个节点 prev，将 prev.next 指向待删除节点的下一个节点。

时间复杂度：哈希表的查找、插入和删除操作时间复杂度均为 O(1)，但需要考虑哈希函数的性能和哈希冲突的处理。

空间复杂度：O(n)

稳定性：不稳定

六， 二叉查找树

二叉查找树（Binary Search Tree，简称 BST）是一种常用的数据结构，它具有以下特点：

  1. 左子树上所有节点的值均小于其父节点的值。
  2. 右子树上所有节点的值均大于其父节点的值。
  3. 左右子树也分别为二叉查找树。

在 golang 中实现一个二叉查找树可以使用如下代码：

在该代码中，我们使用 Node 结构体来表示二叉查找树的节点，其中包含一个 value 值和左右子节点指针。具体实现如下：

  1. 插入新元素：从根节点开始遍历 BST，如果当前节点为空，则创建一个新节点并返回；否则比较插入值与当前节点值的大小关系，选择向左子树或右子树递归插入。
  2. 查找元素是否存在：从根节点开始遍历 BST，如果当前节点为空，则说明未找到目标元素；否则比较查找值与当前节点值的大小关系，选择向左子树或右子树递归查找。
  3. 删除指定元素：从根节点开始遍历 BST，如果当前节点为空，则说明未找到目标元素；否则比较删除值与当前节点值的大小关系，选择向左子树或右子树递归删除。对于要删除的三种情况分别进行处理：没有子节点直接删除、只有一个子节点用该子节点替换、有两个子节点则将其替换为右子树中最小值，并在右子树中递归删除该最小值节点。

时间复杂度：插入、查找和删除操作的平均时间复杂度为 O(logn)，但在最坏情况下可能会退化成链表，时间复杂度为 O(n)。

空间复杂度：O(n)

稳定性：不稳定