拍卖网站模板,图片比较多的网站怎么做,北京低价网站建设,wordpress邮件失败算法编程题-排序 比较型排序算法冒泡排序选择排序插入排序希尔排序堆排序快速排序归并排序 非比较型排序算法计数排序基数排序 本文将对七中经典比较型排序算法进行介绍#xff0c;并且给出golang语言的实现#xff0c;还包括基数排序、计数排序等非比较型的算法的介绍和实现… 算法编程题-排序 比较型排序算法冒泡排序选择排序插入排序希尔排序堆排序快速排序归并排序 非比较型排序算法计数排序基数排序 本文将对七中经典比较型排序算法进行介绍并且给出golang语言的实现还包括基数排序、计数排序等非比较型的算法的介绍和实现。 比较型排序算法
所谓的比较型排序算法就是算法中会使用数据之间的比较只能数组保存的是能相关比较大小的数据即可使用该类算法相比于非比较型排序算法适用面更广。 在实现上进行了一定的封装支持泛型和自定义排序规则默认传入一个比较函数less按照less指定的小于关系进行“从小到大”排序。抽象接口代码如下
type Sorter[T any] struct {less func(item1, item2 T) bool
}func NewSorter[T any](less func(item1, item2 T) bool) *Sorter[T] {return Sorter[T]{less: less}
}冒泡排序
冒泡排序如其名就是排序的过程和冒泡有点像。一个气泡从水底浮向水面其体积是越来越大的。那么同理在排序的过程中也可以让一个个大的元素浮上去从而完成整个的排序。代码实现如下
// BubbleSort 冒泡排序时间复杂度O(n^2) 空间复杂度O(1), 稳定
func (s *Sorter[T]) BubbleSort(arr []T) {n : len(arr)for i : 0; i n; i {var bubbleFlag bool // 是否有冒泡for j : i; j1 n; j {if s.less(arr[j1], arr[j]) {arr[j], arr[j1] arr[j1], arr[j]bubbleFlag true}}if !bubbleFlag { // 无冒泡说明已经排序完成提前退出break}}
}冒泡排序时间复杂度是 O ( n 2 ) O(n^2) O(n2)空间复杂度为 O ( 1 ) O(1) O(1)。其是一种稳定的排序算法。在实现上可以记录一个标志表明此一轮有没有发生冒泡如果没有说明数组已经完全有序可以以前退出。
选择排序
选择排序同样也是人如其名在每一轮中选择剩余数组中的最小值放入一个位置经过n轮完成排序。实现代码如下
// SelectSort 选择排序时间复杂度(n ^ 2), 空间复杂度:O(1)不稳定
func (s *Sorter[T]) SelectSort(arr []T) {n : len(arr)for i : 0; i n; i {minPtr : ifor j : i 1; j n; j {if s.less(arr[j], arr[minPtr]) {minPtr j}}arr[minPtr], arr[i] arr[i], arr[minPtr]}
}选择排序时间复杂度 O ( n 2 ) O(n^2) O(n2)空间复杂度为 O ( 1 ) O(1) O(1)是一种不稳定的排序算法。
插入排序
插入排序的排序过程为维护一个有序序列然后将待排序的数字找到一个合适的位置然后插入进去这样还是一个有序序列依次将所有元素完成这一个操作即可完成数组的排序。实现代码如下
// InsertSort 插入排序时间复杂度:O(n^2) 空间复杂度:O(1), 稳定
func (s *Sorter[T]) InsertSort(arr []T) {n : len(arr)for i : 1; i n; i {for j : i; j 0; j-- {if s.less(arr[j], arr[j-1]) {arr[j], arr[j-1] arr[j-1], arr[j]} else {break}}}
}插入排序的时间复杂度平均为 O ( n 2 ) O(n^2) O(n2)但是对于一个基本有序的数组进行排序时间复杂度可以达到 O ( n ) O(n) O(n)空间复杂度为 O ( 1 ) O(1) O(1)是一种稳定的排序算法。 优化插入排序可以从两个方面入手减少找位置的时间或者移动元素的时间每一轮这两个的时间都是 O ( n ) O(n) O(n)级别的前者可以通过二分查找来优化后者可以通过链表来优化但是如何同时优化呢笔者认为可以使用跳表这样可以将插入排序的平均时间复杂度优化到 O ( n l o g n ) O(nlogn) O(nlogn)但是缺点在于实现复杂且空间开销较大相比于快速排序堆排序等有点得不偿失。
希尔排序
希尔排序其实就是对于插入排序的优化前文提到插入排序在基本有序的数组排序效率比较高那么可以考虑对于数组的子序列进行排序具体的思路就是将子数组分为多个子序列在每一轮中只对子序列内部进行插入排序。子序列分组的规则是每隔gap个的元素作为一个子序列gap值在轮数下不断减小直到为一后相当于是对全部数据进行插入排序由于此时数组已经基本有序所以最后一轮插入排序的效率很高。
// 希尔排序时间复杂度: O(n^(3 / 2)) 空间复杂度O(1) 不稳定
func (s *Sorter[T]) ShellSort(arr []T) {n : len(arr)gap : n 1for gap 0 {for i : 0; i gap; i {for j : i; j n; j gap {for k : i gap; k n; k gap {if s.less(arr[k], arr[k-gap]) {arr[k], arr[k-gap] arr[k-gap], arr[k]}}}}gap 1}
}希尔排序的时间复杂度为 O ( n 3 / 2 ) O(n ^ {3 / 2}) O(n3/2)但是最坏情况下也可能恶化成 O ( n 2 ) O(n^2) O(n2)空间复杂度为 O ( 1 ) O(1) O(1)是一种不稳定的排序算法适用于中等规模的数据集排序。
堆排序
堆排序就是基于堆这种数据结构的性质往往使用一个最小堆将堆顶的元素取出然后将最后一个元素放到堆顶后从上到下进行调整重复这一个过程就能完成数组的排序。
type Heap[T any] struct {less func(item1, item2 T) boolarray []Tlength int // 标识实际长度
}// NewHeap 构建一个空的堆
func NewHeap[T any](less func(item1, item2 T) bool) *Heap[T] {return Heap[T]{less: less, array: make([]T, 0), length: 0}
}// NewHeapWithArr 根据数组构建一个堆
func NewHeapWithArr[T any](less func(item1, item2 T) bool, arr []T) *Heap[T] {h : Heap[T]{less: less, array: arr, length: len(arr)}for i : 1; i len(arr); i {h.siftUp(i)}return h
}// Push 往堆h中插入一个元素
func (h *Heap[T]) Push(v T) {h.pushBack(v)h.siftUp(h.length - 1)
}// Top 返回堆顶的元素
func (h *Heap[T]) Top() T {return h.array[0]
}// Pop 移除堆顶的元素并返回
func (h *Heap[T]) Pop() T {ret : h.array[0]h.array[0] h.array[h.length-1]h.length--h.siftDown(0)return ret
}func (h *Heap[T]) ToArr() []T {return h.array
}func (h *Heap[T]) IsEmpty() bool {return h.length 0
}// pushBack 在尾部插入一个元素
func (h *Heap[T]) pushBack(v T) {if len(h.array) h.length {h.array append(h.array, v)} else {h.array[h.length] v}h.length
}// siftUp 从pos位置处开始往上调整
func (h *Heap[T]) siftUp(pos int) {if pos 0 || pos h.length {return}i : posj : (pos - 1) / 2for j 0 h.less(h.array[i], h.array[j]) {h.array[i], h.array[j] h.array[j], h.array[i]i jj (i - 1) / 2}
}// siftDown 从pos位置处开始往下调整
func (h *Heap[T]) siftDown(pos int) {if pos 0 || pos len(h.array) {return}i : 0j1 : 2*i 1j2 : 2*i 2for j1 h.length {if h.less(h.array[j1], h.array[i]) ((j2 h.length) || h.less(h.array[j1], h.array[j2])) {h.array[i], h.array[j1] h.array[j1], h.array[i]i j1} else if h.less(h.array[j2], h.array[i]) {h.array[i], h.array[j2] h.array[j2], h.array[i]i j2} else {break}j1 2*i 1j2 2*i 2}
}// HeapSort 堆排序时间复杂度:O(nlogn), 空间复杂度O(1), 不稳定
func (s *Sorter[T]) HeapSort(arr []T) {h : NewHeapWithArr(s.less, arr)k : len(arr) - 1for !h.IsEmpty() {arr[k] h.Pop()k--}for i : 0; i len(arr) / 2; i {arr[i], arr[len(arr) - 1 - i] arr[len(arr) - 1 - i], arr[i]}
}堆排序的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)空间复杂度为 O ( n ) O(n) O(n)是一种不稳定的排序算法适用于大数据量下且内存资源相对宝贵的条件下。
快速排序
快速排序是一种基于分制的思路对于一个数组从中选择一个基准点以这个基准点小于的数交换到左边取大于的数交换到右边去然后递归地对左边和右边的子数组进行同样的处理从而完成整个排序过程。
// 快速排序实现时间复杂度O(nlogn) 空间复杂度O(1), 不稳定
func (s *Sorter[T]) QuickSort(arr []T) {s.quickSortV1(arr, 0, len(arr)-1)
}// 递归形式的排序
func (s *Sorter[T]) quickSortV1(arr []T, left, right int) {if left right { // 递归终点return}base : arr[left]basePtr : lefti : left 1for i right {if s.less(arr[i], base) {basePtrif basePtr ! i {arr[basePtr], arr[i] arr[i], arr[basePtr]}}i}arr[left] arr[basePtr]arr[basePtr] bases.quickSortV1(arr, left, basePtr-1)s.quickSortV1(arr, basePtr1, right)
}以上实现版本的快速排序时间复杂度是 O ( n l o g n ) O(nlogn) O(nlogn)空间复杂度为 O ( 1 ) O(1) O(1)是一种不稳定的排序算法但是最坏情况下时间复杂度也会恶化到 O ( n 2 ) O(n^2) O(n2)。比如上面的实现在数组基本有序的情况下会化身为时间刺客如下图。 一种常见的优化手段是从数组中取三个数字然后以这三个数字的中位数作为基准点如下为相关代码实现:
// quickSortV3优化实现基准取头尾中三数中的平均数
func (s *Sorter[T]) quickSortV3(arr []T, left, right int) {if left right { // 递归终点return}s.adjustBase(arr, left, right)base : arr[left]basePtr : lefti : left 1for i right {if s.less(arr[i], base) {basePtrif basePtr ! i {arr[basePtr], arr[i] arr[i], arr[basePtr]}}i}arr[left] arr[basePtr]arr[basePtr] bases.quickSortV3(arr, left, basePtr-1)s.quickSortV3(arr, basePtr1, right)
}// adjustBase 调整基准值将头尾中三数中的平均数放在头部作为基准
func (s *Sorter[T]) adjustBase(arr []T, left, right int) {basePtrs : []int{left, right, (left right) / 2}s1 : NewSorter(func(i, j int) bool {return s.less(arr[i], arr[j])})s1.InsertSort(basePtrs)arr[left], arr[basePtrs[1]] arr[basePtrs[1]], arr[left]
}但是以上方法对于一个全是相同数字的数组还是会恶化成 O ( n 2 ) O(n^2) O(n2)。 在某些面试中可能有些面试官要求实现一些递归算法的非递归版本比如实现非递归版本的快速排序。递归在编程语言中的实质就是借助栈来实现的所以这种题目本质上就是在模拟递归代码实现如下
// 非递归实现借助栈来模拟递归
func (s *Sorter[T]) quickSortV2(arr []T, left, right int) {stack : NewStack[[2]int]()stack.Push([2]int{left, right})for !stack.IsEmpty() {state : stack.Pop()left, right : state[0], state[1]if left right {continue}base : arr[left]basePtr : lefti : left 1for i right {if s.less(arr[i], base) {basePtrif basePtr ! i {arr[basePtr], arr[i] arr[i], arr[basePtr]}}i}arr[left] arr[basePtr]arr[basePtr] basestack.Push([2]int{left, basePtr - 1})stack.Push([2]int{basePtr 1, right})}
}实际上也可以不使用栈使用队列或者其他的数据结构都是可以的。
归并排序
归并排序的重点在于归并上对于两个已经有序的数组而言可以合并到一个有序的数组中时间复杂度为 O ( n ) O(n) O(n)这样最小的段即一个数的数组必然是有序的小段合成大段最后合并完成整个数组的排序。
// MergeSort 归并排序时间复杂度O(nlogn), 空间复杂度O(n), 稳定
func (s *Sorter[T]) MergeSort(arr []T) []T {return s.mergeSortV1(arr)
}// 递归形式的归并排序
func (s *Sorter[T]) mergeSortV1(arr []T) []T {if len(arr) 1 { // 递归终点return arr}// 递归过程leftArr : s.mergeSortV1(append([]T(nil), arr[:len(arr)/2]...))rightArr : s.mergeSortV1(append([]T(nil), arr[len(arr)/2:]...))// 合并i : 0j : 0k : 0for i len(leftArr) || j len(rightArr) {if i len(leftArr) || (j len(rightArr) s.less(rightArr[j], leftArr[i])) {arr[k] rightArr[j]jk} else {arr[k] leftArr[i]ik}}return arr
}归并排序也可以实现非递归的形式如下
// 非递归形式的归并排序
func (s *Sorter[T]) mergeSortV2(arr []T) []T {segLen : 1 // 比较的段长for segLen len(arr) {for p : 0; p len(arr); p 2 * segLen {leftArr : append([]T(nil), arr[p:min(psegLen, len(arr))]...)rightArr : append([]T(nil), arr[min(psegLen, len(arr)):min(p2*segLen, len(arr))]...)// 合并i : 0j : 0k : 0for i len(leftArr) || j len(rightArr) {if i len(leftArr) || (j len(rightArr) s.less(rightArr[j], leftArr[i])) {arr[pk] rightArr[j]jk} else {arr[pk] leftArr[i]ik}}}segLen * 2}return arr
}归并排序时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)空间复杂度为 O ( n ) O(n) O(n)是一种稳定的排序算法。归并排序适用于大数据量且要求稳定的场景毕竟同时间复杂度的排序算法快速排序和堆排序都是不稳定的。
非比较型排序算法
可以注意到以上的排序算法都需要通过比较元素的大小来交换位置或者其他的操作这类算法统称为比较型排序算法。另外一类非比较型排序算法不需要比较大小但是其适用面比较小。
计数排序
所谓的计数排序就是维护一个数组用来表示每一个元素出现的次数然后遍历数组将各个数字取出即可。
type IntSorter struct {
}func NewIntSorter() *IntSorter {return IntSorter{}
}// 计数排序时间复杂度O(nk) k为数据范围 空间复杂度O(k) 稳定
// 适用于数据范围不大的情况下
func (s *IntSorter) CountSort(arr []int64) {minv : arr[0]maxv : arr[0]for _, item : range arr {minv min(minv, item)maxv max(maxv, item)}counts : make([]int64, maxv-minv1)for _, item : range arr {counts[item-minv]}k : 0for i : int64(0); i maxv-minv1; i {for j : int64(0); j counts[i]; j {arr[k] i minvk}}
}计数排序的时间复杂度为 O ( n ) O(n) O(n)级别空间复杂度为 O ( m ) O(m) O(m)其中m为数组中最大数减去最小数可以看到计数排序只适用于整数且最好数据比较集中。
基数排序
以整数的基数排序来说明这一个过程。由于整数的每一位只有十种可能从0到9那么可以建立十个桶遍历数组按照最低位对应的数字放到对应的桶中然后再将所有数组按照0号桶收集起来然后从数字的低第二位做重复的操作直到最大数字的最高位。代码实现如下
func (s *IntSorter) RadixSort(arr []int) {var newBuckets func() []*List[int] func() []*List[int] {buckets : make([]*List[int], 10)for i : 0; i 10; i {buckets[i] NewList[int]()}return buckets}buckets : newBuckets()oldBuckets : newBuckets()for _, num : range arr {oldBuckets[num%10].AppendNodeTail(NewListNode[int](num/10, num))}flag : true // 停止标志for flag {flag falsefor i : 0; i 10; i {for node : oldBuckets[i].Begin(); node ! oldBuckets[i].End(); node node.Next {if node.Key ! 0 {flag true}buckets[node.Key%10].AppendNodeTail(NewListNode[int](node.Key/10, node.Val))}}oldBuckets bucketsbuckets newBuckets()}// 此时所有数据都在零号桶里k : 0for node : oldBuckets[0].Begin(); node ! oldBuckets[0].End(); node node.Next {arr[k] node.Valk}
}基数排序的时间复杂度也大致在 O ( n m ) O(nm) O(nm)左右对于整数可以认为是 O ( n ) O(n) O(n)空间复杂度为 O ( n ) O(n) O(n)适用于整数或者字符串等。
