Go语言实现冒泡排序、选择排序、快速排序及插入排序的方法

本文实例讲述了Go语言实现冒泡排序、选择排序、快速排序及插入排序的方法。分享给大家供大家参考。具体分析如下：

算法是程序的灵魂，而排序算法则是一种最基本的算法。排序算法有许多种，这里介绍4中排序算法：冒泡排序，选择排序，快速排序和插入排序，以从小到大为例。

一、冒泡排序

冒泡排序的原理是，对给定的数组进行多次遍历，每次均比较相邻的两个数，如果前一个比后一个大，则交换这两个数。经过第一次遍历之后，最大的数就在最右侧了；第二次遍历之后，第二大的数就在右数第二个位置了；以此类推。

代码如下:

//冒泡排序（排序10000个随机整数，用时约145ms）
func bubbleSort(nums []int) {
    for i := 0; i < len(nums); i++ {
        for j := 1; j < len(nums)-i; j++ {
            if nums[j] < nums[j-1] {
                //交换
                nums[j], nums[j-1] = nums[j-1], nums[j]
            }
        }
    }
}

二、选择排序

选择排序的原理是，对给定的数组进行多次遍历，每次均找出最大的一个值的索引。

代码如下:

//选择排序（排序10000个随机整数，用时约45ms）
func selectSort(nums []int) {
    length := len(nums)
    for i := 0; i < length; i++ {
        maxIndex := 0
        //寻找最大的一个数，保存索引值
        for j := 1; j < length-i; j++ {
            if nums[j] > nums[maxIndex] {
                maxIndex = j
            }
        }
        nums[length-i-1], nums[maxIndex] = nums[maxIndex], nums[length-i-1]
    }
}

三、快速排序

快速排序的原理是，首先找到一个数pivot把数组‘平均'分成两组，使其中一组的所有数字均大于另一组中的数字，此时pivot在数组中的位置就是它正确的位置。然后，对这两组数组再次进行这种操作。

代码如下:

//快速排序（排序10000个随机整数，用时约0.9ms）
func quickSort(nums []int) {
    recursionSort(nums, 0, len(nums)-1)
}

func recursionSort(nums []int, left int, right int) {
    if left < right {
        pivot := partition(nums, left, right)
        recursionSort(nums, left, pivot-1)
        recursionSort(nums, pivot+1, right)
    }
}

func partition(nums []int, left int, right int) int {
    for left < right {
        for left < right && nums[left] <= nums[right] {
            right--
        }
        if left < right {
            nums[left], nums[right] = nums[right], nums[left]
            left++
        }

        for left < right && nums[left] <= nums[right] {
            left++
        }
        if left < right {
            nums[left], nums[right] = nums[right], nums[left]
            right--
        }
    }
    return left
}

四、插入排序

插入排序的原理是，从第二个数开始向右侧遍历，每次均把该位置的元素移动至左侧，放在放在一个正确的位置（比左侧大，比右侧小）。

代码如下:

//插入排序（排序10000个整数，用时约30ms）
func insertSort(nums []int) {
    for i := 1; i < len(nums); i++ {
        if nums[i] < nums[i-1] {
            j := i - 1
            temp := nums[i]
            for j >= 0 && nums[j] > temp {
                nums[j+1] = nums[j]
                j--
            }
            nums[j+1] = temp
        }
    }
}

通过多次测试可以发现，快速排序是效率最高的。

希望本文所述对大家的Go语言程序设计有所帮助。

您可能感兴趣的文章: