排序算法是在生活中隨處可見，也是算法基礎(chǔ)，因?yàn)槠鋵?shí)現(xiàn)代碼較短,應(yīng)用較常見。所以在面試中經(jīng)常會(huì)問到排序算法及其相關(guān)的問題，可以說是每個(gè)程序員都必須得掌握的了。為了方便大家學(xué)習(xí)，花了一天的時(shí)間用Go語言實(shí)現(xiàn)一下常用的算法且整理了一下，如有需要可以參考。

冒泡排序

思路：從前往后對(duì)相鄰的兩個(gè)元素依次進(jìn)行比較，讓較大的數(shù)往下沉，較小的網(wǎng)上冒，即每當(dāng)兩個(gè)相鄰的元素比較后發(fā)現(xiàn)他們的排序要求相反時(shí)，就將它們互換。

時(shí)間復(fù)雜度：O(N^2)

空間復(fù)雜度：O(1)

func main() {
	fmt.Println(bubbleSort([]int{2, 4, 1, 6, 3}))
}

func bubbleSort(list []int) []int {
	lenth := len(list)
	for i := 0; i <= lenth; i++ {//循環(huán)對(duì)比的輪數(shù)
		exchange := false
		for j := 1; j < lenth-i; j++ {//當(dāng)前輪相鄰元素循環(huán)對(duì)比
			if list[j-1] > list[j]{//如果前邊的大于后邊的
				list[j-1], list[j] = list[j], list[j-1]//交換數(shù)據(jù)
				exchange = true
			}
		}
		if !exchange {
			break
		}
	}
	return list
}

快速排序

思路：以一個(gè)基準(zhǔn)數(shù)將數(shù)組拆分為兩組，一邊大于這個(gè)數(shù)，一邊小于這個(gè)數(shù)，再最左右兩個(gè)組重復(fù)這個(gè)過程，直到各個(gè)區(qū)域只有一個(gè)數(shù)。

時(shí)間復(fù)雜度：O(nlogn)

空間復(fù)雜度：O(1)

func quickSort(list []int) []int {
	length := len(list)
	if length <= 1 {
		return list
	}
	//基準(zhǔn)值
	base := list[0]
    left := make([]int, 0)
	right := make([]int, 0)
	for i := 1; i < length; i++ {
		if list[i]  > base {
			right  = append(right, list[i])
		} else {
			left = append(left, list[i])
		}
	}
	left, right  = quickSort(left), quickSort(right)
	return append(append(left, base),right...)
}

選擇排序

思路：首先找到數(shù)組中的最小元素，然后將這個(gè)最小元素和數(shù)組的第一個(gè)元素交換位置，如果第一個(gè)元素就是最小元素，就和自己交換位置；再次，在剩下的元素中找到最小元素和數(shù)組中的第二個(gè)元素交換位置，如此往復(fù)，直到將整個(gè)數(shù)組排序，一句話總結(jié)就是，不斷在剩余元素中找最小元素。

時(shí)間復(fù)雜度：O(n^2)

空間復(fù)雜度：O(1)

func selectSort(list []int) []int {
	length := len(list)

	for i := 0; i < length; i++ {
		minIndex := i
		//每次循環(huán)找出i+1到最后一個(gè)元素區(qū)間的最小值，然后當(dāng)前元素和當(dāng)前最小值比較
		for j := i + 1; j < length; j++ {
			if list[j] < list[minIndex] {
				minIndex = j
			}
		}
		if i != minIndex {
			list[i], list[minIndex] = list[minIndex], list[i]
		}
	}
	return list
}

插入排序

思路：與選擇排序一樣，當(dāng)前索引左邊的所有元素都是有序的，但是他們的最終位置還不確定，為了給更小的元素騰出空間，他們可能會(huì)被移動(dòng)，但是當(dāng)索引到達(dá)數(shù)組的末端，數(shù)組排序就完成了。

時(shí)間復(fù)雜度：O(N^2)

空間復(fù)雜度：O(1)

func insertSort(list []int) []int {
	length := len(list)
	for i := 0; i < length; i++ {
		for j := i; j > 0; j-- {
			if list[j] > list[j-1] {
				break
			}
			list[j], list[j-1] = list[j-1], list[j]
		}
	}
	return list
}

排序思路算法幾乎一樣。暫時(shí)就介紹這幾種常用的也是面試中經(jīng)常問道的排序算法。

到此這篇關(guān)于Go語言實(shí)現(xiàn)常用排序算法的示例代碼的文章就介紹到這了,更多相關(guān)Go語言排序算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: