Golang实现几个排序算法,并发写法

    技术2023-09-19  83

    希尔

    func shellSort(nums []int){ var l,i int var wg sync.WaitGroup for l=(len(nums)>>1);l>0;l>>=1{ wg.Add(l) for i=0;i<l;i++{ go func(ii int,ll int,llen int){//插入排序 var j,k,v int for j=ii+ll;j<llen;j+=ll{ v = nums[j] for k=j-ll;k>=0&&v<nums[k];k-=ll{ nums[k+ll] = nums[k] } nums[k+ll] = v } wg.Done() }(i,l,len(nums)) } wg.Wait() } }

    快排

    func quickSort(nums []int){ if len(nums) <= 1{ return } var key = nums[0] var left = 0 var right = len(nums)-1 for left< right{ for left<right && key < nums[right]{ right-- } nums[left] = nums[right] for left<right && key >= nums[left]{ left++ } nums[right] = nums[left] } nums[left] = key var wg sync.WaitGroup wg.Add(2) go func(){ quickSort(nums[:left]) wg.Done() }() go func(){ quickSort(nums[left+1:]) wg.Done() }() wg.Wait() }

    归并,2020/08/09更新

    func mergeSort(nums []int){ if len(nums) <= 1{ return } mid := len(nums)/2 var wg sync.WaitGroup wg.Add(2) go func(){ mergeSort(nums[:mid]) wg.Done() }() go func(){ mergeSort(nums[mid:]) wg.Done() }() wg.Wait() nums_tmp := make([]int,len(nums)) copy(nums_tmp,nums) var i,j,k = 0,mid,0 for i<mid&&j<len(nums){ if nums_tmp[i]<nums_tmp[j]{ nums[k] = nums_tmp[i] k++ i++ }else{ nums[k] = nums_tmp[j] k++ j++ } } for i<mid{ nums[k] = nums_tmp[i] k++ i++ } for j<len(nums){ nums[k] = nums_tmp[j] k++ j++ } return }

    快排,在我的ryzen r5 2600试过,1亿个数,排序少于40秒,内存炸裂,快吃完我的16G内存,炸裂,真的强啊

    希尔,比快排慢了点,耗时1分钟左右,内存占用没快排这么炸裂,递归的锅。

    2021/01/26,其实不适合并发,CPU调度耗费太多资源......

    测试平台联想ThinBook 14,CPU R7 4800U,内存16G

    测试了快排和希尔,归并排序提示没有内存可分配,所以不测了

    10000000数排序 2021/01/26 17:20:13.863542 shellSort seconds 16.1656096s 2021/01/26 17:20:15.705950 quickSort seconds 1.6934076s ----------------------------------------------------------------------------- 2021/01/26 17:23:14.267512 shellSort seconds 27.2349808s 2021/01/26 17:23:16.095629 quickSort seconds 1.7271281s ----------------------------------------------------------------------------- 2021/01/26 17:23:45.107758 shellSort seconds 21.0633104s 2021/01/26 17:23:46.920881 quickSort seconds 1.714876s ----------------------------------------------------------------------------- 2021/01/26 17:24:35.710494 shellSort seconds 6.3424508s 2021/01/26 17:24:37.466956 quickSort seconds 1.72946s ----------------------------------------------------------------------------- 2021/01/26 17:24:47.008482 shellSort seconds 4.8842578s 2021/01/26 17:24:48.775934 quickSort seconds 1.741454s ----------------------------------------------------------------------------- 2021/01/26 17:25:21.148269 shellSort seconds 28.1573544s 2021/01/26 17:25:22.990699 quickSort seconds 1.739435s

    基数排序 2020/07/22更新

    package main import( "log" "sync" ) func init(){ log.SetFlags(log.Ldate|log.Lmicroseconds|log.Lshortfile) } func sortt(s []string,index int){ if len(s) <= 1{ return } var n [128]int var i int var j byte var s_tmp []string = make([]string,len(s)) for i=0;i<len(s);i++ { if len(s[i]) == index{ j = 0 }else{ j = s[i][index] } n[j+1]++ } for i=1;i<128;i++ { n[i] += n[i-1] } for i=0;i<len(s);i++ { if len(s[i]) == index{ j = 0 }else{ j = s[i][index] } s_tmp[n[j]] = s[i] n[j]++ } for i=0;i<len(s);i++ { s[i] = s_tmp[i] } var wg sync.WaitGroup wg.Add(10) index++ for i='0';i<='9';i++{//0表示字符串结尾 不必再加入下一次的排序 go func(ii int){ sortt(s[n[ii-1]:n[ii]],index) wg.Done() }(i) } wg.Wait() } func sort(s []string){ sortt(s,0) } func main(){ s := [...]string{ "485192", "311790", "408550", "35470", "194742", "780132", "870672", "130147", "498484", "757666", "552442", "207311", "184124", "429152", "20572", "642394", "896875", "287139", "782446", "984475", "769573", "861429", "490991", "83706", "117566", "872296", "424646", "331964", "98944", "356038", "915106", "553876", "600217", "831682", "49780", "695061", "81214", "565524", "406909", "761898", "644475", "807612", "176872", "116978", "635972", "124273", "863980", "383146", "976562", "107697", "928314", "248888", "775125", "737273", "407211", "424317", "393000", "112718", "569699", "256526", "332949", "23361", "553493", "257989", "814408", "674851", "45542", "522467", "617148", "359065", "864718", "889835", "281236", "742131", "966420", "847913", "519262", "189340", "394798", "398349", "929358", "52686", "108286", "183516", "295265", "748377", "948576", "698368", "3154", "797935", "684363", "997292", "587453", "610754", "89950", "95293", "729427", "877329", "930111", "124050", "890709", "184877", "982277", "995232", "318498", "334982", "859165", "652751", "967589", "227487", "552430", "673687", "256459", "897174", "555017", "27178", "176345", "714110", "772124", "280422", "317317", "678083", "845405", "835741", "737232", "640823", "999020", "116956", "152408", "417472", "535846", "270419", "44866", "48513", "833745", "417692", "498259", "230572", "716584", "775411", "875238", "301792", "63762", "801448", "759241", "232733", "771170", "870774", "965009", "827417", "686637", "424776", "438914", "744082", "769598", "884384", "154195", "664706", "949964", "142734", "158548", "608385", "384919", "62015", "827327", "964908", "909335", "414321", "126512", "650123", "405980", "670047", "404603", "968091", "66372", "708301", "847816", "369581", "89114", "857491", "987221", "513067", "754745", "484518", "790943", "589581", "991401", "656865", "280894", "196531", "376155", "892156", "515131", "782555", "282962", "978221", "788170", "72124", "299737", "286855", "516578", "60354", "458842", "969937", "901790", "903687", "22084", "527138", "133937", "374279", "930780", "799809", "462124", "709909", "162745", "57127", "723438", "678745", "833024", "449738", "663733", "673484", "487375", "180099", "95863", "492514", "974453", "765384", "855752", "864264", "164819", "568533", "688683", "156917", "448081", "917064", "12942", "272746", "647181", "352928", "428638", "809971", "278862", "691173", "499044", "502902", "310189", "887338", "777429", "460120", "883619", "426151", "686851", "202573", "821089", "704623", "277250", "859539", "363055", "60003", "674761", "864762", "18620", "845612", "457294", "944125", "218638", "800394", "939660", "387961", "813164", "176363", "541865", "595323", "967117", "246508", "167366", "930783", "791595", "419043", "910497", "761222", "901739", "366477", "728898", "709481", "732288", "254951", "993302", "343624", "892361", "161905", "374079", "347441", "158313", "369615", "287035", "67980", "751340", "468198", "737405", "44067", "538019", "428895", "659756", "776267", "815198", "842482", "602730", "442399", "522940", "844265", "460687", "180520", "665847", "663190", "850074", "139770", "867664", "112524", "480957", "204369", "451283", "408221", "605822", "919045", "994474", "748092", "865874", "243636", "496555", "653591", "387037", "240091", "332898", "863804", "925581", "285156", "282166", "635776", "872559", "629358", "854468", "947154", "870014", "80123", "216549", "267383", "942530", "313229", "375341", "510881", "745292", "156461", "964272", "927774", "317606", "207514", "51777", "946301", "732743", "100925", "554482", "918368", "250395", "292467", "952855", "342011", "356478", "833674", "76488", "648661", "575138", "911529", "198153", "270175", "575429", "203533", "723783", "989644", "702050", "782828", "749970", "633554", "986535", "496471", "289375", "175727", "253804", "205507", "35301", "349034", "348601", "984276", "119513", "974936", "627084", "303316", "979532", "531305", "518639", "507579", "979144", "92264", "163647", "895255", "879641", "900263", "408499", "170883", "359316", "231035", "340206", "629848", "864594", "285787", "835241", "680933", "449910", "356409", "736431", "557543", "962390", "165262", "958706", "778676", "478621", "672161", "617024", "640421", "127883", "552074", "186852", "276965", "342535", "793718", "637155", "610494", "373397", "951194", "689572", "588530", "959041", "469489", "636568", "531764", "209056", "501394", "323000", "572472", "847616", "800493", "735147", "876475", "373765", "909843", "660135", "848244", "89315", "304511", "49581", "509468", "857778", "61797", "711110", "978763", "106524", "395657", "44094", "740977", "287629", "772287", "398224", "255935", "416215", "461336", "391356", "565740", "962137", "370623", "773968", "396195", "414721", "819534", "225133", "562108", "650786", "228323", "924773", "768356", "575905", "160315", "923337", "274683", "471948", "366089", "334361", "827789", "864025", "238407", "711411", "912027", "32864", "963942", "829146", "226933", "91854", "728349", "415218", "660545", "739636", "113049", "526429", "10832", "417669", "931940", "437209", "130289", "286286", "891737", "208535", "476670", "288099", "326885", "373888", "111385", "349244", "249287", "875425", "388680", "940021", "796575", "729189", "148098", "901432", "246029", "226552", "44203", "67013", "227123", "558182", "188488", "842377", "27728", "852798", "768144", "134513", "522966", "376292", "50002", "401170", "644263", "53248", "203212", "417071", "527826", "477819", "238083", "212249", "316113", "68692", "41999", "208455", "920653", "62748", "612162", "23351", "771523", "741761", "855657", "254056", "138435", "12204", "762984", "545714", "633088", "273650", "247315", "179110", "318988", "805462", "780906", "201191", "10671", "853340", "579146", "996978", "347345", "483441", "425064", "101841", "165048", "322134", "302860", "57315", "385495", "938260", "137900", "473304", "564800", "684650", "927659", "376511", "725763", "737110", "402341", "89508", "530520", "892363", "641361", "368861", "69944", "382772", "894515", "259011", "269535", "5636", "458295", "677461", "83000", "383200", "3754", "584417", "829997", "28921", "986297", "971026", "797787", "230803", "978311", "10167", "156754", "46524", "990041", "211871", "200428", "963071", "356307", "965744", "92699", "400707", "754299", "816401", "345665", "279858", "743192", "203845", "391774", "530615", "500198", "165278", "926352", "496835", "943996", "309900", "989847", "857334", "450967", "459856", "377168", "393968", "633564", "661229", "724627", "356917", "580310", "554228", "629497", "348603", "822049", "135968", "392363", "267785", "958001", "425070", "971088", "115176", "583248", "559557", "34835", "439265", "475188", "118057", "21907", "267910", "683189", "134110", "949663", "928452", "585560", "697439", "545431", "657583", "85410", "889906", "116100", "430890", "89661", "84528", "138073", "478095", "296826", "733221", "402462", "634016", "986794", "624817", "511765", "79466", "136527", "302398", "376421", "960583", "549538", "586255", "915727", "559805", "773843", "645550", "287911", "647016", "756485", "723121", "497699", "762185", "329934", "542924", "612497", "611243", "167314", "733528", "981452", "104280", "571047", "840291", "436904", "201175", "680754", "624400", "310804", "808430", "824059", "801523", "460379", "828014", "287126", "548812", "490792", "598923", "543013", "86668", "270464", "998294", "219497", "969927", "165265", "22427", "560422", "752361", "673704", "519569", "549843", "32208", "280014", "308036", "336133", "35840", "862481", "103339", "973774", "783230", "460785", "300583", "168636", "72295", "972156", "488716", "152998", "690078", "927393", "448470", "556181", "134241", "191772", "808962", "103886", "30931", "998114", "250635", "788253", "827085", "381505", "203732", "175654", "180019", "571310", "417477", "16062", "72291", "601359", "341102", "617601", "340988", "326611", "895035", "195312", "649900", "327657", "669588", "524420", "495074", "519536", "764956", "120953", "377217", "814435", "408502", "390377", "444574", "899510", "515884", "685303", "657911", "595223", "980360", "742051", "750697", "240472", "796391", "11758", "197419", "201642", "437708", "35094", "128257", "561758", "643771", "820214", "766083", "397648", "560666", "891969", "911559", "222779", "591363", "275440", "205049", "831018", "35998", "849260", "614274", "228795", "807550", "920327", "10835", "36888", "653161", "202999", "283757", "727557", "172568", "128777", "854917", "417797", "640308", "985597", "919053", "841961", "946915", "582622", "897248", "999107", "643470", "81624", "95060", "675718", "897655", "563580", "91341", "877655", "58233", "677443", "416423", "85083", "689987", "156441", "102507", "86660", "387094", "559575", "963334", "336470", "879833", "419440", "195503", "957752", "500017", "651843", "252769", "286608", "703851", "179122", "548631", "480873", "55603", "870687", "622309", "466312", "254704", "154136", "279037", "964134", "785435", "579428", "141748", "971419", "477272", "995609", "105226", "641769", "27977", "890810", "226783", "385426", "199235", "910540", "669301", "238018", "383290", "730545", "600848", "45100", "182203", "102824", "25088", "666027", "900786", "417976", "966593", "117401", "242784", "671202", "350884", "129439", "83458", "483857", "973108", "704883", "30318", "31264", "462800", "994801", "3858", "144772", "121796", "911569", "907368", "291627", "518080", "429694", "620937", "470475", "887550", "233749", "960205", "686295", "412079", "215292", "539248", "830172", "211502", "231190", "492593", "197592", "117789", "439868", "690212", "701829", "519574", "96305", "75579", "357887", "892308", "508202", "171210", "632278", "166901", "482552", "311152", "153041", "936721", "853954", "298783", "681706", "133692", "956135", "254114", "971368", "796805", "990615", } sort(s[:]) for i:=0;i<len(s);i++{ log.Println(s[i]) } }

     

    Processed: 0.013, SQL: 9