Quicksort

原文链接： Quicksort

动画展示
1）在数据集之中，选择一个元素作为"基准" pivot
2）所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
3）对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

（1）分解：数组A[p...r]被划分为两个（可能为空）子数组A[p...q-1]和A[q+1...r]，给定一个枢轴，使得A[p...q-1]中的每个元素小于等于A[q]，A[q+1...r]中的每个元素大于等于A[q]，q下标是在划分过程中计算得出的。
（2）解决：通过递归调用快速排序，对子数组A[p...q-1]和A[q+1...r]进行排序。
（3）合并：因为两个子数组是就地排序，不需要合并操作，整个数组A[p…r]排序完成。

func quickSort(values []int, left int, right int) {
	if left < right {
		// 设置基准值
		pivot := values[left]
		// 设置哨兵
		l, r := left, right
		for {

			// 从左向右找，找到第一个比基准值大的数
			for values[l] <= pivot && l < r {
				l++
            }
            			// 从右向左找，找到第一个比基准值小的数
			for values[r] >= pivot && l < r {
				r--
			}
			// 如果哨兵相遇，则退出循环
			if l >= r {
				break
			}
			// 交换左右两侧的值
			values[l], values[r] = values[r], values[l]
		}
		// 将基准值移到哨兵相遇点
		values[left] = values[l]
		values[l] = pivot
		// 递归，左右两侧分别排序
		quickSort(values, left, l-1)
		quickSort(values, l+1, right)
	}
}

快速排序的原理是，首先找到一个数pivot把数组‘平均'分成两组，使其中一组的所有数字均大于另一组中的数字，此时pivot在数组中的位置就是它正确的位置。然后，对这两组数组再次进行这种操作。

    //快速排序（排序10000个随机整数，用时约0.9ms）  
    func quickSort(nums []int) {  
        recursionSort(nums, 0, len(nums)-1)  
    }  
      
    func recursionSort(nums []int, left int, right int) {  
        if left < right {  
            pivot := partition(nums, left, right)  
            recursionSort(nums, left, pivot-1)  
            recursionSort(nums, pivot+1, right)  
        }  
    }  
      
    func partition(nums []int, left int, right int) int {  
        for left < right {  
            for left < right && nums[left] <= nums[right] {  
                right--  
            }  
            if left < right {  
                nums[left], nums[right] = nums[right], nums[left]  
                left++  
            }  
      
            for left < right && nums[left] <= nums[right] {  
                left++  
            }  
            if left < right {  
                nums[left], nums[right] = nums[right], nums[left]  
                right--  
            }  
        }  
        return left  
    }

无需额外编写partition函数，直接使用一个函数递归实现快排。

gopackage main

import "fmt"

func quickSort(arr []int, left, right int) {
    if left < right {
        i, j := left, right
        key := arr[(left+right)/2]
        for i <= j {
            for arr[i] < key {
                i++
            }
            for arr[j] > key {
                j--
            }
            if i <= j {
                arr[i], arr[j] = arr[j], arr[i]
                i++
                j--
            }
        }

        if left < j {
            quickSort(arr, left, j)
        }
        if right > i {
            quickSort(arr, i, right)
        }
    }
}

并行版

语言写的并行排序算法（快速排序）

package main
import "fmt"
 
// threads 线程标识创建线程的个数
func quicksort(nums []int, ch chan int, level int, threads int) {
  level=level*2
  if len(nums) == 1 {  ch<- nums[0]; close(ch); return }//ch<-nums[0] 表示将nums[0] 数据写到ch通道中
  if len(nums) == 0 {  close(ch); return }
  
  less := make([]int, 0)//
  greater := make([]int,0)
  left := nums[0] //快速排序的轴
  nums = nums[1:] 

  //从左向右扫描数据 大于轴的放到greater里小于的放到less中
  for _,num_data := range nums{
    switch{
    case num_data <= left:
      less = append(less,num_data) 
    case num_data > left:
      greater = append(greater,num_data)
    }
  }

  left_ch := make(chan int, len(less)) 
  right_ch := make(chan int, len(greater))
  
  if(level <= threads){
    go quicksort(less, left_ch, level, threads) //分任务
    go quicksort(greater,right_ch, level, threads)
  }else{
    quicksort(less,left_ch, level, threads)
    quicksort(greater,right_ch, level, threads)
  }
  
  //合并数据
  for i := range left_ch{
    ch<-i;
  }
  ch<-left
  for i := range right_ch{
    ch<-i;
  }
  close(ch)
  return
}

func main() {
    x := []int{3, 1, 4, 1, 5, 9, 2, 6}
    ch := make(chan int)
    go quicksort(x, ch, 0, 0) // 0 0 表示不限制线程个数
    for v := range(ch) {
        fmt.Println(v)
    }
}

package quicksort

func Sort(values []int) {
    sort(values, 0, len(values)-1)
}

func sort(values []int, l int, r int) {
    if l >= r {
        return
    }
//左基准
    pivot := values[l]
    i := l + 1

    for j := l; j <= r; j++ {
        if pivot > values[j] {
            values[i], values[j] = values[j], values[i]
            i++
        }
    }

    values[l], values[i-1] = values[i-1], pivot

    sort(values, l, i-2)
    sort(values, i, r)
}

/*
	老毛桃 (Lomuto) 快排：
	以最右位置为基点比较元素，递归模板中不返回排序完的数组，而是返回遍历后基点比较元素应该所在的位置下标p，
	左边分区（包含小于等于基点元素的元素）是相对p值的低值数组，右边分区（包含大于基点元素的元素）
	是相对p值的高值数组。
	评价——
	比霍尔快排简单但是性能稍差。
	关键点——
	基点比较元素（pivot）
	遍历索引
	低值数组锚点
*/
func LomutoSort(list []int, low int, high int){
	if low >= high {return}

	//[[----递归模板区
	pivot := list[high]
	i := low
	for j := low+1; j < high; j++ {
		if list[j] <= pivot {
			list[i], list[j] = list[j], list[i]
			i ++
		}
	}

	list[i], list[high] = list[high], list[i]
	//--------------]]

	LomutoSort(list, low, i-1)
	LomutoSort(list, i+1, high)
}

/*
	霍尔快排：
	递归模板同老毛桃快排，返回低值区的锚点下标。不同的是霍尔快排以最左为基点比较元素，
	并从两端同时进行比较双向排序, 将双方都需调整位置的两个元素相互交换直到双方相交，
	然后将最左元素与右端当前锚点交换，最终实现基准点归位。
	评价——
	关键点——
 */
func HoareSort(list []int, low int, high int) {
	if low >= high {return}

	//[[----递归模板区
	
	pivot := list[low]
	right := high
	left := low
	for {
		for list[right] >= pivot && right > low{
			right --
		}
		for list[left] <= pivot && left < high{
			left ++
		}
		
		
		if left < right {
			list[left], list[right] = list[right], list[left]
		} else {
			break
		}
	}
	list[low], list[right] = list[right], list[low]
	//--------------]]
	

	HoareSort(list, low, right)

	HoareSort(list, right+1, high)
}