一、冒泡排序
type bubbleSort []int
func (s bubbleSort) Sort() {
   for i := 0; i < len(s)-1; i++ {
      for j:=len(s)-1; j > i; j-- {
         if s[j] < s[j-1] {
            s[j], s[j-1] = s[j-1], s[j]
         }
      }
   }
}

 

二、选择排序

type selectSort []int
func (s selectSort) Sort() {
   for i := 0; i < len(s) - 1; i++ {
      min := i
      for j := i + 1; j < len(s); j ++ {
         if s[j] < s[min] {
            min = j
         }
      }

      s[min], s[i] = s[i], s[min]
   }
}

三、快速排序

type quickSort []int
func (s quickSort) Sort() {
   s.binarySort(0, len(s)-1)
}
func (s quickSort) binarySort(start, end int) {
   if start >= end {
      return
   }

   temp := s[start]
   i := start
   j := end
   for i < j {
      for ;s[j] > temp && i < j; j--{}
      if i >= j {
         break
      }
      s[i] = s[j]
      i++

      for ;s[i] <= temp && i < j; i++{}
      if i >= j {
         break
      }
      s[j] = s[i]
      j--
   }

   s[i] = temp
   s.binarySort(start, i-1)
   s.binarySort(i+1, end)
}

四、插入排序

type insertSort []int
func (s insertSort) Sort() {
   for i := 1; i < len(s); i++ {
      temp := s[i]
      for j := 0; j < i; j ++ {
         if s[j] > temp {
            for k := i; k > j; k-- {
               s[k] = s[k-1]
            }
            s[j] = temp
            break
         }
      }
   }
}

五、希尔排序

type shellSort []int
func (s shellSort) Sort() {
   l := len(s)
   for step := l / 2; step > 0; step = step/2 {
      for offset := 0; offset < step; offset++ {
         for i := offset + step; i < l; i+=step {
            temp := s[i]
            j := i - step
            for ; j >= 0; j -= step {
               if s[j] < temp {
                  break
               }
            }
            for k := i; k > j+step; k -= step {
               s[k] = s[k - step]
            }
            s[j + step] = temp
         }
      }
   }
}

六、基数排序

type radixSort []int
func (s radixSort) Sort() {
   if len(s) == 0 {
      return
   }

   max := s[0]
   for i := 1; i < len(s); i++ {
      if s[i] > max {
         max = s[i]
      }
   }
   for radix := 1; radix < max; radix *= 10 {
      s.bucketSort(radix)
   }
}
func (s radixSort) bucketSort(radix int) {
   l := len(s)
   var bucketSize [10]int
   temp := make([]int, l)

   for _,v := range s {
      bucketSize[(v/radix)%10]++
   }

   for i := 1; i < 10; i++ {
      bucketSize[i] += bucketSize[i-1]
   }

   for i := l - 1; i >= 0; i-- {
      v := s[i]
      temp[bucketSize[(v/radix)%10]-1] = v
      bucketSize[(v/radix)%10]--
   }

   for i := 0; i < l; i++ {
      s[i] = temp[i]
   }
}

七、归并排序

type mergeSort []int
func (s mergeSort) Sort() {
   s.part(0, len(s)-1)
}
func (s mergeSort) part(start, end int) {
   if start >= end {
      return
   }

   mid := (start+end)/2
   s.part(start, mid)
   s.part(mid+1, end)
   s.merge(start, mid, end)
}

 

func (s mergeSort) merge(start, mid, end int) {
   temp := make([]int, end-start+1)
   pos := 0
   lc := start
   rc := mid+1

   for lc <= mid && rc <= end {
      if s[lc] < s[rc] {
         temp[pos] = s[lc]
         lc++
      } else {
         temp[pos] = s[rc]
         rc++
      }
      pos++
   }

   for lc <= mid {
      temp[pos] = s[lc]
      lc++
      pos++
   }
   for rc <= end {
      temp[pos] = s[rc]
      rc++
      pos++
   }

   pos = 0
   for i := start; i<=end; i++ {
      s[i] = temp[pos]
      pos++
   }
}

八、堆排序

type heapSort []int
func (s heapSort) Sort() {
   end := len(s) - 1
   if end <= 0 {
      return
   }
   s.BuildMaxHeap(end)

   for i := 0; i < end;  {
      s[0], s[end - i] = s[end - i], s[0]
      i++
      s.DownToLeaf(0, end - i)
   }
}

 

func (s heapSort) BuildMaxHeap(end int) {
   if end <= 0 {
      return
   }

   root := (end + 1)/2 - 1
   for; root >=0; root-- {
      s.DownToLeaf(root, end)
   }
}

 

func (s heapSort) DownToLeaf(root int, end int) {
   for root*2 + 1 <= end {
      leaf := root*2 + 1
      if leaf + 1 <= end && s[leaf] < s[leaf+1] {
         leaf++
      }

      if s[root] >= s[leaf] {
         break
      }
      s[root], s[leaf] =  s[leaf], s[root]
      root = leaf
   }
}