golangは九大ソートアルゴリズムを実現します.
順序付けアルゴリズムの9つの基礎アルゴリズムをGolangにより実現した.
package sortalgorithm
/*****************************************
* *
* : 、 *
* *
*========================================*/
/*****************************************
* *
* : 、 *
*========================================*/
/*****************************************
* *
* : 、 *
*========================================*/
/*****************************************
* *
* : 、 *
*========================================*/
//@description
func BulleSort(numList []int) []int {
length := len(numList)
if length <= 1 {
return numList
}
for i := 0; i < len(numList); i++ {
for j := 0; j < len(numList)-i-1; j++ {
if numList[j] > numList[j+1] {
tem := numList[j+1]
numList[j+1] = numList[j]
numList[j] = tem
}
}
}
return numList
}
//@description
func QuickSort(numList []int, start, end int) []int {
length := len(numList)
if length <= 1 {
return numList
}
if start < end {
i, j, pivot := start, end, numList[start]
for i < j {
for i < j && numList[j] >= pivot {
j--
}
if i < j {
numList[i] = numList[j]
i++
}
for i < j && numList[j] < pivot {
i++
}
if i < j {
numList[j] = numList[i]
j--
}
}
numList[i] = pivot
QuickSort(numList, start, i-1)
QuickSort(numList, i+1, end)
}
return numList
}
//@description
func CountingSort(numList []int) []int {
length := len(numList)
if length <= 1 {
return numList
}
maxVal := getMax(numList, length)
tem := make([]int, maxVal+1)
for i := 0; i < length; i++ {
tem[numList[i]] += 1
}
j := 0
for i := 0; i < maxVal+1; i++ {
for tem[i] > 0 {
numList[j] = i
j++
tem[i]--
}
}
return numList
}
//@description
func InsertSort(numList []int) []int {
length := len(numList)
if length <= 1 {
return numList
}
for i := 1; i < len(numList); i++ {
for j := i - 1; j > -1; j-- {
if numList[j] > numList[j+1] {
tem := numList[j+1]
numList[j+1] = numList[j]
numList[j] = tem
}
}
}
return numList
}
//@description
func InsertShell(numList []int) []int {
length := len(numList)
if length <= 1 {
return numList
}
gap := int(len(numList) / 2)
for gap >= 1 {
for i := gap; i < len(numList); i++ {
for j := i - gap; j > -1; j-- {
if numList[j] > numList[j+gap] {
tem := numList[j+gap]
numList[j+gap] = numList[j]
numList[j] = tem
}
}
}
gap = int(gap / 2)
}
return numList
}
//@description
func SelectSort(numList []int) []int {
length := len(numList)
if length <= 1 {
return numList
}
for i := 0; i < len(numList); i++ {
minimun := numList[i]
for j := i + 1; j < len(numList); j++ {
if numList[j] < minimun {
tem := numList[j]
numList[j] = minimun
minimun = tem
}
}
numList[i] = minimun
}
return numList
}
//@description
func HeapSort(numList []int) []int {
length := len(numList)
if length <= 1 {
return numList
}
for i := int(len(numList) - 1/2); i > -1; i-- {
adjustMaxHeap(numList, length, i)
}
for length > 0 {
temp := numList[length-1]
numList[length-1] = numList[0]
numList[0] = temp
length--
adjustMaxHeap(numList, length, 0)
}
return numList
}
func adjustMaxHeap(numList []int, length, i int) {
largest := i
for {
left := 2*i + 1
right := 2*i + 2
if left < length && numList[left] > numList[i] {
largest = left
} else {
largest = i
}
if right < length && numList[right] > numList[largest] {
largest = right
}
if largest != i {
tem := numList[i]
numList[i] = numList[largest]
numList[largest] = tem
i = largest
continue
} else {
break
}
}
}
//@description
func MergeSort(numList []int) []int {
length := len(numList)
if length <= 1 {
return numList
}
num := length / 2
left := MergeSort(numList[:num])
right := MergeSort(numList[num:])
return merge(left, right)
}
func merge(left, right []int) (result []int) {
l, r := 0, 0
for l < len(left) && r < len(right) {
if left[l] < right[r] {
result = append(result, left[l])
l++
} else {
result = append(result, right[r])
r++
}
}
result = append(result, left[l:]...)
result = append(result, right[r:]...)
return
}
//@description
func RadixSort(numList []int) []int {
length := len(numList)
if length <= 1 {
return numList
}
max := getMax(numList, length)
for i := 1; max/i > 0; i *= 10 {
numList = countSort(numList, length, i)
}
return numList
}
func getMax(numList []int, n int) int {
max := numList[0]
for i := 0; i < n; i++ {
if numList[i] > max {
max = numList[i]
}
}
return max
}
func countSort(numList []int, n, exp int) []int {
output := make([]int, n)
for i := 0; i < n; i++ {
num := (numList[i] / exp) % 10
output[num]++
}
for i := 1; i < 10; i++ {
output[i] += output[i-1]
}
tem := make([]int, n)
for i := n - 1; i >= 0; i-- {
num := (numList[i] / exp) % 10
tem[output[num]-1] = numList[i]
output[num]--
}
for i := 0; i < n; i++ {
numList[i] = tem[i]
}
return numList
}