Hollis的个人博客
Hollis的个人博客

常见排序算法

Hollis Hollis 收录于 Algorithm 和 未分类
  约 8200 字 预计阅读 17 分钟  - 次阅读   - 条评论  

冒泡排序（Bubble Sort）：冒泡排序通过相邻元素的比较和交换，将最大的元素逐渐冒泡到最后的位置。 它从列表的第一个元素开始，依次比较相邻的元素并交换位置，直到整个列表排序完成。

冒泡排序是一种简单但效率较低的排序算法，适用于小规模数据或基本有序的数据。

选择排序（Selection Sort）：选择排序每次从未排序的部分选择最小（或最大）的元素，并将其放到已排序部分的末尾。它通过不断选择最小（或最大）元素并放置到正确位置，实现整个列表的排序。

选择排序的时间复杂度较高，适用于小规模数据。

插入排序（Insertion Sort）：插入排序通过构建有序序列，对未排序的元素逐个进行插入的方式排序。它从第二个元素开始，将其与已排序序列进行比较并插入到正确的位置，直到所有元素都被插入为止。

插入排序是一种稳定的排序算法，适用于小规模数据或部分有序的数据。

快速排序（Quick Sort）：快速排序是一种分治法的排序算法，通过选取一个基准元素，将数组分成两部分，使得左边的元素小于基准，右边的元素大于基准，然后递归地对两部分进行排序。

它是一种高效的排序算法，通常比其他排序算法更快，尤其适用于大规模数据。

归并排序（Merge Sort）：归并排序：使用分治法将一个数组分成两个子数组，分别对子数组进行排序，然后将排好序的子数组合并成一个有序数组。

它采用递归的方式进行排序，具有稳定性和较高的时间复杂度，适用于大规模数据。

堆排序（Heap Sort）：堆排序利用堆的数据结构进行排序，将数组看作是完全二叉树，并利用堆的性质构建最大堆或最小堆。排序过程中，通过反复将根节点（最大值或最小值）与最后一个叶子节点交换并调整堆，实现排序。

堆排序具有较高的时间复杂度，适用于大规模数据。

Shell排序（Shell Sort）：Shell排序是插入排序的一种变体，通过将列表分割成若干个子列表并对子列表进行插入排序，最后再对整个列表进行一次插入排序。

它利用了插入排序在部分有序列表上的高效性能，适用于中等大小的数据。

基数排序（Radix Sort）：基数排序是一种非比较的排序算法，它按照元素的每位数字进行排序，从低位到高位逐个进行排序。 它可以使用桶排序或计数排序作为基本排序算法，适用于整数或字符串等特定类型的数据。

计数排序（Counting Sort）：计数排序是一种非比较排序算法，它通过统计每个元素出现的次数，然后根据元素的值将其放到正确的位置上。首先，找出待排序数组中的最大值和最小值，然后创建一个计数数组，数组的长度为最大值与最小值之间的差值加上1。接着遍历待排序数组，统计每个元素出现的次数并放入计数数组中相应的位置。最后，根据计数数组中元素的值和位置，将待排序数组中的元素依次放入到正确的位置上，即完成排序。

计数排序的时间复杂度取决于待排序数组的范围，如果待排序数组的范围相对较小，则计数排序是一种高效的排序算法。

桶排序（Bucket Sort）：桶排序是一种排序算法，它将待排序数组分到有限数量的桶中，每个桶再分别进行排序。首先，确定桶的数量，并根据待排序数组的范围确定每个桶的范围。然后，遍历待排序数组，将每个元素放入对应的桶中。接着，对每个桶中的元素进行排序，可以使用插入排序等方法。最后，将各个桶中排序好的元素按顺序合并起来，即得到排序完成的数组。

桶排序的时间复杂度取决于桶的数量以及每个桶中的排序算法，通常情况下，桶排序是一种高效的排序算法，尤其适用于均匀分布的数据。

十大排序算法比较.png

不考虑后 3 种类排序的情况下

  • 稳定的算法有：冒泡、插入、归并。

  • Out-palce 的只有归并排序。

  • 时间复杂度 O($n^2$) 的有：冒泡、选择、插入。其余都是 O($nlogn$)。

后面 3 种都是稳定的，而且都是 Out-palce 方式。

冒泡排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

/**
* Description:  从小到大排序
    两个相邻的元素依次比较并交换，这样可以得到最大的元素；
    循环上面的过程，直到所有的元素有序
* @Author Hollis
* @Create 2024-04-01 14:17
*/

func main() {
    arr := []int{9, 2, 5, 1, 3, 7, 6, 4, 8}
    bubbleSort(arr)
    fmt.Println(arr)
}

func bubbleSort(arr []int) {
    length := len(arr)

    for i := 0; i < length-1; i++ { // i控制排序的轮数（每轮让1个元素有序）
       for j := 0; j < length-i-1; j++ { // j控制实际参与排序的元素（每轮减少1个元素）
          if arr[j] > arr[j+1] {
             arr[j], arr[j+1] = arr[j+1], arr[j]
          }
       }
    }
}

选择排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

/**
* Description:选择排序
    先找出数组中最小的元素，然后将其放在第0个位置；
    然后找出剩余元素中最小的元素，然后放在第1个位置。
技巧：
    先写内层循环，再写外层循环。
    内层循环需要找出最小的元素。我们先假设下标为0（minIndex）的元素值最小，然后遍历数组，
    依次和它比较，如果有比它更下的数，更新minIndex的值。
    这样就找出了最小的元素。
然后再在外面套一层循环，将未排序元素的起始下标后移，这样就可以完成整个数组的排序。

* @Author Hollis
* @Create 2024-04-01 14:33
*/

func main() {
    arr := []int{9, 2, 5, 1, 3, 7, 6, 4, 8}
    selectionSort(arr)
    fmt.Println(arr)
}

func selectionSort(arr []int) {
    for i := 0; i < len(arr)-1; i++ {
       minIndex := i
       for j := i + 1; j < len(arr); j++ {
          if arr[j] < arr[minIndex] {
             minIndex = j
          }
       }
       arr[i], arr[minIndex] = arr[minIndex], arr[i]
    }
}

插入排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

/**
* Description:插入排序
    想扑克牌排序一样，把后面的元素插入到前面已经有序的数组中。具体如下：
    我们需要获取当前值（currentVal）和需要插入的位置（insertIndex）。
    我们需要把当前元素的值依次（从后往前）和有序数组中的元素去比较，直到当前元素的值不小于遍历到的某个元素，
    就说明新插入的元素应该插入到该位置，同时，我们要把参与比较了的那些元素都往后移。
技巧：
    也是先写内层循环，再写外层循环，简化问题的复杂度。
    我们假设现在只有2个元素，currentVal=arr[1], insertIndex=0，由于我们需要遍历前面的元素，
    所以需要使用for循环，同时insertIndex不能小于0。
内层：
    currentVal := arr[1]
    insertIndex := 0
    for insertIndex >= 0 && currentVal < arr[insertIndex] {
       arr[insertIndex+1] = arr[insertIndex]
       insertIndex--
    }
    arr[insertIndex+1] = currentVal
    // 本来currentVal应该插入到insertIndex的位置，
    // 但最后一次比较后，让insertIndex又减了1，所以最后插入时，insertIndex应该加1。
外层：
    外层遍历所有的元素，让所有的元素都插入到有序数组中。

* @Author Hollis
* @Create 2024-04-01 15:22
*/

func main() {
    arr := []int{9, 2, 5, 1, 3, 7, 6, 4, 8}
    insertionSort(arr)
    fmt.Println(arr)
}

func insertionSort(arr []int) {
    for i := 0; i < len(arr)-1; i++ {
       currentVal := arr[i+1]
       insertIndex := i
       for insertIndex >= 0 && currentVal < arr[insertIndex] {
          arr[insertIndex+1] = arr[insertIndex]
          insertIndex--
       }
       arr[insertIndex+1] = currentVal
    }
}

快速排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

/**
* Description:快速排序
    快速排序有一种partition的思想。
    先找一个元素pivot，作为分区的基准值，将小于pivot的元素放到它的左边，大于等于它的元素放到它的右边。
    然后再在左右两边的数组中取重复上面的步骤，直到数组中元素个数小于等于1个。
具体实现：
    我们需要一个partition函数，返回pivot的下标pivotIndex。
    然后根据pivotIndex，对原数组分区治理。函数前面如下：
    quickSort(arr []int,left ,right int)
    通过修改左右指针left和right，将原任务进行分解。
quickSort函数：
    pivotIndex := partition(arr, left, right)
    quickSort(arr, left, pivotIndex-1)
    quickSort(arr, pivotIndex+1, right)
依次递归调用quickSort函数，来实现数组排序的功能。

* @Author Hollis
* @Create 2024-04-01 15:55
*/

func main() {
    arr := []int{9, 2, 5, 1, 3, 7, 6, 4, 8}
    quickSort(arr, 0, len(arr)-1)
    fmt.Println(arr)
}

func partition(arr []int, left, right int) int {
    pivot := arr[right]
    i := left - 1 // i指向左边小于pivot元素集合中的最后一个元素
    for j := left; j < right; j++ {
       if arr[j] <= pivot {
          i++
          arr[i], arr[j] = arr[j], arr[i]
       }
    }
    arr[i+1], arr[right] = arr[right], arr[i+1] // 把pivot放在“中间”的位置
    return i + 1                                // i+1就是pivot的位置下标
}

func quickSort(arr []int, left, right int) {
    if left < right {
       pivotIndex := partition(arr, left, right)
       quickSort(arr, left, pivotIndex-1)
       quickSort(arr, pivotIndex+1, right)
    }
}

归并排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

/**
* Description:归并排序
    也是一种分治的思想，将原数组分为左右两个数组，
    然后对左右两个数组递归执行mergeSort函数，直到最后数组元素个数小于等于1。
    在mergeSort函数中，调用merge函数，将左右两个数组合并。
具体如下：
    merge函数签名：mergeSort(arr, help []int, left, right int)
    在mergeSort函数中，先求得元素的中点位置下标，然后递归调用：
    mergeSort(arr, help, left, middleIndex)  // 对左边排序
    mergeSort(arr, help, middleIndex+1, right)  // 对右边排序
    merge(arr, help, middleIndex, left, right) // 合并左右的数组
* @Author Hollis
* @Create 2024-04-01 16:44
*/

func main() {
    arr := []int{9, 2, 5, 1, 3, 7, 6, 4, 8}
    help := make([]int, len(arr))
    mergeSort(arr, help, 0, len(arr)-1)
    fmt.Println(arr)
}

func mergeSort(arr, help []int, left, right int) {
    // 递归的出口：left>=right
    if left < right {
       middleIndex := left + (right-left)>>1      // 求中点下标
       mergeSort(arr, help, left, middleIndex)    // 左边排序
       mergeSort(arr, help, middleIndex+1, right) // 右边排序
       merge(arr, help, middleIndex, left, right) // 合并左右的数组
    }
}

func merge(arr, help []int, middleIndex, left, right int) {
    p1 := left
    p2 := middleIndex + 1
    i := left
    for ; p1 <= middleIndex && p2 <= right; i++ {
       if arr[p1] <= arr[p2] {
          help[i] = arr[p1]
          p1++
       } else {
          help[i] = arr[p2]
          p2++
       }
    }
    for ; p1 <= middleIndex; i++ {
       help[i] = arr[p1]
       p1++
    }
    for ; p2 <= right; i++ {
       help[i] = arr[p2]
       p2++
    }

    for j := left; j <= right; j++ {
       arr[j] = help[j]
    }
}

堆排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

/**
* Description:堆排序
    堆排序之前需要先构建大（小）根堆。
    大根堆：首先，堆是一个完全二叉树，其次，二叉树中所有子树的根节点都大于它的孩子节点，也就是堆的根节点是最大的元素。
    我们现在需要将元素从小到大排序，那么我们需要构建大根堆（a[0]为最大值），
    然后取出a[0]的值和数组中的最后一个元素交换，这样最后一个元素就是最大的了。
    然后再对0位置进行堆化，又得到a[0]为最大值，再和倒数第二个元素进行交换，依次循环下去。
构建大根堆：
    我们首先要找到最后一个非叶子节点i（下标为n/2-1），这样我们才能判断其左右子孩子和该节点元素的大小，然后进行堆化。
    现在我们要对i位置进行堆化，先假设i位置元素值最大（largest=i），比较左右两个孩子元素和i位置元素的大小关系。
    拿到i，i左孩子，i右孩子 三个中最大元素的下标，更新largest的值。
    如果i和largest不相等，交换arr[largest]和arr[i]的值，然后对largest位置再次进行堆化（递归调用）。

* @Author Hollis
* @Create 2024-04-01 20:14
*/

// 调整堆
func heapify(arr []int, n, i int) {
    largest := i
    left := 2*i + 1
    right := 2*i + 2

    // 如果左子节点大于根节点，则更新最大值索引
    if left < n && arr[left] > arr[largest] {
       largest = left
    }

    // 如果右子节点大于根节点，则更新最大值索引
    // 注意加上 right < n 的条件限制，因为堆最多n个元素
    if right < n && arr[right] > arr[largest] {
       largest = right
    }

    // 如果最大值不是根节点，则交换根节点和最大值，然后继续调整堆
    if largest != i {
       arr[i], arr[largest] = arr[largest], arr[i]
       heapify(arr, n, largest) // 对 largest 位置再次堆化
    }
}

// 堆排序
func heapSort(arr []int) {
    n := len(arr)

    // 构建最大堆
    for i := n/2 - 1; i >= 0; i-- { // 从最后一个非叶子节点（下标为n/2-1）开始，因为在heapify要比较i位置元素和它左右孩子元素的大小
       heapify(arr, n, i)
    }

    // 逐个将最大值（根节点）移到数组末尾，并调整堆
    for i := n - 1; i >= 0; i-- {
       arr[0], arr[i] = arr[i], arr[0] // 此时 arr[0]是最大的元素，将其和数组中的最后一个元素交换，然后再对0位置进行堆化
       heapify(arr, i, 0)              // 注意这里的第二个参数为i
    }
}

func main() {
    arr := []int{9, 2, 5, 1, 3, 7, 6, 4, 8}
    fmt.Println("原始数组:", arr)
    heapSort(arr)
    fmt.Println("排序后数组:", arr)
}

基数排序

思想

基数排序是一种非比较型的排序算法，其基本思想是按照每个数字的位数进行排序。它的具体步骤如下：

  1. 准备：

    • 确定待排序数组中的最大数，并计算出其位数，作为排序的轮数。
    • 准备10个桶，代表0到9这10个数字，用于存放待排序元素。

  2. 按位排序：

    • 从个位开始，对待排序数组中的每个数字，根据当前轮数的位数，将其放入对应的桶中。
    • 对于同一个桶中的元素，保持它们在原始数组中的相对顺序。

  3. 重组数组：

    • 将每个桶中的数字按照顺序依次取出，形成新的数组。

  4. 重复：

    • 重复以上步骤，直到所有位数均已考虑完毕。

  5. 输出：

    • 最终得到的数组即为排好序的数组。

基数排序的关键在于按位排序的过程，它不是基于比较来进行排序的，而是根据每个数字的位数进行分配，因此时间复杂度可以达到线性时间 O(n)。虽然基数排序在某些情况下可能不如其他排序算法，但在特定范围内的整数排序中，它是一种非常高效的排序方法。

实现

以下是使用 Go 语言实现基数排序的示例代码，并进行详细解释：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

// 获取数组中的最大值
func getMax(arr []int) int {
	max := arr[0]
	for _, value := range arr {
		if value > max {
			max = value
		}
	}
	return max
}

// 基数排序函数
func radixSort(arr []int) {
	max := getMax(arr) // 获取数组中的最大值

	// 循环每一位数字，从个位到最高位
	for exp := 1; max/exp > 0; exp *= 10 {
		count := [10]int{} // 计数数组，用于存储每个桶中的元素数量
		output := make([]int, len(arr)) // 输出数组，用于存储排序后的元素

		// 统计每个桶中元素的个数
		for _, value := range arr {
			count[(value/exp)%10]++
		}

		// 将 count 转换为每个桶最后一个元素的索引位置
		for i := 1; i < 10; i++ {
			count[i] += count[i-1]
		}

		// 根据每个元素的位数，将元素放入对应的桶中
		for i := len(arr) - 1; i >= 0; i-- {
			output[count[(arr[i]/exp)%10]-1] = arr[i]
			count[(arr[i]/exp)%10]--
		}

		// 将排序后的元素复制回原数组
		for i := 0; i < len(arr); i++ {
			arr[i] = output[i]
		}
	}
}

func main() {
	arr := []int{170, 45, 75, 90, 802, 24, 2, 66}
	fmt.Println("原始数组:", arr)

	radixSort(arr)

	fmt.Println("排序后数组:", arr)
}

解释：

  1. getMax 函数用于获取数组中的最大值，以确定需要排序的位数范围。
  2. radixSort 函数实现基数排序算法。在每次循环中，根据当前位数对数组进行分桶、计数、排序和重组，直到最高位被处理完毕。
  3. 在主函数 main 中，我们定义一个待排序的数组 arr，并打印出原始数组。
  4. 然后调用 radixSort 函数对数组进行排序。
  5. 最后，打印出排序后的数组。

基数排序的关键在于按位进行排序，通过计数排序的思想来实现每个位数的排序。在这个过程中，使用计数数组来存储每个桶中的元素数量，以及输出数组来存储排序后的元素。通过多次按位排序，最终得到了排好序的数组。

计数排序

思想

计数排序是一种非比较型的排序算法，其基本思想是通过统计待排序数组中每个元素出现的次数，进而确定每个元素在排序后的数组中的位置。具体步骤如下：

  1. 准备：

    • 确定待排序数组中的最大值和最小值。
    • 创建一个计数数组，长度为待排序数组中最大值与最小值之间的差值加1，用于存储每个元素出现的次数。

  2. 计数：

    • 遍历待排序数组，统计每个元素出现的次数，并将其存储在计数数组中对应的位置上。

  3. 累加计数：

    • 对计数数组中的元素进行累加操作，即每个元素的值等于它自身与前一个元素的累加值之和。

  4. 排序：

    • 创建一个与待排序数组大小相同的临时数组。
    • 从待排序数组的末尾开始遍历，根据计数数组中元素的值找到其在排序后数组中的位置，将其放入临时数组中。
    • 每放入一个元素，更新计数数组中对应元素的值，以保证相同元素在排序后的数组中保持相对顺序。

  5. 输出：

    • 将临时数组中的元素复制回待排序数组，完成排序。

计数排序的关键在于统计每个元素出现的次数，并根据这些统计信息确定每个元素在排序后数组中的位置。由于不涉及元素之间的比较，计数排序的时间复杂度为 O(n+k)，其中 n 是待排序数组的大小，k 是计数数组的大小。当待排序数组的范围不是很大时，计数排序是一种非常高效的排序算法。

实现

以下是使用 Go 语言实现计数排序的示例代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

// 计数排序函数
func countingSort(arr []int) {
	// 获取待排序数组中的最大值和最小值
	min, max := arr[0], arr[0]
	for _, num := range arr {
		if num < min {
			min = num
		}
		if num > max {
			max = num
		}
	}

	// 计算计数数组的长度，并初始化计数数组
	countLength := max - min + 1
	count := make([]int, countLength)

	// 统计每个元素出现的次数
	for _, num := range arr {
		count[num-min]++
	}

	// 根据计数数组中的统计信息，重建排序后的数组
	index := 0
	for i := min; i <= max; i++ {
		for count[i-min] > 0 {
			arr[index] = i
			index++
			count[i-min]--
		}
	}
}

func main() {
	arr := []int{4, 2, 2, 8, 3, 3, 1}
	fmt.Println("原始数组:", arr)

	countingSort(arr)

	fmt.Println("排序后数组:", arr)
}

解释：

  1. countingSort 函数实现了计数排序算法。
  2. 在函数中，首先找到待排序数组的最大值和最小值，以确定计数数组的长度。然后初始化计数数组，并统计每个元素出现的次数。
  3. 接下来，根据计数数组中的统计信息，重建排序后的数组。
  4. 在主函数 main 中，我们定义一个待排序的数组 arr，并打印出原始数组。
  5. 然后调用 countingSort 函数对数组进行排序。
  6. 最后，打印出排序后的数组。

计数排序的实现相对简单，关键在于统计每个元素出现的次数，并根据这些统计信息重建排序后的数组。由于不涉及元素之间的比较，计数排序的时间复杂度为 O(n+k)，其中 n 是待排序数组的大小，k 是计数数组的大小。

桶排序

思想

桶排序是一种分布式排序算法，其基本思想是将待排序元素分到有限数量的桶中，再对每个桶中的元素进行排序，最后按照顺序把各个桶中的元素依次取出，即可得到有序序列。桶排序的具体步骤如下：

  1. 准备：

    • 确定待排序数组的范围和分桶数量。
    • 创建若干个空桶，用于存放待排序数组中的元素。

  2. 分桶：

    • 遍历待排序数组，根据元素的大小将每个元素放入相应的桶中。

  3. 排序：

    • 对每个非空桶中的元素进行排序，可以使用其他排序算法（如插入排序、快速排序等）或递归地使用桶排序。

  4. 合并：

    • 将各个非空桶中的元素按顺序合并成一个新的数组。

  5. 输出：

    • 输出合并后的数组，即为有序序列。

桶排序的关键在于合理地确定分桶的数量和每个桶的范围，以及如何在分桶后对每个桶中的元素进行排序。通常情况下，如果待排序的元素分布比较均匀，可以选择较多的桶数，以减少每个桶中元素的数量，从而提高排序的效率。桶排序的时间复杂度取决于桶的数量以及在每个非空桶中进行排序的时间复杂度。

实现

以下是使用 Go 语言实现桶排序的示例代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

// 桶排序函数
func bucketSort(arr []float64) {
	if len(arr) <= 1 {
		return
	}

	// 创建若干个桶，数量为待排序数组长度
	buckets := make([][]float64, len(arr))

	// 将元素分配到桶中
	for _, num := range arr {
		index := int(num * float64(len(arr)))
		buckets[index] = append(buckets[index], num)
	}

	// 对每个非空桶中的元素进行排序
	for _, bucket := range buckets {
		if len(bucket) > 1 {
			sort.Float64s(bucket)
		}
	}

	// 合并各个桶中的元素
	index := 0
	for _, bucket := range buckets {
		for _, num := range bucket {
			arr[index] = num
			index++
		}
	}
}

func main() {
	arr := []float64{0.23, 0.67, 0.89, 0.45, 0.12, 0.56}
	fmt.Println("原始数组:", arr)

	bucketSort(arr)

	fmt.Println("排序后数组:", arr)
}

解释：

  1. bucketSort 函数实现了桶排序算法。
  2. 在函数中，首先创建了若干个桶，数量为待排序数组长度。然后将待排序数组中的元素根据一定的规则（例如取小数部分乘以数组长度）分配到相应的桶中。
  3. 接下来对每个非空桶中的元素进行排序，这里使用了 Go 语言标准库中的 sort.Float64s 函数对浮点数进行排序。
  4. 最后，将各个桶中的元素按顺序合并到原始数组中，完成排序。
  5. 在主函数 main 中，我们定义一个待排序的浮点数数组 arr，并打印出原始数组。
  6. 然后调用 bucketSort 函数对数组进行排序。
  7. 最后，打印出排序后的数组。

桶排序的核心思想是将元素分配到若干个桶中，然后对每个非空桶中的元素进行排序，最后将各个桶中的元素按顺序合并到原始数组中，完成排序。

后三种排序算法的比较

基数排序、计数排序和桶排序都是非常高效的线性时间复杂度排序算法，它们在不同的场景下各有优缺点：

  1. 基数排序（Radix Sort）：

    • 优点：
      • 对于整数类型的排序非常有效，具有稳定性。
      • 相较于其他排序算法，基数排序在数据量较大时性能较为稳定。
    • 缺点：
      • 对于大量且取值范围较大的数据，需要额外的空间开销。
      • 不适用于负数排序，需要特殊处理。
    • 适合的场景：当排序的数据量较大，且每个数据的位数不是很大时，基数排序是一个很好的选择。

  2. 计数排序（Counting Sort）：

    • 优点：
      • 在数据量不是很大、且取值范围不是很大的情况下，计数排序具有很高的效率。
      • 不是基于比较的排序算法，因此在某些情况下比基于比较的排序算法更快。
    • 缺点：
      • 需要额外的辅助数组来存储计数信息，当数据范围很大时，空间复杂度会很高。
      • 只适用于非负整数排序。
    • 适合的场景：当排序的数据都是非负整数，且数据量不是很大时，计数排序是一个非常快速的排序算法。

  3. 桶排序（Bucket Sort）：

    • 优点：
      • 对于均匀分布的数据，桶排序表现良好，具有较高的效率。
      • 可以有效地处理小范围内的数据排序。
    • 缺点：
      • 需要事先知道数据的分布情况，如果数据分布不均匀，可能导致桶间数据分布不均匀，进而影响排序效率。
      • 需要额外的空间来存储桶，当数据量很大时，空间复杂度会增加。
    • 适合的场景：当待排序数据的范围较小，且数据分布比较均匀时，桶排序是一个很好的选择。

总的来说，基数排序、计数排序和桶排序都是在特定场景下非常高效的排序算法，选择合适的算法取决于待排序数据的特点以及所需的时间与空间复杂度。

收录于 合集・未分类 7
更新于 2025-04-08 
CC BY-NC-SA 4.0
LeetcodeAlgorithm
返回 | 主页
0%