Golang實(shí)現(xiàn)常見排序算法的示例代碼

第Golang實(shí)現(xiàn)常見排序算法的示例代碼目錄前言五種基礎(chǔ)排序算法對比1、冒泡排序2、選擇排序3、插入排序4、快速排序

前言

現(xiàn)在的面試真的是越來越卷了，算法已經(jīng)成為了面試過程中必不可少的一個(gè)環(huán)節(jié)，你如果想進(jìn)稍微好一點(diǎn)的公司，「算法是必不可少的一個(gè)環(huán)節(jié)」。那么如何學(xué)習(xí)算法呢很多同學(xué)的第一反應(yīng)肯定是去letcode上刷題，首先我并不反對刷題的方式，但是對于一個(gè)沒有專門學(xué)習(xí)過算法的同學(xué)來說，刷題大部分是沒什么思路的，花一個(gè)多小時(shí)暴力破解一道題意義也不大，事后看看別人比較好的解法大概率也記不住，所以我覺得「專門針對算法進(jìn)行一些簡單的訓(xùn)練」是很有必要的，正好我自己最近也在學(xué)習(xí)，同時(shí)把學(xué)習(xí)成果同步更新在公眾號(hào)上，可能會(huì)更很多期，希望能幫助到你。另外最近很多同學(xué)也都在學(xué)習(xí)go，所以我就用go代碼演示算法。今天咱們閑話不用多說，就從最簡單的開始。

五種基礎(chǔ)排序算法對比

五種基礎(chǔ)排序算法對比

1、冒泡排序

算法描述

比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換它們兩個(gè)。對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對，這樣在最后的元素應(yīng)該會(huì)是最大的數(shù)。針對所有的元素重復(fù)以上的步驟，除了最后一個(gè)。重復(fù)步驟1~3，直到排序完成。

代碼演示

funcbubbleSort(arr[]int)[]int{

iflen(arr)=1{

returnarr

fore:=len(arr)-1;ee--{

fori:=0;ii++{

ifarr[i]arr[i+1]{

Swap(arr,i,i+1)//交換元素

returnarr

funcSwap(arr[]int,i,jint)[]int{

temp:=arr[j]

arr[j]=arr[i]

arr[i]=temp

returnarr

}

2、選擇排序

算法描述

n個(gè)記錄的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果。具體算法描述如下：

將假想墻放置在數(shù)字列表最左側(cè)，墻的左側(cè)為已排序子列表，右側(cè)為未排序子列表。找出(選擇)未排序子列表中的最小(或最大)元素。把選擇的元素與未排序列表中第一個(gè)元素進(jìn)行交換。將假想墻向右移動(dòng)一個(gè)位置。反復(fù)執(zhí)行2至4步操作，直至整個(gè)數(shù)字列表排序完成(需要n-1輪)。

代碼演示

funcselectSort(arr[]int)[]int{

iflen(arr)=1{

returnarr

fori:=0;ilen(arr);i++{

varminIndexint=i

forj:=i+1;jlen(arr);j++{

ifarr[j]arr[minIndex]{

minIndex=j

arr=Swap(arr,i,minIndex)

returnarr

funcSwap(arr[]int,i,jint)[]int{

temp:=arr[j]

arr[j]=arr[i]

arr[i]=temp

returnarr

}

3、插入排序

算法描述

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

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

代碼實(shí)現(xiàn)

funcinsertSort(arr[]int)[]int{

iflen(arr)=1{

returnarr

fori:=1;ilen(arr);i++{

forj:=i-1;jj--{

ifarr[j]arr[j+1]{

Swap(arr,j,j+1)

returnarr

funcSwap(arr[]int,i,jint)[]int{

temp:=arr[j]

arr[j]=arr[i]

arr[i]=temp

returnarr

}

4、快速排序

算法描述

快速排序的基本思想：通過一趟排序?qū)⒋庞涗浄指舫瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。

從數(shù)列中挑出一個(gè)元素，稱為基準(zhǔn)(pivot)。重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面(相同的數(shù)可以到任一邊)。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)(partition)操作。遞歸地(recursive)把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。

代碼實(shí)現(xiàn)

//快速排序

funcquickSort(arr[]int)[]int{

iflen(arr)=1{

returnarr

middle:=arr[0]

varleft[]int

varright[]int

fori:=1;ilen(arr);i++{

ifarr[i]middle{

right=append(right,arr[i])

}else{

left=append(left,arr[i])

middle_s:=[]int{middle}

left=quickSort(left)

right=quickSort(ri