快排
访问量:525

一、简介

思路:从线性表中选取一个元素,设为T,然后将线性表该位置后面小于T的元素移到前面,而前面大于T的元素移到后面,这样线性表分成了两部分(两个子表),T插入到分界线的位置处。然后对分割后的子表继续进行分割,一直到所有的子表为空为止。

二、实现

func QuickSort(data []int) []int {
   return QuickSortC(data, 0, len(data)-1)
}

// 以data[left]对应的值flag 为基准点,将data元素划分区域
// 左边的元素都小于或等于flag
// 右边边的元素都大于于或等于flag
func QuickSortC(data []int, start, end int) []int {
   if start >= end {
      return data
   }

   flag := data[start]
   left := start
   right := end
   for left < right {
      // 从右边寻找小于 flag填充左边
      for left < right {
         if data[right] > flag {
            right --
            continue
         }

         data[left] = data[right]
         left ++
         break
      }

      // 从左边寻找大于flag填充右边
      for left < right {
         if data[left] < flag {
            left ++
            continue
         }

         data[right] = data[left]
         right --
         break
      }
   }

   data[right] = flag
   // 左边排序
   if start < left {
      QuickSortC(data, start, left-1)
   }

   // 右边排序
   if left < end {
      QuickSortC(data, left+1, end)
   }

   return data
}