快速排序

快速排序

思想

• 1．先从数列中取出一个数作为基准数。
• 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
• 3．再对左右区间重复第二步，直到各区间只有一个数。
  经典快速排序是用最后一个数作为基数，平时用的是随机快速排序，使用随机数减少排序的次数

思路 step1普通的快排，取数列中的最后一个数据做为基数，然后进行分区操作,将比他小的放在左边，比其大的等于的放在右边

// 以最后的那个进行划分
func partition1(array []int, left, right int) int {
    p := array[right]
    less := left - 1
    for i := 0; i <= right; i++ {
        if array[i] <= p {
            less++
            Swap(array, less, i)
        }
    }
    return less
}
// [54 73 90 44 88 65 59 18 10 67 41 56 64 83 97 65 80 94 58 87] 以 87 为分界线，进行左右两边分区 
// [54 73 44 65 59 18 10 67 41 56 64 83 65 80 58 87 90 94 97 88]
// 15 最后的分割位置 15

思路 step2荷兰国旗问题，将数列中的小于基准放在左边，等于基准的放在中间，大于基准的放在右边

// 荷兰国旗问题 划分过程 大于A 放右边，小于放在左边，中间的放在中间
func partition(array []int, left, right int) (l, r int) {
    less := left - 1
    more := right
    for left < more {
        if array[left] < array[right] {
            less++
            Swap(array, less, left)
            left++
        } else if array[left] > array[right] {
            more--
            Swap(array, more, left)
        } else {
            left++
        }
    }
    Swap(array, more, right)
    return less + 1, more
}

思路 step3 再对左右区间重复第二步，直到各区间只有一个数

// 真正的快排
func QuickSort(array []int, left, right int) {
   r := rand.New(rand.NewSource(time.Now().UnixNano()))
   if left < right {
      Swap(array, left+r.Intn(right-left), right)
      l, r := partition(array, left, right)
      QuickSort(array, left, l-1)
      QuickSort(array, r+1, right)
   }
}

所以最后的快速排序是

func QuickSort(array []int, left, right int) {
   r := rand.New(rand.NewSource(time.Now().UnixNano()))
   if left < right {
      Swap(array, left+r.Intn(right-left), right)
      l, r := partition2(array, left, right)
      QuickSort(array, left, l-1)
      QuickSort(array, r+1, right)
   }
}
func partition(array []int, left, right int) (l, r int) {
    less := left - 1
    more := right
    for left < more {
        if array[left] < array[right] {
            less++
            Swap(array, less, left)
            left++
        } else if array[left] > array[right] {
            more--
            Swap(array, more, left)
        } else {
            left++
        }
    }
    Swap(array, more, right)
    return less + 1, more
}
func Swap(arr []int, i, j int) { // 因为数组是地址传参 所以不用地址
    if i != j {
        arr[i] = arr[i] ^ arr[j]
        arr[j] = arr[i] ^ arr[j]
        arr[i] = arr[i] ^ arr[j]
    }

}