Golang实现算法:快速排序和归并排序的比较 在计算机科学中,排序是一种基本的算法问题。排序算法主要有两类:比较排序和非比较排序。比较排序是通过比较元素的大小来排序的,而非比较排序则不是,常见的非比较排序有计数排序、桶排序和基数排序。而比较排序中,快速排序和归并排序是两种比较常见的排序算法。本文将比较这两种算法的性能和实现。 一、快速排序 快速排序是典型的分治思想的体现,它的基本思想是:通过一次排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按照此方法对两部分数据分别进行快速排序,整个过程递归进行,以此达到整个序列变成有序序列。 1. 算法步骤 快速排序的算法步骤如下: - 挑选基准值:从数列中挑出一个元素作为基准值,称为枢轴(pivot); - 分割:重新排列序列,使得比枢轴小的元素在左边,比枢轴大的元素在右边。在这个分割结束之后,对于每个元素,它左边的元素都比它小,右边的元素都比它大; - 递归排序子序列:通过递归排序左右两个子序列,排序完成。 2. 代码实现 Golang实现快速排序的代码如下: ```go func QuickSort(arr []int, left, right int) { if left >= right { return } pivot := partition(arr, left, right) QuickSort(arr, left, pivot-1) QuickSort(arr, pivot+1, right) } func partition(arr []int, left, right int) int { pivot := arr[left] for left < right { for left < right && arr[right] >= pivot { right-- } arr[left] = arr[right] for left < right && arr[left] <= pivot { left++ } arr[right] = arr[left] } arr[left] = pivot return left } ``` 在实现上采用了递归的思想,每次选择最左边的数作为基准值,遍历数组,将比基准值小的数放到左边,比基准值大的数放到右边,并返回基准值(枢轴)在数组中的位置,以便于对左右两个子数组进行递归排序。 如果使用golang内置sort包对数组进行排序,快排的代码如下: ```go func QuickSort(data Interface) { n := data.Len() quickSort(data, 0, n, maxDepth(n)) } func quickSort(data Interface, a, b, maxDepth int) { for b-a > 12 { if maxDepth == 0 { heapSort(data, a, b) return } maxDepth-- i, j := a+1, b-1 if data.Less(j, i) { data.Swap(i, j) } if data.Less(j, i+1) { data.Swap(i+1, j) } if data.Less(i, i+1) { data.Swap(i, i+1) } p := i for { for ; data.Less(i, p); i++ { } for ; j > p && !data.Less(p, j); j-- { } if i >= j { break } data.Swap(i, j) } data.Swap(p, j) if j-p > b-j { quickSort(data, a, j, maxDepth) a = j + 1 } else { quickSort(data, j+1, b, maxDepth) b = j } } if b-a > 1 { for i := a + 1; i < b; i++ { for j := i; j > a && data.Less(j, j-1); j-- { data.Swap(j, j-1) } } } } ``` 在Golang内置的sort包中,快排算法的效率极高,它通过减少递归的深度,以及处理小数组的方式来提高效率。 二、归并排序 归并排序也是一种分治的排序算法,它的基本思想是:将待排序序列分成若干个子序列,每个子序列都是有序的,然后合并子序列,使整个序列的数都有序。 1. 算法步骤 归并排序的算法步骤如下: - 拆分:将要排序的序列拆分成两个子序列,拆分到序列只有一个元素时停止拆分; - 排序:将每个子序列排序; - 合并:将已经排好序的子序列合并成一个新的序列。 2. 代码实现 Golang实现归并排序的代码如下: ```go 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) } func merge(left, right []int) []int { result := []int{} for len(left) > 0 && len(right) > 0 { if left[0] <= right[0] { result = append(result, left[0]) left = left[1:] } else { result = append(result, right[0]) right = right[1:] } } if len(left) > 0 { result = append(result, left...) } if len(right) > 0 { result = append(result, right...) } return result } ``` 在实现上采用了递归的思想,将数组拆分成左右两个子数组,然后对每个子数组进行递归排序。最后将已经排好序的左右两个子数组进行合并。 如果使用golang内置sort包对数组进行排序,归并排序的代码如下: ```go func MergeSort(data Interface) { n := data.Len() if n < 2 { return } a := make(slice, n/2) b := make(slice, n-n/2) copy(a, data) copy(b, data[n/2:]) MergeSort(a) MergeSort(b) if a[n/2-1].Less(b[0]) { copy(data, a) copy(data[n/2:], b) return } for i, j, k := 0, 0, 0; k < n; k++ { if j >= len(b) || (i < len(a) && !a[i].Less(b[j])) { data[k] = a[i] i++ } else { data[k] = b[j] j++ } } } ``` 在Golang内置的sort包中,归并排序的算法效率相对比较低,但它具有稳定性,可以保证相同元素的顺序不变。这也是它被广泛使用的原因之一。 三、算法比较 快速排序和归并排序都是分治思想的体现,它们的时间复杂度都为O(nlogn)。但是在最坏的情况下,快速排序的时间复杂度会退化到O(n^2),而归并排序的时间复杂度则稳定在O(nlogn)。 另外,归并排序需要额外的空间存储子数组,而快速排序不需要额外的空间,它是原地排序的,所以在空间复杂度方面,快速排序优于归并排序。但是这也使得快速排序不稳定,它不能保证相同元素的顺序不变。 四、结论 在实际的应用中,快速排序和归并排序各有优缺点,具体使用哪种算法需要根据实际情况进行选择。如果需要对大量数据进行排序,且空间比较紧张,可以使用快速排序。如果要求排序稳定,可以使用归并排序。如果既需要排序稳定,又不希望额外浪费太多空间,可以考虑使用其他算法,比如堆排序。