golang快速排序算法

快速排序算法实现及优化

快速排序是一种常用而有效的排序算法，在大数据量下表现出色。它的基本思想是选取一个基准元素，通过不断比较和交换，将序列分割成两个子序列，然后分别对子序列进行递归排序。

1. 实现快速排序

首先，定义一个函数来实现快速排序：

func QuickSort(arr []int) {
    if len(arr) <= 1 {
        return
    }
    pivot := arr[0]
    left, right := 0, len(arr)-1
    for i := 1; i <= right; {
        if arr[i] < pivot {
            arr[left], arr[i] = arr[i], arr[left]
            left++
            i++
        } else {
            arr[right], arr[i] = arr[i], arr[right]
            right--
        }
    }
    QuickSort(arr[:left])
    QuickSort(arr[left+1:])
}

2. 示例

arr := []int{5, 4, 6, 3, 7, 2, 8, 1}
QuickSort(arr)
fmt.Println(arr) // 输出 [1, 2, 3, 4, 5, 6, 7, 8]

3. 算法分析

快速排序的时间复杂度为O(nlogn)，最坏情况下为O(n^2)。快速排序是一种原地排序算法，不需要额外的存储空间。由于使用递归，快速排序的空间复杂度为O(logn)。

4. 优化

虽然快速排序在大多数情况下表现良好，但在某些特殊情况下可能退化成O(n^2)的时间复杂度。为了提高性能，可以采用以下优化措施：

• 随机选择基准元素：在选择基准元素时，可以随机选取一个元素，而不总是选取第一个或最后一个元素。这样可以避免某些特定输入情况下退化。
• 三数取中法：在选择基准元素时，可以从待排序序列的头、尾和中间分别取一个元素，取其中值作为基准元素，以减少选取极端元素的概率。
• 插入排序优化：当序列的长度比较小（如10）时，可以改用插入排序来提高效率。
• 优化递归：当进行递归排序时，可以通过限制递归深度或使用尾递归等方式来减少递归次数。

5. 示例代码（优化后）

const insertSortThreshold = 10

func QuickSort(arr []int) {
    quickSortOptimized(arr, 0, len(arr)-1)
}

func quickSortOptimized(arr []int, left, right int) {
    if right-left <= insertSortThreshold {
        insertSort(arr, left, right)
        return
    }
    pivot := medianOfThree(arr, left, right)
    i, j := left+1, right-1
    for {
        for arr[i] < pivot {
            i++
        }
        for arr[j] > pivot {
            j--
        }
        if i >= j {
            break
        }
        arr[i], arr[j] = arr[j], arr[i]
        i++
        j--
    }
    arr[left+1], arr[j] = arr[j], arr[left+1]
    arr[left], arr[j-1] = arr[j-1], arr[left]
    quickSortOptimized(arr, left, j-1)
    quickSortOptimized(arr, j+1, right)
}

func insertSort(arr []int, left, right int) {
    for i := left + 1; i <= right; i++ {
        temp := arr[i]
        j := i
        for ; j > left && arr[j-1] > temp; j-- {
            arr[j] = arr[j-1]
        }
        arr[j] = temp
    }
}

func medianOfThree(arr []int, left, right int) int {
    mid := (left + right) / 2
    if arr[left] > arr[mid] {
        arr[left], arr[mid] = arr[mid], arr[left]
    }
    if arr[left] > arr[right] {
        arr[left], arr[right] = arr[right], arr[left]
    }
    if arr[mid] > arr[right] {
        arr[mid], arr[right] = arr[right], arr[mid]
    }
    arr[left], arr[right-1] = arr[right-1], arr[left]
    return arr[right-1]
}

6. 结论

快速排序是一种高效的排序算法，在大多数情况下表现优于其他常见排序算法。通过合适的优化措施，可以进一步提高其性能。

要记住的一点是，虽然快速排序适用于大数据集和一般情况，但对于小规模数组，插入排序可能更好，因为它具有较低的常量因子。