新生代程序员必须会的排序法

灭霸排序

检查数组是否已排序，若未排序，则随机将一半元素化为尘埃，重复此过程直到数组有序。

时间复杂度：O(n^2) 空间复杂度：O(1)

image

function thanosSort(arr){
  function isSorted(arr){
    for(let i=0;i<arr.length-1;i++){
      if(arr[i]>arr[i+1]) return false;
    }
    return true;
  }

  while(!isSorted(arr)){
    const half=Math.floor(arr.length/2);
    for(let i=0;i<half;i++){
      const r=Math.floor(Math.random() * (arr.length));
      arr.splice(r,1);//删除掉下标为r的元素
    }
  }
  return arr;
}

斯大林排序

遍历数组，仅保留非递减元素，仍和小于当前最大值的元素都会被清除。

时间复杂度：O(n) 空间复杂度：O(n)

image

def stalinSort(arr):
    if len(arr) ==0:
        return []
    kept = [arr[0]]
    maxSoFar = arr[0]
    for i in range(1,len(arr)):
        if arr[i] >= maxSoFar:
            kept.append(arr[i])
            maxSoFar = arr[i]
    return kept

拒绝排序

检查数组是否为正序，当不是正序时拒绝排序

时间复杂度：O(n) 空间复杂度：O(1)

image

# 拒绝排序
def rejectSort(arr):
    for i in range(len(arr)-1):
        if arr[i] > arr[i+1]:
            print('不是正序的我不排')
            break
    print(arr)

奇迹排序

检查数组是否已排序，如果未排序，它将等待奇迹发生（如宇宙射线将内存中的一个位翻转）来对数组进行排序，它会反复循环检查，直到奇迹发生。

时间复杂度：O(∞) 空间复杂度：O(1)

image

function miracleSort(arr) {
  let isSorted = false;
  while (!isSorted) {
    isSorted = true;
    for (let i = 0; i < arr.length; i++) {
      if (arr[i] > arr[i + 1]) {
        isSorted = false;
        break;
      }
    }
    if(!isSorted){
      // 等待奇迹发生
      waitForMiracle();
    }
  }
}

指针排序

利用鼠标指针，手动拖拽元素进行排序

时间复杂度：O(手速) 空间复杂度：O(1)

image

function humanSort(arr){
  while(!sorted(arr)){
    let bar = user.grab();
    let pos = user.dragTo();
    insert(arr,bar,pos);
  }
}

洗牌排序

纯靠运气排序，运气好一次成功，运气不好永远排不玩

时间复杂度：O(luck) 空间复杂度：O(1)

image

def bogosort(arr):
    while not is_sorted(arr):
        random.shuffle(arr)
    return arr