# 【排序】

# 冒泡排序

冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就交换它们。

# 冒泡排序优点

简单易懂：冒泡排序算法的思想非常直观，易于理解和实现。
代码量小：冒泡排序的代码实现非常简单，只需要几行代码即可完成。
稳定排序：相等元素的相对顺序不会改变，保证了排序的稳定性。

# 冒泡排序缺点

效率较低：冒泡排序的时间复杂度为O(n^2)，性能不如其他高级排序算法。
不适用于大规模数据：当需要排序的数据规模较大时，冒泡排序的效率会很低，需要耗费较长的时间。

function bubbleSort(arr) {
  const len = arr.length;
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

// example usage
const arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
const sortedArr = bubbleSort(arr);
console.log(sortedArr); // [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

# 选择排序

选择排序是一种简单直观的排序算法，它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置。

# 选择排序优点

简单易懂：选择排序算法的思想非常直观，易于理解和实现。
稳定排序：相等元素的相对顺序不会改变，保证了排序的稳定性。
不需要额外的存储空间：选择排序只需要一个额外的变量来记录最小元素的位置，不需要额外的存储空间。

# 选择排序缺点

效率较低：选择排序的时间复杂度为O(n^2)，性能不如其他高级排序算法。
不适用于大规模数据：当需要排序的数据规模较大时，选择排序的效率会很低，需要耗费较长的时间。
不稳定排序：如果两个相等元素的位置交换了，它们的相对顺序就会改变，不保证排序的稳定性。

function selectionSort(arr) {
  let len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    if (i !== minIndex) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  return arr;
}
let arr = [3, 5, 2, 1, 4];
console.log(selectionSort(arr)); // 输出 [1, 2, 3, 4, 5]

# 插入排序

插入排序是一种简单直观的排序算法，它的工作原理是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加1的有序表。

# 插入排序优点

实现简单，易于理解和实现。
对于小规模数据的排序效率较高，由于算法的时间复杂度为O(n^2)，所以在数据量小的情况下，插入排序的速度会很快。
稳定性好，相同的元素在排序前后顺序不变。

# 插入排序缺点

插入排序算法的时间复杂度为O(n^2)，对于大规模数据的排序效率较低。
插入排序算法的空间复杂度为O(1)，排序过程中不需要额外的存储空间，但是由于需要频繁地移动元素位置，所以在实际运用中会占用较多的计算资源。
插入排序算法的排序稳定性和排序效率之间存在一定的矛盾。如果要保证排序的稳定性，就必须在插入元素的时候维护元素的相对位置，这会导致排序效率降低。如果不考虑排序稳定性，可以通过交换元素位置的方式提高排序效率，但是这样会导致排序的不稳定性。

function insertionSort(arr) {
  let len = arr.length;
  for (let i = 1; i < len; i++) {
    let temp = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > temp) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = temp;
  }
  return arr;
}
let arr = [3, 5, 2, 1, 4];
console.log(insertionSort(arr)); // 输出 [1, 2, 3, 4, 5]

# 归并排序

# 归并排序优点

时间复杂度为 O(n log n)，比许多排序算法都要快，尤其是在处理大数据量时；
稳定性高，即在排序过程中相同元素的相对位置不会发生变化；
可以实现并行化排序，从而更快地处理大规模数据。

# 归并排序缺点

归并排序需要额外的空间来存储数组，即需要一个与待排序数组同样大小的辅助数组；
归并排序虽然时间复杂度较低，但是常数项较大，因此对于小规模数据，其他算法可能更快。

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  const mid = Math.floor(arr.length / 2);
  const leftArr = mergeSort(arr.slice(0, mid));
  const rightArr = mergeSort(arr.slice(mid));
  return merge(leftArr, rightArr);
}
function merge(leftArr, rightArr) {
  let result = [];
  let i = 0;
  let j = 0;
  while (i < leftArr.length && j < rightArr.length) {
    if (leftArr[i] < rightArr[j]) {
      result.push(leftArr[i]);
      i++;
    } else {
      result.push(rightArr[j]);
      j++;
    }
  }
  return result.concat(leftArr.slice(i)).concat(rightArr.slice(j));
}

# 快速排序

# 快速排序优点

时间复杂度较低：平均时间复杂度为 O(nlogn)，最坏情况下为 O(n^2)，但这种情况出现的概率比较小。
空间复杂度较低：只需要一个辅助空间用于交换数据，不需要额外的空间。
可以进行原地排序：不需要额外的空间进行排序，所以它可以在非常有限的内存中运行。

# 快速排序缺点

最坏情况下时间复杂度较高：当数据已经有序或接近有序时，快速排序的效率将大大降低，最坏情况下时间复杂度为 O(n^2)。
不稳定排序：快速排序在排序的过程中，不保证相等的元素相对顺序不变，可能会导致稳定性问题。

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  const pivot = arr[0];
  const left = [];
  const right = [];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
}

// example usage
const arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
const sortedArr = quickSort(arr);
console.log(sortedArr); // [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

# JavaScript 常用大到小（权重）排序

let arr = [6,10,2,8,4];
arr.sort(
    function(a,b) 
    { 
        // if((b - a) > 0)
        // {
        //     return 1;// b 比 a 大，返回 b在前a在后[b,a]
        // }
        // return -1;
        return b - a;// 等同于上面
    }
);
console.log(arr);// 输出[ 10, 8, 6, 4, 2 ]

# Godot 常用大到小（权重）排序

extends Node2D

func _ready():
  var arr:Array[int] = [6,10,2,8,4];
  arr.sort_custom(sort_function)
  print(arr)# 输出 [10, 8, 6, 4, 2]

# 按照权重排序
func sort_function(a,b):
  #if a > b :
    #return true
  #else :
    #return false
  return (a-b) > 0 # 等同上面

← 【A星寻路】【王浩瓷砖】 →