README
¶
按照时间复杂度分类:
-
$O(N^2)$:
- 冒泡排序（Bubble sort）
- 选择排序（Selection sort）
- 插入排序（Insertion sort）
-
$O(Nlog_2N)$:
- 合并排序（Merge sort）
- 快速排序（Quick sort）
-
$O(N)$:
- 桶排序（Bucket sort）
- 计数排序（Counting sort）
- 基数排序（Radix sort）
方法：
- 选择排序：在i ~ n-1范围内，找到最小值，并将其于i位置元素进行交换；然后在i+1 ~ n-1范围上继续之前的操作
- 冒泡排序：在0 ~ i范围内，依次两两比较使偏大的数交换到后面的位置；然后在0 ~ i-1范围上继续之前的操作
- 插入排序：在0 ~ i范围已经是有序的了，将i+1位置的数据按照从右向左依次比较的方式，选择合适位置插入；然后使用相同的操作插入i + 2位置的数据
参考资料：
Documentation
¶
Index ¶
- func BubbleSort(arr []int)
- func BucketSort(nums []int) []int
- func CountingSort(nums []int, min, max int)
- func DoublyListBubbleSort[T constraints.Ordered](head *types.DListNode[T]) *types.DListNode[T]
- func DoublyListBubbleSortChangeValue[T constraints.Ordered](head *types.DListNode[T])
- func InsertionSort(arr []int)
- func ListBubbleSort[T constraints.Ordered](node *types.ListNode[T]) *types.ListNode[T]
- func ListBubbleSortChangValue[T types.Number](node *types.ListNode[T])
- func MergeSort(arr []int) []int
- func PartitionHead(arr []int) int
- func PartitionMedian(arr []int) int
- func PartitionMiddle(arr []int) int
- func PartitionTail(arr []int) int
- func QuickSort(arr []int, fn func([]int) int)
- func SelectionSort(arr []int)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func BubbleSort ¶
func BubbleSort(arr []int)
BubbleSort 冒泡排序（稳定排序；时间复杂度O(n^2)） 基本思路：一次遍历每一个元素，如果该元素比下一个元素大，就交换两个元素的位置。这样的过程 执行n-1即可达到有序的状态
func BucketSort ¶
BucketSort 桶排序 Constraints: 1 <= nums.length <= 5 * 10^4 -5 * 104 <= nums[i] <= 5 * 10^4
func CountingSort ¶
CountingSort 计数排序 The data table generated by the code at the tail of this file. +-------------------------------+---+---+---+---+---+---+ | INDEX | 0 | 1 | 2 | 3 | 4 | 5 | +-------------------------------+---+---+---+---+---+---+ | unsorted numbers | 3 | 2 | 1 | 0 | 2 | 2 | | counting array | 1 | 1 | 3 | 1 | | | | cumulative count | 1 | 2 | 5 | 6 | | | | Iteration in reverse order[2] | | | | | 2 | | | cumulative count | 1 | 2 | 4 | 6 | | | | Iteration in reverse order[2] | | | | 2 | 2 | | | cumulative count | 1 | 2 | 3 | 6 | | | | Iteration in reverse order[0] | 0 | | | 2 | 2 | | | cumulative count | 0 | 2 | 3 | 6 | | | | Iteration in reverse order[1] | 0 | 1 | | 2 | 2 | | | cumulative count | 0 | 1 | 3 | 6 | | | | Iteration in reverse order[2] | 0 | 1 | 2 | 2 | 2 | | | cumulative count | 0 | 1 | 2 | 6 | | | | Iteration in reverse order[3] | 0 | 1 | 2 | 2 | 2 | 3 | | cumulative count | 0 | 1 | 2 | 5 | | | +-------------------------------+---+---+---+---+---+---+
func DoublyListBubbleSort ¶
DoublyListBubbleSort 双向链表的冒泡排序算法（元素值为int类型） Constraints: 不可以修改元素值
func DoublyListBubbleSortChangeValue ¶
func DoublyListBubbleSortChangeValue[T constraints.Ordered](head *types.DListNode[T])
DoublyListBubbleSortChangeValue 双向链表的冒泡排序算法（元素值为int类型） Constraints: 可以修改元素值
func InsertionSort ¶
func InsertionSort(arr []int)
InsertionSort 插入排序（原地排序算法；稳定排序；时间复杂度O(n^2)） 基本思路：遍历每一个元素，如果该元素比上一个元素小，相邻元素依次交换， 直到该元素不再比上一个元素大
func ListBubbleSort ¶
ListBubbleSort 单向链表的冒泡排序算法（元素值为int类型） Constraints: 不修改元素字段值
func ListBubbleSortChangValue ¶
ListBubbleSortChangValue 单向链表的冒泡排序算法（元素值为int类型） Constraints: 可以修改元素字段值
func MergeSort ¶
MergeSort 合并排序算法，非原地排序算法（merge方法无法原地执行），稳定的排序算法 时间复杂度为nlogn 基本思路：将数组一分为二，每个子数组达成有序状态后，在进行合并，合并之后的数组达到整体有序
func QuickSort ¶
QuickSort 快速排序，原地排序算法，不稳定的排序算法 时间复杂度为nlogn（最坏的时间复杂度为n^2，取决于pivot的选取是否尽可能将数组平分） 基本思路：选择一个pivot，通过移动元素，达到pivot左侧的都小于它，右侧的均大约等于它； 整个数组按照pivot切分后，对每个小数组再次进行上述操作，直到每个小数组只剩下1个元素， 整个数组将达成有序的状态
func SelectionSort ¶
func SelectionSort(arr []int)
SelectionSort 选择排序（不稳定排序；时间复杂度O(n^2)）；优点是避免了不必要的元素交换 基本思路：遍历每一个元素，在该元素以及右侧寻找最小元素，如果找到了和当前元素交换位置， 直到遍历完整个数组
Types ¶
This section is empty.
Source Files