package sort
func Swap(a *int ,b *int){ //c:= *a //*a = *b //*b = c if *a == *b { return } *a = *a ^ *b *b = *a ^ *b *a = *a ^ *b } //1.冒泡排序 //核心在于交换 O(n2) func BubbleSort(arr []int){ j:=len(arr) - 1 for ;j > 0 ; j-- { for i := range(arr[:j]) { if i == len(arr)-1 { break } if arr[i] > arr[i+1] { Swap(&arr[i],&arr[i+1]) } } } } //2.选择排序 //select sort 选出最大放到最后，第二大的数放到倒数第二，一次遍历 排序完成 func SelectSort(arr []int){ j:=len(arr)-1 for ;j > 0 ; j-- { for i := range(arr[:j]) { if i == len(arr)-1 { break } if arr[i] > arr[j] { Swap(&arr[i],&arr[j]) } } } }
var count int //3.快速排序 //核心思想 空出一个位置 以此为基准分成两堆 进行移动 O(nlogn) - n2 func QuickSort(arr []int, left int , right int){ if left >= right { return } count++ low := left high := right base:= arr[low] for low < high { for low < high && arr[high] >= base { high-- } if low < high { //Swap(&arr[low],&arr[high]) arr[low] = arr[high] low++ } for low < high && arr[low] <= base { low++ } if low < high { //Swap(&arr[low],&arr[high]) arr[high] = arr[low] high-- } } //arr[low] = base //中间元素找到位置 arr[low] = base
QuickSort(arr,0,low-1) QuickSort(arr,low+1, right) } //4.堆排序 //大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] //小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] //https://www.cnblogs.com/chengxiao/p/6129630.html //堆排序的时间复杂度为：O(nlogn) func HeapSort(arr []int){ //构建大顶堆 length := len(arr) //最后一个非叶子节点 node=length/2-1 for i:=length/2-1; i >= 0; i--{ AdjustMaxHeapNode(arr,i,length) } Swap(&arr[0],&arr[length-1]) for j := length - 1; j > 1 ; j--{ for i:=j/2-1; i >= 0; i--{ AdjustMaxHeapNode(arr,i,j) } Swap(&arr[0],&arr[j-1]) //AdjustHeap(arr,j/2-1,j) } } func HeapMinSort(arr []int){ //构建小顶堆 length := len(arr) for i:=length/2-1; i >= 0; i--{ AdjustMinHeapNode(arr,i,length) } Swap(&arr[0],&arr[length-1]) for j := length - 1; j > 1 ; j--{ for i:=j/2-1; i >= 0; i--{ AdjustMinHeapNode(arr,i,j) } Swap(&arr[0],&arr[j-1]) //AdjustHeap(arr,j/2-1,j) } } //第一个非叶子结点 arr.length/2-1 //大顶堆交换 func AdjustMaxHeapNode(arr []int,node int, length int){ //交换选出最大 if node < 0 { return } if arr[node] < arr[2*node+1] { Swap(&arr[node],&arr[2*node+1]) } if 2*node+2 <= (length -1) && arr[node] < arr[2*node+2]{ Swap(&arr[node],&arr[2*node+2]) } }
//第一个非叶子结点 arr.length/2-1 //小顶堆交换 func AdjustMinHeapNode(arr []int,node int, length int){ //交换选出最大 if node < 0 { return } if arr[node] > arr[2*node+1] { Swap(&arr[node],&arr[2*node+1]) } if 2*node+2 <= (length -1) && arr[node] > arr[2*node+2]{ Swap(&arr[node],&arr[2*node+2]) } } // minheap 构建k大小最小堆,遍历剩余元素 最后得到的最小堆为 topk 无序 //时间复杂度 nlogk func TopK(arr []int,k int) (topk []int){ length := len(arr) if k >= length { k = length } //构建 k长度最小堆 AdjustHeap(k, arr)
for j := k; j < length; j++ { if arr[0] < arr[j] { Swap(&arr[0], &arr[j]) AdjustHeap(k, arr) } } return arr[:k] }
func AdjustHeap(k int, arr []int) { for i := k/2 - 1; i >= 0; i-- { AdjustMinHeapNode(arr, i, k) } }
//5.插入排序 //插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。 func InsertSort(arr []int){ for i:= range arr{ //第二个元素开始 if i == 0 { continue } index:=i for j := i-1; j >= 0; j-- { if arr[index] < arr[j] { Swap(&arr[index],&arr[j]) index = j //break }else { break } } } } //6.希尔排序，插入排序优化版 //分组插入排序，又叫缩小增量排 2->n组数字进行插入排序 直到无法进行分割 func ShellSort(nums []int) { //外层步长控制 for step := len(nums) / 2; step > 0; step /= 2 { //开始插入排序 for i := step; i < len(nums); i++ { //满足条件则插入 for j := i - step; j >= 0 && nums[j+step] < nums[j]; j -= step { nums[j], nums[j+step] = nums[j+step], nums[j] } } } //return nums } //7.归并排序 归并排序 O（nlogn）/ // 分治法 时间复杂度：O(nlogn) 空间复杂度：O(N) func MergeSort(arr []int, left int, right int){ //mid := len(arr)/2 if(right - left) < 1 { return; } //两个元素排序 =0判断会栈溢出 if(right - left) == 1 { if arr[left] > arr[right] { Swap(&arr[left],&arr[right]) } return } mid := left + ((right - left) >> 1); MergeSort(arr,left,mid) MergeSort(arr,mid,right) //两路合并 Merge(right, left, mid, arr) }
func Merge(right int, left int, mid int, arr []int) { arrLength := right - left + 1 temparr := make([]int, arrLength) rmark := mid lmark := left tempindex := 0 for lmark < mid || rmark <= right { if lmark >= mid { temparr[tempindex] = arr[rmark] tempindex++ rmark++ continue } if rmark > right { temparr[tempindex] = arr[lmark] tempindex++ lmark++ continue } if arr[lmark] < arr[rmark] { temparr[tempindex] = arr[lmark] tempindex++ lmark++ } else { temparr[tempindex] = arr[rmark] tempindex++ rmark++ } } for i := 0; i < arrLength; i++ { arr[left] = temparr[i] left++ } } mergeSort/ //8.桶排序 //工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序 // 对于N个待排数据，M个桶，平均每个桶[N/M]个数据的桶排序平均时间复杂度为： O(N)+O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM) 当N=M时，即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到O(N)。
//bucket:= [20][]int func BucketSort(arr []int){ //init bucket var bucket [][]int for i := 0; i < 20; i++ { tmp := make([]int, 1) bucket = append(bucket, tmp) } //bucket sort for i := 0; i < len(arr); i++ { bucket[arr[i]] = append(bucket[arr[i]], arr[i]) } //拷贝到原数组中 index:=0 for i := 0; i < 20; i++ { if len(bucket[i]) > 1 { for j := 1;j < len(bucket[i]) ;j++ { arr[index] = bucket[i][j] index++ } } } }
