Golang实现算法快速排序和归并排序的比较

Golang实现快速排序和归并排序，比较两者性能。

Golang实现算法快速排序和归并排序的比较

快速排序(Quick Sort)是一种高效的排序算法，其基本思想是通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

归并排序(Merge Sort)是一种分治法(Divide and Conquer)的排序算法，它的基本思想是将待排序的数据分为两个子序列，对子序列分别进行排序，然后将已排序的子序列合并成一个有序序列，归并排序的时间复杂度为O(nlogn),是一种非常高效的排序算法。

本文将介绍Golang中如何实现快速排序和归并排序，并对这两种算法进行比较。

快速排序实现

1、定义一个快速排序的函数quickSort,接收一个整数切片arr和两个整数left和right作为参数，表示需要排序的范围。

func quickSort(arr []int, left, right int) {
}

2、在quickSort函数中，首先判断left是否小于right,如果满足条件，则执行以下操作：

选取基准值pivot,这里我们选择数组的第一个元素作为基准值。

通过遍历数组，将小于基准值的元素放到左边，大于基准值的元素放到右边。

对左右两边的子数组分别递归调用quickSort函数。

if left < right {
    p := partition(arr, left, right)
    quickSort(arr, left, p-1)
    quickSort(arr, p+1, right)
}

3、实现partition函数，用于将数组划分为两部分，该函数接收一个整数切片arr和两个整数left和right作为参数，返回一个整数p,表示划分的位置。

func partition(arr []int, left, right int) int {
    pivot := arr[left] // 基准值为第一个元素
    i := left + 1 // i指向小于基准值的元素的第一个位置
    j := right // j指向大于基准值的元素的最后一个位置
    for k := left; k <= j; k++ {
        if arr[k] < pivot {
            arr[i], arr[k] = arr[k], arr[i] // 将小于基准值的元素放到左边
            i++ // i指针后移一位
        } else if arr[k] > pivot {
            arr[j], arr[k] = arr[k], arr[j] // 将大于基准值的元素放到右边
            j-// j指针前移一位
        }
    }
    arr[i], arr[right] = arr[right], arr[i] // 将基准值放到正确的位置
    return i // 返回划分的位置
}

归并排序实现

1、实现一个归并排序的函数mergeSort,接收一个整数切片arr作为参数，在函数内部，首先判断数组长度是否小于等于1,如果是，则直接返回，否则，将数组分成两半，分别对左右两半进行递归调用mergeSort函数，将两个已排序的子数组合并成一个有序数组。

func mergeSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    mid := len(arr) / 2 // 计算中间位置
    left := mergeSort(arr[:mid]) // 对左半部分进行递归排序
    right := mergeSort(arr[mid:]) // 对右半部分进行递归排序
    return merge(left, right) // 将两个已排序的子数组合并成一个有序数组
}

2、实现merge函数，用于将两个已排序的子数组合并成一个有序数组，该函数接收两个整数切片left和right作为参数，返回一个整数切片，在函数内部，使用双指针法遍历两个子数组，将较小的元素放到结果数组中，直到遍历完两个子数组。

func merge(left, right []int) []int {
    res := make([]int, len(left)+len(right)) // 创建一个足够大的结果数组
    i := 0 // i指向结果数组的第一个位置
    j := 0 // j指向第二个子数组的第一个位置
    k := 0 // k指向结果数组的第一个位置加1(即原数组的第一个位置)
    for i < len(left) && j < len(right) { // 当两个子数组都没有遍历完时，继续循环
        if left[i] < right[j] { // 如果左半部分的元素小于右半部分的元素，将其放入结果数组中
            res[k] = left[i]
            i++ // i指针后移一位
        } else if left[i] > right[j] { // 如果左半部分的元素大于右半部分的元素，将其放入结果数组中
            res[k] = right[j]
            j++ // j指针后移一位
        } else { // 如果左半部分的元素等于右半部分的元素，跳过这两个元素，继续比较下一个元素
            i++ // i指针后移一位
            j++ // j指针后移一位
        }
        k++ // k指针后移一位(即原数组的第一个位置加1)
    }
    for i < len(left) { // 当左半部分还有剩余元素时，将其放入结果数组中
        res[k] = left[i]
        i++ // i指针后移一位
        k++ // k指针后移一位(即原数组的第一个位置加1)
    }
    for j < len(right) { // 当右半部分还有剩余元素时，将其放入结果数组中(此时左半部分已经全部放入结果数组)
        res[k] = right[j]
        j++ // j指针后移一位
        k++ // k指针后移一位(即原数组的第一个位置加1)
    }
    return res // 返回合并后的有序数组
}