欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Golang 實(shí)現(xiàn)插入排序的方法示例(2種)

 更新時(shí)間:2020年02月13日 08:32:59   作者:鄒友  
這篇文章主要介紹了Golang 實(shí)現(xiàn)插入排序的方法示例,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧

再次研究了插入排序的概念:定義一個(gè)有序的數(shù)據(jù)序列a,將待排序的序列b中的數(shù)依次插入到a的合適位置,插入后仍然有序

總結(jié)其與冒泡、選擇的區(qū)別在于,內(nèi)部迭代的次數(shù)是逐漸增大的,二后兩者隨著排序進(jìn)行迭代次數(shù)逐漸減少

嘗試基于Go的實(shí)現(xiàn):

插入排序都采用in-place在數(shù)組上實(shí)現(xiàn)。具體算法描述如下:

  • 從第一個(gè)元素開(kāi)始,該元素可以認(rèn)為已經(jīng)被排序 取出下一個(gè)元素
  • 在已經(jīng)排序的元素序列中從后向前掃描
  • 如果該元素(已排序)大于新元素,將該元素移到下一位置
  • 重復(fù)步驟3,直到找到已排序的元素小于或者等于新元素的位置 將新元素插入到該位置后
  • 將新元素插入到該位置后
  • 重復(fù)步驟2~5

兩種實(shí)現(xiàn)方式:1,新建切片; 2,在原切片中進(jìn)行元素交換

方式一:新建切片

package main

import "fmt"

func main() {
 arr := []int{1, 0, 5, 7, 8, 5, 3, 6, 9, 2, 54, 33, 66}
 newArr := []int{}
 insertionSort(arr, &newArr)
 fmt.Println(newArr)
}

/**
插入排序法:取原數(shù)組old中第一個(gè)值作為新數(shù)組中的第一個(gè)值,然后遍歷old,將每個(gè)元素按照條件插入到新數(shù)組中
時(shí)間復(fù)雜度:O(n^2)
*/
func insertionSort(old []int, new *[]int) {
 if len(*new) == len(old) {
 return
 }
 current := len(*new)
 *new = append(*new, old[current])
 sort(*new)
 insertionSort(old, new)
}

func sort(arr []int) {
 for i := len(arr) - 1; i > 0; i-- {
 if arr[i] < arr[i-1] {
  arr[i], arr[i-1] = arr[i-1], arr[i]
 }
 }
}


注意:insertionSort()函數(shù)中的第二個(gè)參數(shù)為切片的指針,不然打印出來(lái)的的新數(shù)組為空

原因:雖然切片是指針傳遞,這是指切片內(nèi)的各個(gè)元素是指針傳遞,對(duì)于切片本身仍是值傳遞

證明:

package test

import (
 "fmt"
 "testing"
)

func TestSlice(t *testing.T) {
 slice1 := []string{"zhang", "san"}
 fmt.Printf("%p\n", &slice1)
 fmt.Printf("%p\n", &slice1[1])
 modify(slice1)
 fmt.Println(slice1)
}
func modify(data []string) {
 fmt.Printf("%p\n", &data)
 fmt.Printf("%p\n", &data[1])
 data[1] = "si"
}

打印結(jié)果:

0xc0420e4680
0xc0420e46b0
0xc0420e46c0
0xc0420e46b0
[zhang si]

引申:Go 語(yǔ)言里的引用類型有如下幾個(gè):切片、映射、通道、接口和函數(shù)類型。當(dāng)聲明上述類型的變量時(shí),創(chuàng)建的變量被稱作標(biāo)頭(header)值。從技術(shù)細(xì)節(jié)上說(shuō),字符串也是一種引用類型。每個(gè)引用類型創(chuàng)建的標(biāo)頭值是包含一個(gè)指向底層數(shù)據(jù)結(jié)構(gòu)的指針。因?yàn)闃?biāo)頭值是為復(fù)制而設(shè)計(jì)的,所以永遠(yuǎn)不需要共享一個(gè)引用類型的值。標(biāo)頭值里包含一個(gè)指針,因此通過(guò)復(fù)制來(lái)傳遞一個(gè)引用類型的值的副本,本質(zhì)上就是在共享底層數(shù)據(jù)結(jié)構(gòu)

結(jié)論:不會(huì)對(duì)切片進(jìn)行增加或刪除操作時(shí)(也就是長(zhǎng)度不會(huì)改變),切片作為參數(shù)在函數(shù)間的傳遞不需使用指針。但是如果切片需要進(jìn)行增加或刪除元素的操作,并且原函數(shù)需要調(diào)用更新后的切片,那么在原函數(shù)調(diào)用其它函數(shù)時(shí),就需要用切片的指針作為參數(shù)。

方式二:在原切片中進(jìn)行元素交換

func method2(arr []int) {
 if len(arr) < 2 {
 return
 }
 for i := 1; i < len(arr); i++ {
 for j := i; j > 0; j-- {
  if arr[j] < arr[j-1] {
  arr[j], arr[j-1] = arr[j-1], arr[j]
  }
 }
 }
}
 

由于不用創(chuàng)建新的切片,不用進(jìn)行插入操作,只需要交換操作,所以要較方法一速度快些

以上就是本文的全部?jī)?nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。

相關(guān)文章

  • 詳解go?mod?使用方法

    詳解go?mod?使用方法

    golang 提供了 go mod命令來(lái)管理包,是go的一個(gè)模塊管理工具,用來(lái)代替?zhèn)鹘y(tǒng)的GOPATH方案,本文給大家介紹go?mod?使用方法,感興趣的朋友一起看看吧
    2022-05-05
  • Golang無(wú)限緩存channel的設(shè)計(jì)與實(shí)現(xiàn)解析

    Golang無(wú)限緩存channel的設(shè)計(jì)與實(shí)現(xiàn)解析

    這篇文章主要為大家介紹了Golang無(wú)限緩存channel的設(shè)計(jì)與實(shí)現(xiàn)解析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2023-07-07
  • golang?JSON序列化和反序列化示例詳解

    golang?JSON序列化和反序列化示例詳解

    通過(guò)使用Go語(yǔ)言的encoding/json包,你可以輕松地處理JSON數(shù)據(jù),無(wú)論是在客戶端應(yīng)用、服務(wù)器端應(yīng)用還是其他類型的Go程序中,這篇文章主要介紹了golang?JSON序列化和反序列化,需要的朋友可以參考下
    2024-04-04
  • Go語(yǔ)言使用Redis和Etcd實(shí)現(xiàn)高性能分布式鎖

    Go語(yǔ)言使用Redis和Etcd實(shí)現(xiàn)高性能分布式鎖

    這篇文章主要為大家介紹了Go語(yǔ)言使用Redis實(shí)現(xiàn)高性能分布式鎖示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2023-12-12
  • GO必知必會(huì)的常見(jiàn)面試題匯總

    GO必知必會(huì)的常見(jiàn)面試題匯總

    這篇文章主要為大家介紹了GO必知必會(huì)的常見(jiàn)面試題匯總
    2022-08-08
  • Go語(yǔ)言列表List獲取元素的4種方式

    Go語(yǔ)言列表List獲取元素的4種方式

    Golang的列表元素的獲取可以使用內(nèi)置的 Front 函數(shù)獲取頭結(jié)點(diǎn),使用 Back 函數(shù)獲取尾結(jié)點(diǎn),使用 Prev 獲取前一個(gè)結(jié)點(diǎn),使用 Next 獲取下一個(gè)結(jié)點(diǎn),本文就介紹了Go語(yǔ)言列表List獲取元素的4種方式,感興趣的可以了解一下
    2022-04-04
  • Golang中這些channel用法你了解嗎

    Golang中這些channel用法你了解嗎

    channel?是GO語(yǔ)言中一種特殊的類型,是連接并發(fā)goroutine的管道,這篇文章主要來(lái)和大家分享一下關(guān)于?nil?channel?通道,有緩沖通道,無(wú)緩沖通道的常用方法以及巧妙使用的方式,希望對(duì)大家有所幫助
    2023-08-08
  • 解析Go 標(biāo)準(zhǔn)庫(kù) http.FileServer 實(shí)現(xiàn)靜態(tài)文件服務(wù)

    解析Go 標(biāo)準(zhǔn)庫(kù) http.FileServer 實(shí)現(xiàn)靜態(tài)文件服務(wù)

    http.FileServer 方法屬于標(biāo)準(zhǔn)庫(kù) net/http,返回一個(gè)使用 FileSystem 接口 root 提供文件訪問(wèn)服務(wù)的 HTTP 處理器。下面通過(guò)本文給大家介紹Go 標(biāo)準(zhǔn)庫(kù) http.FileServer 實(shí)現(xiàn)靜態(tài)文件服務(wù)的相關(guān)知識(shí),感興趣的朋友一起看看吧
    2018-08-08
  • golang 如何用反射reflect操作結(jié)構(gòu)體

    golang 如何用反射reflect操作結(jié)構(gòu)體

    這篇文章主要介紹了golang 用反射reflect操作結(jié)構(gòu)體的操作,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧
    2021-04-04
  • 詳解Golang中Context的原理和使用技巧

    詳解Golang中Context的原理和使用技巧

    Golang?的?Context?包,中文可以稱之為“上下文”,是用來(lái)在?goroutine?協(xié)程之間進(jìn)行上下文信息傳遞的,這些上下文信息包括?kv?數(shù)據(jù)、取消信號(hào)、超時(shí)時(shí)間、截止時(shí)間等。本文主要介紹了Context的原理和使用技巧,希望對(duì)大家有所幫助
    2022-11-11

最新評(píng)論