用Go汇编实现一个快速排序算法

本代码全网首发，使用Go plan9 windows arm64汇编，实现基础版快速排序算法。

未引入随机因子的快速排序的普通Go代码长这样。

func QuickSort(arr []int) {if len(arr) <= 1 {return}base, l, r := arr[0], 0, len(arr)-1for i := 1; i <= r; {if arr[i] > base {arr[i], arr[r] = arr[r], arr[i]r--continue}arr[i], arr[l] = arr[l], arr[i]l, i = l+1, i+1}QuickSort(arr[:l])QuickSort(arr[l+1:])
}

如下，使用windows arm64 Go plan9汇编实现的快速排序。

file: quickSort.s

#include "textflag.h"
// func QuickSortByASM(slice []int)
TEXT ·QuickSortByASM(SB), $104-24// NO_LOCAL_POINTERSMOVD R0 , tmp-8*3(SP);  MOVD R1 , tmp-8*4(SP)MOVD R2 , tmp-8*5(SP);  MOVD R3 , tmp-8*6(SP)MOVD R4 , tmp-8*7(SP);  MOVD R5 , tmp-8*8(SP)MOVD R6 , tmp-8*9(SP);  MOVD R7 , tmp-8*10(SP)MOVD R8 , tmp-8*11(SP); MOVD R9 , tmp-8*12(SP)MOVD R10, tmp-8*13(SP)MOVD slice+0(FP), R0    // arrayPtrMOVD slice+8(FP), R1    // arrayLengthMOVD $0, R2             // l_indexMOVD R1, R3             // r_index = arrayLengthSUB  $1, R3             // r_index -= 1MOVD $0, R4             // pointer1MOVD $0, R5             // pointer2MOVD $8, R6             // dataSizeMOVD $1,   R7           // indexMOVD (R0), R8           // base   TODO random indexMOVD $0,   R9CMP $1, R1; BLE LABEL_END       // if arrayLength <= 1 return
LABEL_FOR_START:CMP R3, R7; BGT LABEL_FOR_END   // if index > r_index returnMOVD R7, R4      // offset = indexMUL  R6, R4      // offset *= dataSizeADD R0,  R4      // arr[i] = R4MOVD (R4), R5    // arr[i]CMP R8, R5; BLE LABEL_SWAP // if arr[i] <= baseMOVD R3, R5      // offset = r_indexMUL  R6, R5      // offset *= dataSizeADD  R0, R5      // arr[r]MOVD (R5), R9    // tmp     = arr[r]MOVD (R4), R10   // tmp1    = arr[i]MOVD R10, (R5)   // arr[r]  = arr[i]MOVD R9, (R4)    // arr[i]  = tmpSUB  $1, R3       // r_index -= 1JMP LABEL_FOR_START
LABEL_SWAP:MOVD R7, R4MUL  R6, R4ADD  R0, R4MOVD R2, R5MUL  R6, R5ADD  R0, R5MOVD (R4), R9  // tmp = arr[i]MOVD (R5), R10 // tmp1 = arr[l]MOVD R10, (R4) // arr[i] = tmp1MOVD R9, (R5)  // arr[l] = tmpADD $1, R2     // l_index += 1ADD $1, R7     // index += 1JMP LABEL_FOR_START
LABEL_FOR_END:MOVD R0, R4MOVD R2, R5MOVD R4, tmp-104(SP)MOVD R5, tmp-96(SP)CALL ·QuickSortByASM(SB)MOVD R2, R4ADD  $1, R4MUL  R6, R4ADD  R0, R4  // right addressMOVD R1, R5  // tmp = arrayLengthSUB  R2, R5  // tmp -= l_indexSUB $1,  R5MOVD R4, tmp-104(SP)MOVD R5, tmp-96(SP)CALL ·QuickSortByASM(SB)
LABEL_END:MOVD  tmp-8*3(SP),  R0; MOVD  tmp-8*4(SP),  R1MOVD  tmp-8*5(SP),  R2; MOVD  tmp-8*6(SP),  R3MOVD  tmp-8*7(SP),  R4; MOVD  tmp-8*8(SP),  R5MOVD  tmp-8*9(SP),  R6; MOVD  tmp-8*10(SP), R7MOVD  tmp-8*11(SP),  R8;MOVD  tmp-8*12(SP), R9MOVD  tmp-8*13(SP), R10RET

该汇编版本快排基于普通版快排手写而成， 未加入stackmap信息，大数据量样本可能会出现panic，仅供参考。

对数器

package mainimport ("fmt""math/rand""sort"
)func QuickSortByASM(slice []int) // 汇编函数声明func main() {N := 50for index := 0; index < 1000; index++ {slice := make([]int, N)for i := 0; i < N; i++ {slice[i] = rand.Int()}slice1 := make([]int, N)slice2 := make([]int, N)for i, v := range slice {slice1[i] = vslice2[i] = v}sort.Ints(slice1)QuickSortByASM(slice2)for i := 0; i < N; i++ {if slice1[i] != slice2[i] {fmt.Println(slice)fmt.Println(slice1)fmt.Println(slice2)panic(i)}}}fmt.Println("pass")
}

pass