快速排序算法实现(非递归)

Jaden · · 963 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

GO语言非递归实现快速排序算法

func QuickSort2(src []int) {
   SubSeqSet := make([][]int, 0)
   SubSeqSet = append(SubSeqSet, src)
   for len(SubSeqSet) > 0 {
      // pop one sequence
      subSeq := SubSeqSet[len(SubSeqSet)-1]
      SubSeqSet = SubSeqSet[:len(SubSeqSet)-1]
     
      //seq count <= 1
      if len(subSeq) <= 1 {
         continue
      }
      
      midIndex := QuickSortSub(subSeq)
      
      if midIndex > 0 {
         SubSeqSet = append(SubSeqSet, subSeq[:midIndex])
      }
      
      if midIndex < len(subSeq)-2 {
         SubSeqSet = append(SubSeqSet, subSeq[midIndex+1:])
      }
   }
}

// 只进行一趟排序, 返回中间位置
func QuickSortSub(src []int) int {
   midV := src[0]
   length := len(src)
   leftIndex := 1
    rightIndex := length - 1
    for leftIndex <= rightIndex {
      for leftIndex < length && src[leftIndex] <= midV {
         leftIndex++
      }
      for rightIndex > 0 && src[rightIndex] > midV {
         rightIndex--
      }
      
      //swap
      if leftIndex < rightIndex {
         src[leftIndex], src[rightIndex] = src[rightIndex], src[leftIndex]
      }
   }
   
   //recursion sort sub src
   if rightIndex > 0 {
      src[0], src[rightIndex] = src[rightIndex], src[0]
   }
   return rightIndex
}

有疑问加站长微信联系（非本文作者）