冒泡排序：
時間複雜度：O(n^2)
穩定性：穩定
<code>//希爾排序//按間隔分組，每組進行插入排序//長度為10，間隔為10/2=5，按(0,5)(1,6)(2,7)(3,8)(4,9)分組//間隔減小為5/2=2，按(0,2,4,6,8)(1,3,5,7,9)分組//組內插入排序時，各組之間交替比較，以間隔為2舉例：先比較0和2，再比較1和3，再比較4，再比較5，依次遍歷//直到間隔為1，按(0,1...9)分組func shellSsort(arr []int) { length := len(arr) //按間隔分組 for gap := length / 2; gap > 0; gap /= 2 { //當前各個分組進行插入排序 for i := gap; i < length; i++ { if arr[i] < arr[i-gap] { temp := arr[i] j := i - gap for ; j >= 0 && temp < arr[j]; j -= gap { arr[j+gap] = arr[j] } arr[j+gap] = temp } } }}/<code>簡單選擇排序：
時間複雜度：O(n^2)
穩定性：不穩定
<code>//歸併排序//將兩個有序序列合併成一個有序序列//取中間值分左右遞歸處理func mergeSort(r []int) []int { length := len(r) if length <= 1 { return r } //左右分別處理 num := length / 2 left := mergeSort(r[:num]) right := mergeSort(r[num:]) //左右兩邊都為有序，進行合併 return merge(left, right)}func merge(left, right []int) (result []int) { l, r := 0, 0 //left或right有一方遍歷完則退出循環 for l < len(left) && r < len(right) { if left[l] < right[r] { result = append(result, left[l]) l++ } else { result = append(result, right[r]) r++ } } //left和right均為有序，直接將剩餘部分加進序列 //如果上面是left遍歷完，left[l:]為[]，right還有剩餘值 //如果上面是right遍歷完，right[r:]為[], left還有剩餘值 result = append(result, left[l:]...) result = append(result, right[r:]...) return}/<code> 直接插入排序：
時間複雜度：O(n^2)
穩定性：穩定
<code>//快速排序//取首位元素為臨界值，一遍循環，臨界值左邊為小數，右邊為大數//遞歸臨界值左邊和右邊func quickSort(arr []int) { length := len(arr) if length <= 1 { return } quick(arr, 0, length-1)}func quick(arr []int, start, end int) { if start >= end { return } i, j := start, end //取首位元素為分界值 temp := arr[i] for i < j { //從右往左找，大的不處理，j-- for i < j && arr[j] >= temp { j-- } //直到遇見第一個小的，跳出上面循環 if i < j { //把小的給i，temp的值沒發生變化 arr[i] = arr[j] i++ } //從左往右找，小的不處理，i++ for i < j && arr[i] <= temp { i++ } //直到遇見第一個大的，跳出上面循環 if i < j { //把大的給j，temp的值沒發生變化 arr[j] = arr[i] j-- } } //把temp給到i位置 arr[i] = temp //遞歸i的左邊，0到i-1 quick(arr, start, i-1) //遞歸i的右邊，i+1到right quick(arr, i+1, end)}/<code>希爾排序：
時間複雜度：O(n^1.5)
穩定性：不穩定
<code>//堆排序//升序使用大頂堆，降序使用小頂堆，以大頂堆為例//頂堆是上下比較大小，父結點與其孩子比較，同一父結點的左右大小無限制，二叉搜索樹是左右比較大小，不要搞混//先調整序列為大頂堆(序列默認是一棵二叉樹，把該二叉樹調整為大頂堆)//處理大頂堆：首尾交換，末位最大，去掉末位，調整剩下序列為大頂堆，循環處理func heapSort(arr []int) []int { length := len(arr) //調整序列為大頂堆 for i := length/2 - 1; i >= 0; i-- { //從最後一個非葉子結點開始，從右往左，從下往上，length/2-1為最後一個非葉子結點 adjustHeap(arr, i, length) } //處理大頂堆 //大頂堆左右無序，上下有序 for i := length - 1; i > 0; i-- { //首位最大，首尾交換，把最大放在隊尾 arr[0], arr[i] = arr[i], arr[0] //去掉隊尾最大元素，所以隊列長度length-1，即為i，把剩餘i個元素調整為大頂堆 //此時只有剛交換的首位不符合大頂堆條件，沒必要像上面循環所有非葉子結點，只需從首位開始調整，所以i=0 adjustHeap(arr, 0, i) } return arr}//調整二叉樹為大頂堆func adjustHeap(arr []int, i, length int) { //非葉子結點i的左右孩子 left := 2*i + 1 right := 2*i + 2 //默認i為最大 max := i //存在左孩子且左孩子大，最大指向left，因為右孩子可能更大，所以暫不交換 if left < length && arr[left] > arr[max] { max = left } //存在右孩子且右孩子更大，最大指向right if right < length && arr[right] > arr[max] { max = right } //最大發生過改變，交換 if max != i { arr[i], arr[max] = arr[max], arr[i] //最後一層非葉子結點，遞歸時不發生交換操作； //假如二叉樹深度為4，最後一層非葉子結點為第三層，處理第二層發生交換時，需要遞歸處理第三層是否被影響了 adjustHeap(arr, max, length) }}/<code> 歸併排序：
時間複雜度：O(nlogn)
穩定性：穩定
<code>//基數排序//分配式排序，桶子法，非負數，共0-9，10個桶子//首次循環根據元素個位數，將元素分配至對應桶子裡，0進0號桶，9進9號桶//按桶子排序，再次循環，根據元素十位數再次分配func radixSort(arr []int) { length := len(arr) if length <= 1 { return } //元素的最大位數 d := maxBit(arr) //用mod和dev求對應位數上的數值 mod, dev := 10, 1 //循環位數 for i := 0; i < d; i++ { //10個桶子 temp := [10][]int{} //遍歷序列 for j := 0; j < length; j++ { //先求餘，再求商 //個位數值：x%10/1；十位數值：x%100/10 bucket := arr[j] % mod / dev //按位存值 temp[bucket] = append(temp[bucket], arr[j]) } //為arr排序時的下標 k := 0 //排序arr for m := 0; m < 10; m++ { for n := 0; n < len(temp[m]); n++ { arr[k] = temp[m][n] k++ } } //為下一位做準備 mod *= 10 dev *= 10 }}//基數排序//分配式排序，桶子法，存在負數，共0-19，20個桶子//首次循環根據元素個位數，將元素分配至對應桶子裡，-9進1號桶，-1進9號桶，0進10號桶，1進11號桶，19進19號桶//按桶子排序，再次循環，根據元素十位數再次分配func radixSort(arr []int) { length := len(arr) if length <= 1 { return } //元素的最大位數 d := maxBit(arr) //用mod和dev求對應位數上的數值 mod, dev := 10, 1 //循環位數 for i := 0; i < d; i++ { //10個桶子 temp := [20][]int{} //遍歷序列 for j := 0; j < length; j++ { //先求餘，再求商，下標不為負，+10保證為非負數 //個位數值：x%10/1+10；十位數值：x%100/10+10 bucket := (arr[j] % mod / dev)+10 //按位存值 temp[bucket] = append(temp[bucket], arr[j]) } //為arr排序時的下標 k := 0 //排序arr for m := 0; m < 20; m++ { for n := 0; n < len(temp[m]); n++ { arr[k] = temp[m][n] k++ } } //為下一位做準備 mod *= 10 dev *= 10 }}//元素的最大位數func maxBit(arr []int) int { length := len(arr) d := 1 p := 10 for i := 0; i < length; i++ { for arr[i] >= p { d++ p *= 10 } } return d}/<code>快速排序：
時間複雜度：O(nlogn)
穩定性：不穩定
<code>//快速排序//取首位元素為臨界值，一遍循環，臨界值左邊為小數，右邊為大數//遞歸臨界值左邊和右邊func quickSort(arr []int) { length := len(arr) if length <= 1 { return } quick(arr, 0, length-1)}func quick(arr []int, start, end int) { if start >= end { return } i, j := start, end //取首位元素為分界值 temp := arr[i] for i < j { //從右往左找，大的不處理，j-- for i < j && arr[j] >= temp { j-- } //直到遇見第一個小的，跳出上面循環 if i < j { //把小的給i，temp的值沒發生變化 arr[i] = arr[j] i++ } //從左往右找，小的不處理，i++ for i < j && arr[i] <= temp { i++ } //直到遇見第一個大的，跳出上面循環 if i < j { //把大的給j，temp的值沒發生變化 arr[j] = arr[i] j-- } } //把temp給到i位置 arr[i] = temp //遞歸i的左邊，0到i-1 quick(arr, start, i-1) //遞歸i的右邊，i+1到right quick(arr, i+1, end)}/<code>堆排序：
時間複雜度：O(nlogn)
穩定性：不穩定
<code>//堆排序//升序使用大頂堆，降序使用小頂堆，以大頂堆為例//頂堆是上下比較大小，父結點與其孩子比較，同一父結點的左右大小無限制，二叉搜索樹是左右比較大小，不要搞混//先調整序列為大頂堆(序列默認是一棵二叉樹，把該二叉樹調整為大頂堆)//處理大頂堆：首尾交換，末位最大，去掉末位，調整剩下序列為大頂堆，循環處理func heapSort(arr []int) []int { length := len(arr) //調整序列為大頂堆 for i := length/2 - 1; i >= 0; i-- { //從最後一個非葉子結點開始，從右往左，從下往上，length/2-1為最後一個非葉子結點 adjustHeap(arr, i, length) } //處理大頂堆 //大頂堆左右無序，上下有序 for i := length - 1; i > 0; i-- { //首位最大，首尾交換，把最大放在隊尾 arr[0], arr[i] = arr[i], arr[0] //去掉隊尾最大元素，所以隊列長度length-1，即為i，把剩餘i個元素調整為大頂堆 //此時只有剛交換的首位不符合大頂堆條件，沒必要像上面循環所有非葉子結點，只需從首位開始調整，所以i=0 adjustHeap(arr, 0, i) } return arr}//調整二叉樹為大頂堆func adjustHeap(arr []int, i, length int) { //非葉子結點i的左右孩子 left := 2*i + 1 right := 2*i + 2 //默認i為最大 max := i //存在左孩子且左孩子大，最大指向left，因為右孩子可能更大，所以暫不交換 if left < length && arr[left] > arr[max] { max = left } //存在右孩子且右孩子更大，最大指向right if right < length && arr[right] > arr[max] { max = right } //最大發生過改變，交換 if max != i { arr[i], arr[max] = arr[max], arr[i] //最後一層非葉子結點，遞歸時不發生交換操作； //假如二叉樹深度為4，最後一層非葉子結點為第三層，處理第二層發生交換時，需要遞歸處理第三層是否被影響了 adjustHeap(arr, max, length) }}/<code> 基數排序：
時間複雜度：O(d(n+r))
穩定性：穩定
<code>//基數排序//分配式排序，桶子法，非負數，共0-9，10個桶子//首次循環根據元素個位數，將元素分配至對應桶子裡，0進0號桶，9進9號桶//按桶子排序，再次循環，根據元素十位數再次分配func radixSort(arr []int) { length := len(arr) if length <= 1 { return } //元素的最大位數 d := maxBit(arr) //用mod和dev求對應位數上的數值 mod, dev := 10, 1 //循環位數 for i := 0; i < d; i++ { //10個桶子 temp := [10][]int{} //遍歷序列 for j := 0; j < length; j++ { //先求餘，再求商 //個位數值：x%10/1；十位數值：x%100/10 bucket := arr[j] % mod / dev //按位存值 temp[bucket] = append(temp[bucket], arr[j]) } //為arr排序時的下標 k := 0 //排序arr for m := 0; m < 10; m++ { for n := 0; n < len(temp[m]); n++ { arr[k] = temp[m][n] k++ } } //為下一位做準備 mod *= 10 dev *= 10 }}//基數排序//分配式排序，桶子法，存在負數，共0-19，20個桶子//首次循環根據元素個位數，將元素分配至對應桶子裡，-9進1號桶，-1進9號桶，0進10號桶，1進11號桶，19進19號桶//按桶子排序，再次循環，根據元素十位數再次分配func radixSort(arr []int) { length := len(arr) if length <= 1 { return } //元素的最大位數 d := maxBit(arr) //用mod和dev求對應位數上的數值 mod, dev := 10, 1 //循環位數 for i := 0; i < d; i++ { //10個桶子 temp := [20][]int{} //遍歷序列 for j := 0; j < length; j++ { //先求餘，再求商，下標不為負，+10保證為非負數 //個位數值：x%10/1+10；十位數值：x%100/10+10 bucket := (arr[j] % mod / dev)+10 //按位存值 temp[bucket] = append(temp[bucket], arr[j]) } //為arr排序時的下標 k := 0 //排序arr for m := 0; m < 20; m++ { for n := 0; n < len(temp[m]); n++ { arr[k] = temp[m][n] k++ } } //為下一位做準備 mod *= 10 dev *= 10 }}//元素的最大位數func maxBit(arr []int) int { length := len(arr) d := 1 p := 10 for i := 0; i < length; i++ { for arr[i] >= p { d++ p *= 10 } } return d}/<code>元旦快樂！
分享到:
閱讀更多 南方有嘉木1993 的文章
