golang 数据结构实现之内部排序（一)

直接上代码：

packagesort

//直接插入排序
funcDirectInsertSort(array[]int)[]int{
len:=len(array)
vartmp,jint
fori:=1;i<len;i++{
ifarray[i]<array[i-1]{
tmp=array[i]
forj=i-1;tmp<array[j];j--{
array[j+1]=array[j]
}
array[j+1]=tmp
}
}
returnarray
}

//折半插入排序
funcBinaryInsertSort(array[]int)[]int{
vartmp,low,high,midint
len:=len(array)
fori:=1;i<len;i++{
tmp=array[i]
low,high=0,i-1
forlow<=high{
mid=(low+high)/2
ifarray[mid]>array[i]{
high=mid-1
}else{
low=mid+1
}
}
forj:=i-1;j>=high+1;j--{
array[j+1]=array[j]
}
array[high+1]=tmp
}
returnarray
}

//冒泡排序
funcBubbleSort(array[]int)[]int{
len:=len(array)
fori:=0;i<len-1;i++{
forj:=len-1;j>i;j--{
ifarray[j-1]>array[j]{
array[j-1],array[j]=array[j],array[j-1]
}
}
}
returnarray
}

//简单选择排序
funcSelectSort(array[]int)[]int{
len:=len(array)
fori:=0;i<len-1;i++{
forj:=len+1;j<len;j++{
ifarray[j-1]>array[j]{
array[j-1],array[j-1]
}
}
}
returnarray
}

//快速排序
funcQuickSort(array[]int)[]int{
quickSort(array,len(array)-1)
returnarray
}

funcquickSort(array[]int,left,rightint){
ifleft<right{
pivotPosition:=partition(array,right)
quickSort(array,pivotPosition-1)
quickSort(array,pivotPosition+1,right)
}
}

funcpartition(array[]int,rightint)int{
pivot:=array[left]
forleft<right{
forleft<right&&array[right]>pivot{
right--
}
array[left]=array[right]
forleft<right&&array[left]<=pivot{
left++
}
array[right]=array[left]
}

array[left]=pivot
returnleft
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!