排序算法实现 - 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）

参考资料

热门文章

最新文章

相关电子书

推荐镜像