排序算法实现 - Golang版-阿里云开发者社区

算法列表

算法实现

冒泡排序（Bubble Sort）

funcBubbleSort(arrayInterface, begin, endint) {
length :=end-begin+1iflength<2 {
return    }
i, j :=0, 0fori=begin; i<end; i++ {
forj=begin; j<end-i; j++ {
ifarray.Less(j+1, j) {
array.Swap(j, j+1)
            }
        }
    }
}

鸡尾酒排序（Cocktail Sort）

// CocktailSort 鸡尾酒排序// @see https://zh.wikipedia.org/zh-hans/%E9%B8%A1%E5%B0%BE%E9%85%92%E6%8E%92%E5%BA%8F// @see https://zhuanlan.zhihu.com/p/125008445funcCocktailSort(arrayInterface, begin, endint) {
length :=end-begin+1iflength<2 {
return    }
low, high :=begin, endi :=0swapped :=trueforswapped {
swapped=falsefori=low; i<high; i++ {
ifarray.Less(i+1, i) {
array.Swap(i, i+1)
swapped=true            }
        }
if!swapped {
break        }
swapped=falsehigh--fori=high-1; i>=low; i-- {
ifarray.Less(i+1, i) {
array.Swap(i, i+1)
swapped=true            }
        }
low++    }
}

选择排序（Selection Sort）

// SelectionSort 选择排序// @see https://en.wikipedia.org/wiki/Selection_sortfuncSelectionSort(arrayInterface, begin, endint) {
length :=end-begin+1iflength<2 {
return    }
i, j, minIndex :=0, 0, 0fori=begin; i<end; i++ {
minIndex=iforj=i+1; j<=end; j++ {
ifarray.Less(j, minIndex) {
minIndex=j            }
        }
ifminIndex!=i {
array.Swap(i, minIndex)
        }
    }
}

插入排序（Insertion Sort）

// InsertionSort 插入排序funcInsertionSort(arrayInterface, begin, endint) {
length :=end-begin+1iflength<2 {
return    }
i, j :=begin+1, 0for ; i<=end; i++ {
forj=i; j>0&&array.Less(j, j-1); j-- {
array.Swap(j, j-1)
        }
    }
}

归并排序（Merge Sort）

// MergeSort 归并排序// @see https://en.wikipedia.org/wiki/Merge_sort// @see https://www.enjoyalgorithms.com/blog/merge-sort-algorithm// @see https://qvault.io/golang/merge-sort-golang/funcMergeSort(arrayInterface, begin, endint) {
length :=end-begin+1iflength<2 {
return    }
tmp :=mergeSort(array.Part(begin, end+1))
fori :=0; i<length; i++ {
array.Set(i, tmp.Get(i))
    }
}
funcmergeSort(arrayInterface) Interface {
ifarray.Len() <2 {
returnarray    }
mid :=divisionByTwo(array.Len())
left :=mergeSort(array.Part(0, mid))
right :=mergeSort(array.Part(mid, array.Len()))
returnspaceMerge(left, right)
}
// spaceMerge 归并funcspaceMerge(left, rightInterface) Interface {
lengthLeft :=left.Len()
lengthRight :=right.Len()
varresult=make(InterfaceSlice, 0, lengthLeft+lengthRight)
i, j :=0, 0fori<lengthLeft&&j<lengthRight {
ifless(left.Get(i), right.Get(j)) {
result=append(result, left.Get(i))
i++        } else {
result=append(result, right.Get(j))
j++        }
    }
for ; i<lengthLeft; i++ {
result=append(result, left.Get(i))
    }
for ; j<lengthRight; j++ {
result=append(result, right.Get(j))
    }
returnresult}

原地归并排序（In-place Merge Sort）

// InPlaceMergeSort 原地归并排序// @see https://en.wikipedia.org/wiki/Merge_sort// @see https://www.geeksforgeeks.org/in-place-merge-sort/funcInPlaceMergeSort(arrayInterface, begin, endint) {
ifbegin<end {
mid :=int(math.Floor(float64(begin+ (end-begin)>>1)))
InPlaceMergeSort(array, begin, mid)
InPlaceMergeSort(array, mid+1, end)
inPlaceMerge(array, begin, mid, end)
    }
}
// inPlaceMerge 原地归并funcinPlaceMerge(arrayInterface, begin, mid, endint) {
indexLeft, indexRight :=begin, mid+1endLeft, endRight :=mid, endifarray.Less(endLeft, indexRight) {
return    }
sortedIndex :=0forindexLeft<=endLeft&&indexRight<=endRight {
ifarray.Less(indexLeft, indexRight) {
indexLeft++        } else {
tempValue :=array.Get(indexRight)
sortedIndex=indexRightforsortedIndex!=indexLeft {
array.Swap(sortedIndex, sortedIndex-1)
sortedIndex--            }
array.Set(indexLeft, tempValue)
indexLeft++endLeft++indexRight++        }
    }
}

堆排序（Heap Sort）

// HeapSort 堆排序// @see https://brilliant.org/wiki/heap-sort/funcHeapSort(arrayInterface, begin, endint) {
length :=end-begin+1iflength<2 {
return    }
varmaxHeapheapmaxHeap.buildHeap(array, begin, end)
maxHeap.popTop(array, begin, end)
}
typeheapstruct {
}
func (h*heap) siftDown(dataInterface, lo, hi, firstint) {
root :=lofor {
child :=2*root+1ifchild>=hi {
break        }
ifchild+1<hi&&data.Less(first+child, first+child+1) {
child++        }
if!data.Less(first+root, first+child) {
return        }
data.Swap(first+root, first+child)
root=child    }
}
func (h*heap) buildHeap(arrayInterface, begin, endint) {
low, high :=begin, endmid :=int(math.Floor(float64(end+1>>1)))
fori :=mid; i>=begin; i-- {
h.siftDown(array, i, high, low)
    }
}
func (h*heap) popTop(arrayInterface, begin, endint) {
first :=beginlow, high :=begin, endfori :=high; i>=begin; i-- {
array.Swap(first, first+i)
h.siftDown(array, low, i, first)
    }
}

快速排序（Quick Sort）

// QuickSort 快速排序// @see https://en.wikipedia.org/wiki/Quicksort// @see https://www.eecs.yorku.ca/course_archive/2010-11/W/2011/Notes/s4_quick_sort.pdffuncQuickSort(arrayInterface, begin, endint) {
ifbegin<end {
pi :=quickSortPartition(array, begin, end)
QuickSort(array, begin, pi-1)
QuickSort(array, pi+1, end)
    }
}
funcquickSortPartition(arrayInterface, begin, endint) int {
pivot :=array.Get(end)
pi :=begin-1fori :=begin; i<end; i++ {
ifless(array.Get(i), pivot) {
pi++array.Swap(pi, i)
        }
    }
array.Swap(pi+1, end)
returnpi+1}

希尔排序（Shell Sort）

// ShellSort 希尔排序// @see https://en.wikipedia.org/wiki/ShellsortfuncShellSort(arrayInterface, begin, endint) {
length :=end-begin+1iflength<2 {
return    }
i, j :=0, 0gap :=divisionByTwo(begin+ (end-begin))
for ; gap>begin; gap=divisionByTwo(gap) {
fori=gap; i<=end; i++ {
forj=i-gap; j>=begin; j-=gap {
ifarray.Less(j+gap, j) {
array.Swap(j, j+gap)
                } else {
break                }
            }
        }
    }
}

计数排序（Counting Sort）

// CountingSort 计数排序funcCountingSort(arrayIntSlice, begin, endint) {
length :=end-begin+1iflength<2 {
return    }
maxValue :=array[begin]
i :=0fori=begin+1; i<=end; i++ {
ifarray[i] >maxValue {
maxValue=array[i]
        }
    }
bucketLen :=maxValue+1bucket :=make(IntSlice, bucketLen)
fori=begin; i<=end; i++ {
bucket[array[i]]++    }
sortedIndex :=0fori=0; i<bucketLen; i++ {
forbucket[i] >0 {
array[sortedIndex] =isortedIndex++bucket[i]--        }
    }
}
// CountingSortNegative 计数排序 - 可以处理负数的版本funcCountingSortNegative(arrayIntSlice, begin, endint) {
length :=end-begin+1iflength<2 {
return    }
minValue, maxValue :=array[begin], array[begin]
i :=0fori=begin+1; i<=end; i++ {
ifarray[i] <minValue {
minValue=array[i]
        }
ifarray[i] >maxValue {
maxValue=array[i]
        }
    }
bucketLen :=maxValue+1bucket :=make(IntSlice, bucketLen)
negativeBucketLen :=0ifminValue<0 {
negativeBucketLen=int(math.Abs(float64(minValue))) +1    }
negativeBucket :=make(IntSlice, negativeBucketLen)
fori=begin; i<=end; i++ {
ifarray[i] >=0 {
bucket[array[i]]++        } else {
negativeBucket[int(math.Abs(float64(array[i])))]++        }
    }
sortedIndex :=0fori=negativeBucketLen-1; i>=0; i-- {
fornegativeBucket[i] >0 {
array[sortedIndex] =-isortedIndex++negativeBucket[i]--        }
    }
fori=0; i<bucketLen; i++ {
forbucket[i] >0 {
array[sortedIndex] =isortedIndex++bucket[i]--        }
    }
}

基数排序（Radix Sort）

typeBuckets []IntSlice// RadixSort 基数排序// @see https://mp.weixin.qq.com/s/Z8gU9QLpMnA-zoMc9ZeR2w// @see https://www.geeksforgeeks.org/radix-sort/// @see https://en.wikipedia.org/wiki/Radix_sortfuncRadixSort(arrayIntSlice, begin, endint) {
length :=end-begin+1iflength<2 {
return    }
maxNumber :=getMaxNumber(array, begin, end)
constNumberOfBuckets=10n :=1bucket :=make(Buckets, NumberOfBuckets)
forn<=maxNumber {
for_, v :=rangearray {
digit :=getDigit(v, n)
bucket[digit] =append(bucket[digit], v)
        }
n*=10k :=beginfori, v :=rangebucket {
for_, d :=rangev {
array[k] =dk++            }
bucket[i] =bucket[i][:0]
        }
    }
}
funcgetMaxNumberOfDigits(arrayIntSlice, begin, endint) int {
maxNumber :=minInttemp :=0fori :=begin; i<=end; i++ {
temp=int(math.Log10(float64(array[i])) +1)
iftemp>maxNumber {
maxNumber=temp        }
    }
fmt.Println(maxNumber)
returnmaxNumber}
funcgetMaxNumber(arrayIntSlice, begin, endint) int {
maxNumber :=minIntfori :=begin; i<=end; i++ {
ifarray[i] >maxNumber {
maxNumber=array[i]
        }
    }
returnmaxNumber}
funcgetDigit(integer, divisorint) int {
return (integer/divisor) %10}

桶排序（Bucket Sort）

constDefaultBucketSize=5// BucketSort 桶排序// @see https://www3.nd.edu/~dchiang/teaching/ds/2015/handouts/bucketsort.pdf// @see https://www.geeksforgeeks.org/bucket-sort-2/// @see https://en.wikipedia.org/wiki/Bucket_sort// @see https://codecrucks.com/bucket-sort/funcBucketSort(arrayInterface, begin, endint) {
length :=end-begin+1iflength<2 {
return    }
minValue, maxValue :=array.Get(begin), array.Get(begin)
i :=0fori=begin+1; i<=end; i++ {
ifless(array.Get(i), minValue) {
minValue=array.Get(i)
        }
ifless(maxValue, array.Get(i)) {
maxValue=array.Get(i)
        }
    }
bucketSize :=DefaultBucketSizebucketCount :=int(math.Floor(float64(minus(maxValue, minValue)/bucketSize))) +1buckets :=make([]InterfaceSlice, bucketCount)
fori=begin; i<=end; i++ {
bucketIndex :=int(math.Floor(float64(minus(array.Get(i), minValue) /bucketSize)))
buckets[bucketIndex] =append(buckets[bucketIndex], array.Get(i))
    }
sortedIndex :=0for_, bucket :=rangebuckets {
InsertionSort(bucket, 0, bucket.Len()-1)
for_, val :=rangebucket {
array.Set(sortedIndex, val)
sortedIndex++        }
    }
}

二叉排序树排序（Binary Tree Sort）

// BinaryTreeSort 二叉树排序// @see https://en.wikipedia.org/wiki/Tree_sortfuncBinaryTreeSort(arrayInterface, begin, endint) {
length :=end-begin+1iflength<2 {
return    }
tree :=&binaryTree{}
fori :=begin; i<=end; i++ {
tree.insert(array.Get(i))
    }
tree.inOrder(array)
}
typebinaryNodestruct {
datainterface{}
left*binaryNoderight*binaryNode}
typebinaryTreestruct {
root*binaryNode}
func (t*binaryTree) inOrder(arrayInterface) {
ift.root!=nil {
i :=0t.root.inOrder(array, &i)
    }
}
// print the binary treefunc (t*binaryTree) print(wio.Writer) {
t.root.print(w, 0, 'M')
}
// insert a binary tree Node into treefunc (t*binaryTree) insert(datainterface{}) *binaryTree {
ift.root==nil {
t.root=&binaryNode{data: data, left: nil, right: nil}
    } else {
t.root.insert(data)
    }
returnt}
// insert a binary tree Node into Nodefunc (n*binaryNode) insert(datainterface{}) {
ifn==nil {
return    } elseifless(data, n.data) {
ifn.left==nil {
n.left=&binaryNode{data: data, left: nil, right: nil}
        } else {
n.left.insert(data)
        }
    } else {
ifn.right==nil {
n.right=&binaryNode{data: data, left: nil, right: nil}
        } else {
n.right.insert(data)
        }
    }
}
// inOrder traversal of the BSTfunc (n*binaryNode) inOrder(arrayInterface, i*int) {
ifn==nil {
return    }
ifn.left!=nil {
n.left.inOrder(array, i)
    }
array.Set(*i, n.data)
*i++ifn.right!=nil {
n.right.inOrder(array, i)
    }
}
// print the BSTfunc (n*binaryNode) print(wio.Writer, nsint, chrune) {
ifn==nil {
return    }
fori :=0; i<ns; i++ {
_, _=fmt.Fprint(w, " ")
    }
_, _=fmt.Fprintf(w, "%c:%v\n", ch, n.data)
ifn.left!=nil {
n.left.print(w, ns+2, 'L')
    }
ifn.right!=nil {
n.right.print(w, ns+2, 'R')
    }
}

鸽巢排序（Pigeonhole Sort）

// PigeonholeSort 鸽巢排序// @see https://en.wikipedia.org/wiki/Pigeonhole_sort// @see https://zh.wikipedia.org/wiki/%E9%B8%BD%E5%B7%A2%E6%8E%92%E5%BA%8FfuncPigeonholeSort(arrayIntSlice, begin, endint) {
length :=end-begin+1iflength<2 {
return    }
i :=0minValue, maxValue :=array[begin], array[begin]
fori=begin+1; i<=end; i++ {
ifarray[i] <minValue {
minValue=array[i]
        }
ifarray[i] >maxValue {
maxValue=array[i]
        }
    }
holeRange :=maxValue-minValue+1holes :=make([]IntSlice, holeRange)
fori=begin; i<=end; i++ {
holes[array[i]-minValue] =append(holes[array[i]-minValue], array[i])
    }
sortedIndex :=0j :=0fori=0; i<holeRange; i++ {
forj=0; j<holes[i].Len(); j++ {
array[sortedIndex] =holes[i][j]
sortedIndex++        }
    }
}

侏儒排序（Gnome Sort）

// GnomeSort 侏儒排序// @see https://zh.wikipedia.org/wiki/%E4%BE%8F%E5%84%92%E6%8E%92%E5%BA%8FfuncGnomeSort(arrayInterface, begin, endint) {
length :=end-begin+1iflength<2 {
return    }
fori :=begin; i<=end; {
ifi==0 {
i++        }
ifarray.Less(i, i-1) {
array.Swap(i, i-1)
i--        } else {
i++        }
    }
}

块排序（Block Sort）

参考资料

排序算法

排序算法实现 - Golang版

算法列表

算法实现

冒泡排序（Bubble Sort）

鸡尾酒排序（Cocktail Sort）

选择排序（Selection Sort）

插入排序（Insertion Sort）

归并排序（Merge Sort）

原地归并排序（In-place Merge Sort）

堆排序（Heap Sort）

快速排序（Quick Sort）

希尔排序（Shell Sort）

计数排序（Counting Sort）

基数排序（Radix Sort）

桶排序（Bucket Sort）

二叉排序树排序（Binary Tree Sort）

鸽巢排序（Pigeonhole Sort）

侏儒排序（Gnome Sort）

块排序（Block Sort）

参考资料

热门文章

最新文章

相关课程

相关电子书

相关实验场景

推荐镜像

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

排序算法实现 - Golang版

算法列表

算法实现

冒泡排序（Bubble Sort）

鸡尾酒排序（Cocktail Sort）

选择排序（Selection Sort）

插入排序（Insertion Sort）

归并排序（Merge Sort）

原地归并排序（In-place Merge Sort）

堆排序（Heap Sort）

快速排序（Quick Sort）

希尔排序（Shell Sort）

计数排序（Counting Sort）

基数排序（Radix Sort）

桶排序（Bucket Sort）

二叉排序树排序（Binary Tree Sort）

鸽巢排序（Pigeonhole Sort）

侏儒排序（Gnome Sort）

块排序（Block Sort）

参考资料

热门文章

最新文章

相关课程

相关电子书

相关实验场景

推荐镜像