冒泡排序
- 实现思想
冒泡排序（Bubble Sort）是一种简单的排序算法，它重复地遍历要排序的元素，比较相邻两个元素的大小，并在需要时交换它们的位置，直到整个序列有序为止。
- Golang实现
package main
import "fmt"
func bubbleSort(arr []int) {
n := len(arr)
for i := 0; i < n-1; i++ {
for j := 0; j < n-i-1; j++ {
if arr[j] > arr[j+1] {
// 交换arr[j]和arr[j+1]的位置
arr[j], arr[j+1] = arr[j+1], arr[j]
}
}
}
}
func main() {
arr := []int{64, 34, 25, 12, 22, 11, 90}
fmt.Println("原始数组:", arr)
bubbleSort(arr)
fmt.Println("排序后的数组:", arr)
}- 实现原理与过程
遍历数组，比较相邻的元素，如果左边的元素大于右边的元素，就交换它们的位置，将较大的元素冒泡到右边。
重复这个过程，每次都会将当前未排序部分中最大的元素冒泡到最右边。
继续进行上述步骤，每次减少未排序部分的长度，直到整个数组都排序完成。
- 时间复杂度
冒泡排序的最坏时间复杂度为O(n^2)，因为在最坏情况下，需要进行n(n-1)/2次比较和交换操作。
冒泡排序的平均时间复杂度也为O(n^2)。
最好情况下，如果输入数组已经有序，冒泡排序的时间复杂度为O(n)，但这种情况很少发生。
- 空间复杂度
冒泡排序的空间复杂度为O(1)，因为它只需要一个额外的变量来进行元素交换，不需要额外的数据结构存储数据。
- 使用场景
教育和学习：冒泡排序是一种非常基础的排序算法，适用于教育和学习排序算法的基本原理。它可以帮助初学者理解排序算法的基本思想和工作方式。
小规模数据集：当处理的数据集较小，而且性能要求不高时，冒泡排序是一个简单有效的选择。由于它的实现简单，可以在小规模数据集上进行快速排序。
数据基本有序：当数据已经接近有序状态时，冒泡排序可能会比较高效。在这种情况下，冒泡排序的交换操作较少，可以提供较好的性能。
- 局限性
低效性能：冒泡排序的平均和最坏情况时间复杂度都是O(n^2)，其中n是数据集的大小。这使得它在处理大规模数据集时性能不佳，因为它的比较和交换操作次数较多。
不稳定性：冒泡排序是一种不稳定的排序算法，即相等元素的相对顺序在排序后可能发生改变。
不适合大规模数据：由于其性能问题，冒泡排序不适合用于大规模数据排序，更高效的排序算法如快速排序、归并排序、堆排序等通常更适合这些情况。
交换操作频繁：冒泡排序的主要操作是不断地交换相邻元素，这种操作在数据规模较大时会显著影响性能。
选择排序
- 实现思想
选择排序（Selection Sort）是一种简单的排序算法，它每次在未排序的部分中选择最小（或最大）的元素，然后将其与未排序部分的第一个元素交换位置。
- Golang实现
package main
import "fmt"
func selectionSort(arr []int) {
n := len(arr)
for i := 0; i < n-1; i++ {
minIndex := i
for j := i + 1; j < n; j++ {
if arr[j] < arr[minIndex] {
minIndex = j
}
}
// 交换arr[i]和arr[minIndex]的位置
arr[i], arr[minIndex] = arr[minIndex], arr[i]
}
}
func main() {
arr := []int{64, 34, 25, 12, 22, 11, 90}
fmt.Println("原始数组:", arr)
selectionSort(arr)
fmt.Println("排序后的数组:", arr)
}- PHP实现
<?php
function selectionSort(&$arr) {
$n = count($arr);
for ($i = 0; $i < $n - 1; $i++) {
$minIndex = $i;
for ($j = $i + 1; $j < $n; $j++) {
if ($arr[$j] < $arr[$minIndex]) {
$minIndex = $j;
}
}
// 交换$arr[$i]和$arr[$minIndex]的值
$temp = $arr[$i];
$arr[$i] = $arr[$minIndex];
$arr[$minIndex] = $temp;
}
}
$arr = [64, 34, 25, 12, 22, 11, 90];
echo "原始数组: ";
print_r($arr);
selectionSort($arr);
echo "排序后的数组: ";
print_r($arr);
?>- 实现原理与过程
遍历数组，从未排序部分中找到最小元素的索引（或最大元素的索引）。
将找到的最小元素与未排序部分的第一个元素交换位置，将最小元素放到已排序部分的末尾。
继续以上步骤，每次遍历会确定一个最小元素的位置，直到整个数组排序完成。
- 时间复杂度
选择排序的最坏时间复杂度为O(n^2)，因为在最坏情况下，需要进行n(n-1)/2次比较和n-1次交换操作。
选择排序的平均时间复杂度也为O(n^2)。
无论输入数据的分布情况如何，选择排序的时间复杂度都是O(n^2)。
- 空间复杂度
选择排序的空间复杂度为O(1)，因为它只需要一个额外的变量来进行元素交换，不需要额外的数据结构存储数据。
- 使用场景
小规模数据集： 当处理的数据集较小，性能要求不高时，选择排序是一个可行的选择。由于其实现简单，它可以在小规模数据集上进行快速排序。
稳定性不重要： 选择排序是一种不稳定的排序算法，即相等元素的相对顺序在排序后可能发生改变。在某些情况下，稳定性不是一个关键因素，选择排序可以用作一种排序方式。
最小交换操作： 与其他排序算法（如冒泡排序）相比，选择排序的主要操作是交换最小元素与未排序部分的第一个元素，而不是频繁地交换相邻元素。这可能在某些情况下对于减少数据移动操作很有用。
尽管选择排序有上述优点，但它的性能不如其他高级排序算法，特别是在大规模数据集上。因此，对于大型数据集和需要高性能的应用，通常会选择更高效的排序算法，例如快速排序、归并排序、堆排序等。选择排序主要用于教育和学习，或者在特定情况下处理较小的数据集。
插入排序
- 实现思想
插入排序（Insertion Sort）是一种简单的排序算法，它将数组分为已排序和未排序两个部分，然后逐步将未排序部分的元素插入到已排序部分，直到整个数组有序。
- Golang实现
package main
import "fmt"
func insertionSort(arr []int) {
n := len(arr)
for i := 1; i < n; i++ {
key := arr[i]
j := i - 1
// 将大于key的元素向右移动
for j >= 0 && arr[j] > key {
arr[j+1] = arr[j]
j--
}
arr[j+1] = key
}
}
func main() {
arr := []int{64, 34, 25, 12, 22, 11, 90}
fmt.Println("原始数组:", arr)
insertionSort(arr)
fmt.Println("排序后的数组:", arr)
}- Java实现
public class InsertionSort {
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// 将大于key的元素向右移动
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
System.out.print("原始数组: ");
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
insertionSort(arr);
System.out.print("排序后的数组: ");
for (int num : arr) {
System.out.print(num + " ");
}
}
}- PHP实现
<?php
function insertionSort(&$arr) {
$n = count($arr);
for ($i = 1; $i < $n; $i++) {
$key = $arr[$i];
$j = $i - 1;
// 将大于$key的元素向右移动
while ($j >= 0 && $arr[$j] > $key) {
$arr[$j + 1] = $arr[$j];
$j--;
}
$arr[$j + 1] = $key;
}
}
$arr = [64, 34, 25, 12, 22, 11, 90];
echo "原始数组: ";
print_r($arr);
insertionSort($arr);
echo "排序后的数组: ";
print_r($arr);
?>- 实现原理与过程
将数组分为已排序部分（起始为空）和未排序部分。
从未排序部分选择第一个元素作为“key”。
将“key”与已排序部分中的元素逐个比较，将大于“key”的元素向右移动，为“key”腾出插入位置。
将“key”插入到合适的位置，使得已排序部分仍然有序。
重复以上步骤，直到未排序部分为空，整个数组有序。
- 时间复杂度
插入排序的最坏时间复杂度为O(n^2)，在最坏情况下，需要进行n(n-1)/2次比较和n(n-1)/2次移动操作。
插入排序的平均时间复杂度也为O(n^2)。
最好情况下，如果输入数组已经有序，插入排序的时间复杂度为O(n)，因为只需要进行n-1次比较，无需移动元素。
- 空间复杂度
插入排序的空间复杂度为O(1)，因为它只需要一个额外的变量来存储“key”，不需要额外的数据结构存储数据。
- 使用场景
小规模数据集： 插入排序在处理小规模数据集时性能良好，因为它的时间复杂度是O(n^2)，其中n是数据集的大小。对于少量数据的排序任务，插入排序通常比其他高级排序算法更快。
部分有序数据： 当输入数据部分有序时，插入排序通常表现出色。由于插入排序是在已排序部分中找到适当位置来插入元素，因此它的比较和交换操作次数相对较少。
在线排序： 插入排序是一种稳定的排序算法，它可以在不需要额外空间的情况下进行排序。这使得它适用于在线排序，即对流式数据进行排序而不必存储整个数据集。
简单性和可读性： 插入排序的实现非常简单，易于理解和调试。它是一种直观的排序算法，因此在某些情况下，它可能是首选的排序方式，尤其是在需要快速排序少量数据时。
稳定性： 插入排序是一种稳定的排序算法，即相等元素的相对顺序在排序后保持不变。这对某些应用非常重要，如排序带有优先级的任务。
希尔排序
- 实现原理
希尔排序（Shell Sort）是插入排序的一种改进版本，它通过将原始数组分为多个子序列来排序，最终合并这些子序列以获得最终有序的数组。希尔排序的核心思想是通过较大的步长进行初步排序，然后逐渐减小步长进行更细致的排序
- Golang实现
package main
import "fmt"
func shellSort(arr []int) {
n := len(arr)
gap := n / 2 // 初始步长
for gap > 0 {
for i := gap; i < n; i++ {
temp := arr[i]
j := i
// 插入排序
for j >= gap && arr[j-gap] > temp {
arr[j] = arr[j-gap]
j -= gap
}
arr[j] = temp
}
gap /= 2 // 缩小步长
}
}
func main() {
arr := []int{64, 34, 25, 12, 22, 11, 90}
fmt.Println("原始数组:", arr)
shellSort(arr)
fmt.Println("排序后的数组:", arr)
}- Java实现
public class ShellSort {
public static void shellSort(int[] arr) {
int n = arr.length;
// 初始步长为数组长度的一半
int gap = n / 2;
while (gap > 0) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j = i;
// 插入排序
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
gap /= 2; // 缩小步长
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
System.out.print("原始数组: ");
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
shellSort(arr);
System.out.print("排序后的数组: ");
for (int num : arr) {
System.out.print(num + " ");
}
}
}- 实现原理和过程
希尔排序将原始数组分为若干个子序列，每个子序列有相同的步长（gap）。
对每个子序列进行插入排序，即将较大的元素移动到子序列的末尾。
逐渐缩小步长，重复以上过程，直到步长为1，此时对整个数组进行插入排序，完成排序过程。
- 时间复杂度
希尔排序的时间复杂度不容易精确确定，因为它的性能取决于步长序列的选择。
最坏情况下的时间复杂度通常为O(n^2)。但对于某些特定的步长序列，希尔排序的性能可以达到O(n log^2 n)。
在实践中，希尔排序的性能通常比简单的插入排序要好。
- 空间复杂度
希尔排序的空间复杂度为O(1)，因为它只需要一个额外的变量来进行元素交换，不需要额外的数据结构存储数据。
归并排序
- 实现思想
归并排序（Merge Sort）是一种分治算法，它将原始数组分成较小的子数组，然后递归地排序这些子数组，并将它们合并以获得最终有序数组。
- Golang实现
package main
import "fmt"
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 := make([]int, 0)
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:]
}
}
result = append(result, left...)
result = append(result, right...)
return result
}
func main() {
arr := []int{64, 34, 25, 12, 22, 11, 90}
fmt.Println("原始数组:", arr)
sortedArr := mergeSort(arr)
fmt.Println("排序后的数组:", sortedArr)
}- PHP实现
<?php
function mergeSort($arr) {
if (count($arr) <= 1) {
return $arr;
}
$mid = floor(count($arr) / 2);
$left = array_slice($arr, 0, $mid);
$right = array_slice($arr, $mid);
$left = mergeSort($left);
$right = mergeSort($right);
return merge($left, $right);
}
function merge($left, $right) {
$result = [];
$leftIndex = 0;
$rightIndex = 0;
while ($leftIndex < count($left) && $rightIndex < count($right)) {
if ($left[$leftIndex] < $right[$rightIndex]) {
$result[] = $left[$leftIndex];
$leftIndex++;
} else {
$result[] = $right[$rightIndex];
$rightIndex++;
}
}
while ($leftIndex < count($left)) {
$result[] = $left[$leftIndex];
$leftIndex++;
}
while ($rightIndex < count($right)) {
$result[] = $right[$rightIndex];
$rightIndex++;
}
return $result;
}
$arr = [64, 34, 25, 12, 22, 11, 90];
echo "原始数组: ";
print_r($arr);
$sortedArr = mergeSort($arr);
echo "排序后的数组: ";
print_r($sortedArr);
?>- Javascript实现
function mergeSort(arr) {
if (arr.length <= 1) {
return arr;
}
const mid = Math.floor(arr.length / 2);
const left = arr.slice(0, mid);
const right = arr.slice(mid);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
let result = [];
let leftIndex = 0;
let rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
result.push(left[leftIndex]);
leftIndex++;
} else {
result.push(right[rightIndex]);
rightIndex++;
}
}
return result.concat(left.slice(leftIndex), right.slice(rightIndex));
}
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log("原始数组:", arr);
const sortedArr = mergeSort(arr);
console.log("排序后的数组:", sortedArr);- 实现原理和过程
归并排序首先将原始数组递归地分成两个子数组，直到每个子数组的长度为1或0。
然后，将这些子数组两两合并，每次合并都保持有序。
合并过程中，比较两个子数组的元素，将较小的元素放入结果数组，并将该子数组中的指针向后移动。
最终合并得到一个有序的数组。
- 时间复杂度
归并排序的时间复杂度始终是O(nlogn)，无论输入数据的分布如何。这使得它成为一种稳定且高效的排序算法。
- 空间复杂度
归并排序的空间复杂度取决于递归调用和合并操作所使用的额外空间。通常情况下，它的空间复杂度为O(n)。如果实现时优化，可以将空间复杂度降低到O(1)。
快速排序
- 实现思想
快速排序（Quick Sort）是一种高效的、基于分治法的排序算法。它的核心思想是选择一个基准元素，将数组分成两个子数组，其中一个子数组的元素都小于基准元素，另一个子数组的元素都大于基准元素。然后，递归地对这两个子数组进行排序，直到整个数组有序。
- Golang实现
package main
import "fmt"
func quickSort(arr []int) {
if len(arr) <= 1 {
return
}
pivotIndex := partition(arr)
quickSort(arr[:pivotIndex])
quickSort(arr[pivotIndex+1:])
}
func partition(arr []int) int {
pivot := arr[0]
left := 1
right := len(arr) - 1
for left <= right {
for left <= right && arr[left] <= pivot {
left++
}
for left <= right && arr[right] >= pivot {
right--
}
if left <= right {
arr[left], arr[right] = arr[right], arr[left]
}
}
arr[0], arr[right] = arr[right], arr[0]
return right
}
func main() {
arr := []int{64, 34, 25, 12, 22, 11, 90}
fmt.Println("原始数组:", arr)
quickSort(arr)
fmt.Println("排序后的数组:", arr)
}
- PHP实现
<?php
function quickSort(&$arr) {
$length = count($arr);
if ($length <= 1) {
return;
}
$left = [];
$right = [];
$pivot = $arr[0];
for ($i = 1; $i < $length; $i++) {
if ($arr[$i] < $pivot) {
$left[] = $arr[$i];
} else {
$right[] = $arr[$i];
}
}
quickSort($left);
quickSort($right);
$arr = array_merge($left, [$pivot], $right);
}
$arr = [64, 34, 25, 12, 22, 11, 90];
echo "原始数组: ";
print_r($arr);
quickSort($arr);
echo "排序后的数组: ";
print_r($arr);
?>- 实现原理和过程
选择一个基准元素（通常是数组的第一个元素）。
使用两个指针，一个从左向右移动，一个从右向左移动，分别找到第一个大于基准元素和第一个小于基准元素的元素。
交换这两个元素的位置，将小于基准的元素放在左边，大于基准的元素放在右边。
重复步骤2和3，直到两个指针相遇。
将基准元素与相遇位置的元素交换，使得基准元素处于正确的位置。
递归地对基准元素左右两侧的子数组进行快速排序。
- 时间复杂度
平均情况下，快速排序的时间复杂度为O(nlogn)。
最坏情况下，时间复杂度为O(n^2)，但可以通过选择合适的基准元素和随机化来避免最坏情况的发生。
- 空间复杂度
快速排序的空间复杂度为O(logn)，因为递归调用的最大深度是log n，每层需要的额外空间是常数级的。
堆排序
堆排序（Heap Sort）是一种基于二叉堆数据结构的排序算法，它通过将待排序的元素构建成一个二叉堆（最大堆或最小堆），然后逐步将堆顶元素与堆中的最后一个元素交换，再对剩余的元素进行堆调整，重复这个过程直到整个数组有序。
- Golang实现
package main
import "fmt"
func heapSort(arr []int) {
n := len(arr)
// 构建最大堆
for i := n/2 - 1; i >= 0; i-- {
heapify(arr, n, i)
}
// 逐步将堆顶元素与堆中的最后一个元素交换，并调整堆
for i := n - 1; i > 0; i-- {
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
}
}
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
}
if right < n && arr[right] > arr[largest] {
largest = right
}
if largest != i {
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
}
}
func main() {
arr := []int{64, 34, 25, 12, 22, 11, 90}
fmt.Println("原始数组:", arr)
heapSort(arr)
fmt.Println("排序后的数组:", arr)
}
- PHP实现
<?php
function heapSort(&$arr) {
$n = count($arr);
// 构建最大堆
for ($i = floor($n / 2) - 1; $i >= 0; $i--) {
heapify($arr, $n, $i);
}
// 逐步将堆顶元素与堆中的最后一个元素交换，并调整堆
for ($i = $n - 1; $i > 0; $i--) {
$temp = $arr[0];
$arr[0] = $arr[$i];
$arr[$i] = $temp;
heapify($arr, $i, 0);
}
}
function heapify(&$arr, $n, $i) {
$largest = $i;
$left = 2 * $i + 1;
$right = 2 * $i + 2;
if ($left < $n && $arr[$left] > $arr[$largest]) {
$largest = $left;
}
if ($right < $n && $arr[$right] > $arr[$largest]) {
$largest = $right;
}
if ($largest != $i) {
$temp = $arr[$i];
$arr[$i] = $arr[$largest];
$arr[$largest] = $temp;
heapify($arr, $n, $largest);
}
}
$arr = [64, 34, 25, 12, 22, 11, 90];
echo "原始数组: ";
print_r($arr);
heapSort($arr);
echo "排序后的数组: ";
print_r($arr);
?>- 实现原理和过程
构建最大堆：从数组的中间位置开始，逐个元素进行堆调整，确保每个节点都满足最大堆的性质，即父节点的值大于或等于子节点的值。
逐步将堆顶元素与堆中的最后一个元素交换，并将堆的大小减1。
对交换后的堆进行堆调整，将新的堆顶元素移动到合适的位置，使得剩余的元素继续构成最大堆。
重复步骤2和3，直到堆的大小为1，整个数组有序。
- 时间复杂度
堆排序的时间复杂度为O(nlogn)，无论是最好情况、平均情况还是最坏情况，都具有相同的时间复杂度。这使得堆排序成为一种稳定而高效的排序算法。
- 空间复杂度
堆排序的空间复杂度为O(1)，因为它只需要常数级的额外空间来存储一些辅助变量。
计数排序
- 实现思想
计数排序（Counting Sort）是一种线性时间复杂度的排序算法，适用于非负整数作为输入。它的核心思想是统计每个输入元素的出现次数，然后根据这些统计信息重建有序序列。
- Golang实现
package main
import "fmt"
func countingSort(arr []int) []int {
if len(arr) <= 1 {
return arr
}
max := arr[0]
min := arr[0]
// 找到最大值和最小值
for _, num := range arr {
if num > max {
max = num
}
if num < min {
min = num
}
}
// 创建计数数组并初始化为0
count := make([]int, max-min+1)
for _, num := range arr {
count[num-min]++
}
// 根据计数数组重建有序序列
sortedArr := make([]int, 0, len(arr))
for i, freq := range count {
for j := 0; j < freq; j++ {
sortedArr = append(sortedArr, i+min)
}
}
return sortedArr
}
func main() {
arr := []int{64, 34, 25, 12, 22, 11, 90}
fmt.Println("原始数组:", arr)
sortedArr := countingSort(arr)
fmt.Println("排序后的数组:", sortedArr)
}- PHP实现
<?php
function countingSort($arr) {
if (count($arr) <= 1) {
return $arr;
}
$max = max($arr);
$min = min($arr);
// 创建计数数组并初始化为0
$count = array_fill($min, $max - $min + 1, 0);
foreach ($arr as $num) {
$count[$num]++;
}
// 根据计数数组重建有序序列
$sortedArr = array();
foreach ($count as $num => $freq) {
for ($i = 0; $i < $freq; $i++) {
$sortedArr[] = $num;
}
}
return $sortedArr;
}
$arr = array(64, 34, 25, 12, 22, 11, 90);
echo "原始数组: ";
print_r($arr);
$sortedArr = countingSort($arr);
echo "排序后的数组: ";
print_r($sortedArr);
?>- 实现原理和过程
找到输入数组中的最大值和最小值，以确定计数数组的范围。
创建一个计数数组，其长度等于最大值和最小值之差加1，并初始化为0。
遍历输入数组，将每个元素的出现次数记录在计数数组中，计数数组的索引对应于输入元素减去最小值的值。
根据计数数组的统计信息，重建有序序列。遍历计数数组，将每个元素重复相应次数，得到排序后的数组。
- 时间复杂度
计数排序的时间复杂度为O(n + k)，其中n是输入数组的长度，k是计数数组的范围（即最大值与最小值之差加1）。
当k较小且接近n时，计数排序可以达到线性时间复杂度O(n)。
- 空间复杂度
计数排序的空间复杂度为O(k)，取决于计数数组的大小，与输入数组的规模n无关。
桶排序
- 实现思想
桶排序（Bucket Sort）是一种排序算法，它将待排序的元素分散到一组桶中，然后对每个桶中的元素进行排序，最后按照顺序将各个桶中的元素合并得到有序数组。桶排序适用于元素均匀分布在一定范围内的情况。
- Golang实现
package main
import (
"fmt"
"math"
)
func bucketSort(arr []float64) []float64 {
if len(arr) <= 1 {
return arr
}
// 寻找最大值和最小值
maxVal := arr[0]
minVal := arr[0]
for _, num := range arr {
if num > maxVal {
maxVal = num
}
if num < minVal {
minVal = num
}
}
// 计算桶的数量，每个桶的范围为(maxVal-minVal)/len(arr)
bucketCount := int(math.Floor((maxVal - minVal) / float64(len(arr)-1)))
if bucketCount <= 0 {
bucketCount = 1
}
// 创建桶
buckets := make([][]float64, bucketCount)
for i := 0; i < bucketCount; i++ {
buckets[i] = make([]float64, 0)
}
// 将元素分配到桶中
for _, num := range arr {
index := int(math.Floor((num - minVal) / float64(len(arr)-1)))
buckets[index] = append(buckets[index], num)
}
// 对每个桶中的元素进行排序
sortedArr := make([]float64, 0, len(arr))
for _, bucket := range buckets {
if len(bucket) > 0 {
insertionSort(bucket)
sortedArr = append(sortedArr, bucket...)
}
}
return sortedArr
}
func insertionSort(arr []float64) {
for i := 1; i < len(arr); i++ {
key := arr[i]
j := i - 1
for j >= 0 && arr[j] > key {
arr[j+1] = arr[j]
j--
}
arr[j+1] = key
}
}
func main() {
arr := []float64{0.8, 0.4, 0.1, 0.7, 0.9, 0.2}
fmt.Println("原始数组:", arr)
sortedArr := bucketSort(arr)
fmt.Println("排序后的数组:", sortedArr)
}- PHP实现
<?php
function bucketSort($arr) {
if (count($arr) <= 1) {
return $arr;
}
$maxVal = max($arr);
$minVal = min($arr);
// 计算桶的数量，每个桶的范围为(maxVal-minVal)/count($arr)
$bucketCount = max(1, floor(($maxVal - $minVal) / (count($arr) - 1)));
// 创建桶
$buckets = [];
for ($i = 0; $i < $bucketCount; $i++) {
$buckets[] = [];
}
// 将元素分配到桶中
foreach ($arr as $num) {
$index = floor(($num - $minVal) / (count($arr) - 1));
$buckets[$index][] = $num;
}
// 对每个桶中的元素进行排序
$sortedArr = [];
foreach ($buckets as $bucket) {
if (!empty($bucket)) {
insertionSort($bucket);
$sortedArr = array_merge($sortedArr, $bucket);
}
}
return $sortedArr;
}
function insertionSort(&$arr) {
$length = count($arr);
for ($i = 1; $i < $length; $i++) {
$key = $arr[$i];
$j = $i - 1;
while ($j >= 0 && $arr[$j] > $key) {
$arr[$j + 1] = $arr[$j];
$j--;
}
$arr[$j + 1] = $key;
}
}
$arr = [0.8, 0.4, 0.1, 0.7, 0.9, 0.2];
echo "原始数组: ";
print_r($arr);
$sortedArr = bucketSort($arr);
echo "排序后的数组: ";
print_r($sortedArr);
?>- 实现原理和过程
寻找输入数组中的最大值和最小值，以确定桶的范围。
计算桶的数量，每个桶的范围为(maxVal-minVal)/(n-1)，其中n是输入数组的长度。
创建桶并将元素分配到相应的桶中。
对每个桶中的元素进行排序，这里使用插入排序。
合并所有桶中的元素，得到排序后的数组。
- 时间复杂度
桶排序的时间复杂度取决于桶的数量和每个桶内部元素的排序复杂度。
如果桶的数量合理选择，每个桶内元素的数量平均为O(n/k)，其中k是桶的数量。每个桶内部使用插入排序，时间复杂度为O((n/k)^2)。因此，总体时间复杂度为O(n + n^2/k)。
当k接近n时，桶排序的时间复杂度近似为O(n)，最坏情况下为O(n^2)。
- 空间复杂度：
桶排序的空间复杂度主要取决于桶的数量和每个桶的大小，因此是O(n)。
基数排序
- 实现思想
基数排序（Radix Sort）是一种多关键字排序算法，它根据每个元素的位数从最低位到最高位进行排序。基数排序适用于非负整数或固定长度字符串的排序。
Golang实现
package main
import (
"fmt"
"math"
)
func radixSort(arr []int) []int {
if len(arr) <= 1 {
return arr
}
maxVal := max(arr)
// 计算最大值的位数
maxDigit := int(math.Floor(math.Log10(float64(maxVal))) + 1)
for digit := 1; digit <= maxDigit; digit++ {
arr = countingSortByDigit(arr, digit)
}
return arr
}
func countingSortByDigit(arr []int, digit int) []int {
buckets := make([][]int, 10)
for i := 0; i < 10; i++ {
buckets[i] = []int{}
}
for _, num := range arr {
digitVal := getDigit(num, digit)
buckets[digitVal] = append(buckets[digitVal], num)
}
sortedArr := []int{}
for _, bucket := range buckets {
sortedArr = append(sortedArr, bucket...)
}
return sortedArr
}
func getDigit(num, digit int) int {
return (num / int(math.Pow(10, float64(digit-1)))) % 10
}
func max(arr []int) int {
maxVal := arr[0]
for _, num := range arr {
if num > maxVal {
maxVal = num
}
}
return maxVal
}
func main() {
arr := []int{170, 45, 75, 90, 802, 24, 2, 66}
fmt.Println("原始数组:", arr)
sortedArr := radixSort(arr)
fmt.Println("排序后的数组:", sortedArr)
}- 实现原理和过程
首先，找到输入数组中的最大值，以确定最大值的位数（即最高位数）。
从最低位（个位）到最高位，依次进行排序。每一轮排序使用计数排序，根据当前位上的数字分配元素到桶中。
将各个桶中的元素合并得到新的数组，继续下一轮排序，直到排序完成。
- 时间复杂度
基数排序的时间复杂度取决于位数和每个位数上的排序复杂度。在最坏情况下，时间复杂度为O(k * n)，其中k是最大值的位数，n是输入数组的长度。通常情况下，k较小，因此基数排序通常具有线性时间复杂度O(n)。
- 空间复杂度
基数排序的空间复杂度主要取决于桶的数量和每个桶的大小，因此是O(n)。
时间复杂度总结
- 桶排序（Bucket Sort）：O(n) - 平均时间复杂度。
- 基数排序（Radix Sort）：O(n * k) - 平均时间复杂度，其中k是最大值的位数。
- 计数排序（Counting Sort）：O(n + k) - 平均时间复杂度，其中k是数据范围。
- 插入排序（Insertion Sort）：O(n^2) - 平均时间复杂度。
- 归并排序（Merge Sort）：O(n * log(n)) - 平均时间复杂度。
- 快速排序（Quick Sort）：O(n * log(n)) - 平均时间复杂度。
- 希尔排序（Shell Sort）：O(n^1.3) - 平均时间复杂度，不稳定。
- 选择排序（Selection Sort）：O(n^2) - 平均时间复杂度，不稳定。
- 堆排序（Heap Sort）：O(n * log(n)) - 平均时间复杂度，不稳定。
- 冒泡排序（Bubble Sort）：O(n^2) - 平均时间复杂度，稳定。
【申明：部分图片来源于网络，如有侵权，联系我们，删除[谢谢]】
本文暂时没有评论，来添加一个吧(●'◡'●)