常用排序算法的实现与Comparator接口

概述

总结一下所有常用的排序算法。

桶排序

实现起来很是简单，创建一个大小为目标数组中最大值的数组，然后遍历目标数组，将对应的值当做索引插入到temp临时数组中。
之后遍历temp数组，如果存在内容，那么就输出这个索引就行了，反之不输入。
优点是速度较快，缺点就比较多了。最大值有多大，你就得开辟多大的数组，耗费空间过大。

    int[] arr = {1,8,5,3,2,4,6};
    int[] temp = new int[9];
    for (int i = 0; i < arr.length; i++) {
        temp[arr[i]] += 1;
    }
    for (int i = 0; i < temp.length; i++) {
        if (temp[i] != 0){
            System.out.print(i);

        }
    }

冒泡排序

1.通过从左往右依次对比，如果左边比右边大，那么就交换双方，依次循环N（数组长度 - 1）次。
2.循环上一步N（数组长度-1）次。
相对于桶排序而言，冒泡排序的空间复杂度就不是很高，因为它只是挨个进行交换。但缺点是如果数据庞大，它所消耗的时间就很长。

    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length-1-i; j++) {
            if (arr[j] > arr[j+1]){
                int t = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = t;
            }

        }
    }

快速排序

听名字就知道，这个算法是在排序算法中平均最快的一个。实现思路为：
1.选择最左边的数为基准数，
2.从右往左检索比基准数小的值
3.从左往右检索比基准数大的值
4.两边都找到之后进行交换
5.如果两者相遇，则将相遇的数值与基准数替换。 这个时候再将相遇数值的两端 0~相遇-1 相遇+1~结束，进行递归调用。

    public static void kp(int left,int right){
    if (left > right) return;
    int base = arr[left];
    int l = left;
    int r = right;

    while (l != r){
        while (arr[r] >= base && r > l){
            r--;
        }
        while (arr[l] <= base && l < r){
            l++;
        }

        if (r > l){
            int t = arr[r];
            arr[r] = arr[l];
            arr[l] = t;
        }

    }
    int t = arr[left];
    arr[left] = arr[l];
    arr[l] = t;
    kp(left,r-1);
    kp(r+1,right);

}

睡眠排序

哈哈哈这个是用来搞笑的,通过sleep进行延迟线程添加到list,实现排序哈哈哈哈...

        int[] arr = {1, 8, 2, 3, 4000, 7};
    List<Integer> list = new CopyOnWriteArrayList<>();
    ExecutorService ex = Executors.newFixedThreadPool(arr.length);
    for (int i = 0; i < arr.length; i++) {
        int finalI = i;
        ex.execute(() -> {
            try {
                Thread.sleep(arr[finalI]);
            } catch (InterruptedException e) {
                e.printStackTrace();
            } finally {
                list.add(arr[finalI]);
            }
        });
    }

    while (list.size() != arr.length) {}

    System.out.println(list);
    ex.shutdown();

堆排序

归并排序

Arrays.sort 与 Comparator接口

一般情况下我们真的需要手写这么多排序算法吗？其实没有必要。因为Java实际上已经内置了许多API...
正常情况下，我们只需要使用：

Arrays.sort(arr);

就可以完成从小到大的一个排序，并且它的函数底层是使用上面我们说的快速排序与堆排序，也就是说速度是非常快的~
如果我们想要逆序，我们就需要使用Comparator接口了。首先我们需要将这个数组更改为Integer类型，因为int作为一个基础类型并不能这样用。

     Arrays.sort(arr, new Comparator<Integer>() {
     @Override
     public int compare(Integer o1, Integer o2) {
            return o2-o1;
     }
 });

简单的说，如果返回值 >=1,那么就会不会交换o1与o2，反之，如果是-1则交换。如果我们想要从大到小进行排序，只需要将o2在大于o1的情况下进行交换就行了。
当然，不止可以交换数值哦，字符串、自定的类型、都是可以的。

在类中实现Comparator接口

class L implements Comparable<Integer>{

 @Override
 public int compareTo(Integer o) {
     return 0;
 }

}