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

2019-11-10 09:21:24 来源:易采站长站 作者:于丽

本文实例讲述了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) 

微信扫一扫

易采站长站微信账号