时间戳

首页 > 技术文章 > 数组排序

数组排序

dingshaohua 2021-09-06 11:53 原文

冒泡排序

大的下沉，轻的冒泡

  • 每趟排序，只排出最大值放最后。 即每次都会将大的下沉操作
  • 趟排序遍历到最后一个元素不需要排，肯定是最小的 所以趟数是length-1
  • 每趟排序 包含内循环也要少一次 length-1 因为是两两比较。 同时每趟排序还要减去已走的趟数 因为每一趟都会下沉一个，决定了一些大值的排序，所以没必要重复对比已有的结果序部分 所以每趟的遍历次数最终是 length-1-当前的趟数索引
  • 每次排序（内循环）都是相邻比较 并决定是否 交换位置
const arr = [11, 3, 6, 2, 9];
for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
        const beforeSort = JSON.stringify(arr);
        const temp = arr[j + 1];
        if (arr[j] > arr[j + 1]) {
            arr[j + 1] = arr[j];
            arr[j] = temp;
        }
        console.log(`<---第${j + 1}次: 比较前${beforeSort} 比较后得出${JSON.stringify(arr)} 本次对比${arr[j]}、${arr[j + 1]} `);
    }
    console.warn(`第${i + 1}趟：比较后得出${JSON.stringify(arr)}`);
}
console.error(`最终得出${JSON.stringify(arr)}`);

快排

归并排序使用的就是分治思想。分而治之，将一个大问题分解成小的子问题来解决，小的子问题解决了，大问题也就解决了。

const array = [11, 3, 6, 2, 9];
const quickSort = function (arr,type) {
    if (arr.length <= 1) { return arr; } //空或1说明某子组已经排序完毕
    
    // 找到基准数（中间元素）
    const centIndex = Math.floor(arr.length / 2);
    const cent = arr[centIndex];
    console.warn(`${type}组${JSON.stringify(arr)}进来排序，找到中间元素：元素${cent}`);
    
    // 比基数小的放左边容器，大的放右边
    const left = [],right = [];
    for (let i = 0; i < arr.length; i++) {
        arr[i] < cent && left.push(arr[i]);
        arr[i] > cent && right.push(arr[i]);
    }
    console.log(`本轮的left为${left.length===0?'[]':left}，right为${right.length===0?'[]':right}`);

    // 合并小、中、大数据，递归
    return [...quickSort(left,'left'), ...[cent], ...quickSort(right,'right')];
};
const res = quickSort(array,'all');
console.error(`最终的排序结果${res}`);

程序执行图如下，加深理解

搞笑无用的--睡眠排序

这是一个思想比较简单，脑洞巨大的算法 -- 我们知道sleep方法可以让一个线程睡眠s毫秒，如果需要对一个有n个数的数列进行排序，我们何不为每个数创建一个线程，然后让每个线程都睡眠该数的时间，那么对于越小的数，其睡眠时间越短，越大的数，其睡眠时间越长，最后就使得所有元素完成“排序”了
java版

public void sleepSort(int[] arr){

        /** 创建线程类 */
        class Slee extends Thread{

            private int time;

            public Slee(int time){
                this.time=time;
            }

            public void run(){
                try {
                    /* 因为毫秒时间太短 如果两个数相差比较小 完成不了排序 建议乘一个系数 比如10 */
                    Thread.sleep(time*10);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                System.out.print(time+", ");
            }
        }

        /* 排序 */
        for (int i = 0; i < arr.length; i++) {
            new Slee(arr[i]).start();
        }
    }

javaScript版本

const array = [11, 3, 6, 2, 9];
const sleepSort = [];
for (let index = 0; index < array.length; index++) {
    const element = array[index];
    setTimeout(()=>{
        sleepSort.push(element)
    },element*1000)
    
}
setInterval(() => {
    console.log(sleepSort);
}, 1000);

搞笑无用的--猴子排序

猴子排序引用了无限猴子定理：即一只猴子随机不停的敲击键盘，如果时间足够长，那么它总有可能会打出特定的文本，比如莎士比亚全集？，算法通过不停的随机排列数组，直到数组有序
结合无限猴子定理考虑的话，最终的答案就是只要你愿意等足够久的时间，最终一定能得到有序序列(●'◡'●)

java版本

/* 判断一个数列是否有序 */
    public boolean isSort(int[] arr){
        for (int i = 0; i < arr.length-1; i++) {
            if(arr[i+1]<arr[i]){
                return false;
            }
        }
        return true;
    }

    public void monkeySort(int[] arr){
        int count=0;
        Random random=new Random();
        do{
            /* 从待排序数组右边随机抽取一位数与左边进行交换*/
            for (int i = 0; i < arr.length-1; i++) {
                count++;
                int t=(random.nextInt(arr.length-i)+i);
                int tmp=arr[i];
                arr[i]=arr[t];
                arr[t]=tmp;
            }
        }while(!isSort(arr));
        
        System.out.println(count+"  "+Arrays.toString(arr));
    }

javaScript版本

const array = [11, 3, 6, 2, 9];

/* 判断一个数列是否有序 */
const isSort = (arr) => {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i + 1] < arr[i]) {
            return false;
        }
    }
    return true;
}

/* 开始排序 */
let count = [];
do {
    for (let i = 0; i < array.length-1; i++) {
        let randomIndex = Math.floor(Math.random() * (array.length-1));
        let tmp = array[i];
        array[i] = array[randomIndex];
        array[randomIndex] = tmp;
    }
    count.push(JSON.stringify(array));
} while (!isSort(array));
console.log(`排序${count.length}次：`,array);
console.log(count);

推荐阅读