一个博客总结十大排序算法

排序算法真的很多，最难受的是你学完以后过了半年就很难很顺利的实现出来了，笔者都已经写过三遍了......，大一时候写了一遍，一年前开始刷题时候学了一遍，面试前还得再看一遍~~，因此本篇博客对排序算法进行了整理，面试前看一下事半功倍。排序算法一般还是结合TOPK手撕，让手写一个快排或者最小堆居多。主要还是排序思想，比如归并排序的分治和。

从稳定和不稳定来看

1. 稳定：冒泡排序、选择排序、归并排序、计数排序、桶排序、基数排序。
2. 不稳定：插入排序、希尔排序、堆排序、快速排序。

从时间复杂度来看，分为平均，最坏，最好。这个应该是很显然的，就是三个层次，O(n^2^)、O(nlogn)、O(n)，O(n)只有满足一定条件的非比较排序算法才能满足。

附一个偷的图：

冒泡排序

• 因为排序过程形似泡泡一个一个往上冒因而得名。特点是相邻元素两两比较，这样最大值或最小值可以浮到数组的最后面。
• 它的优点是在经过优化后，对于有序或近乎有序的数组可以达到O(n)的时间复杂度。

private void bubbleSort(int[] a) {
    int cache = a.length - 1;  // 记录后面有序的
    int j;  
    while (true) {
        if (cache == 0) return;    // 处理到最后一个元素了
        j = cache;
        for (int i = 0; i < j; i++) {
            if (a[i] > a[i + 1]) {  // 交换位置
                int temp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = temp;
                cache = i;
            }
        }
    }
}

选择排序

• 顾名思义，每轮选择一个最大或最小的元素，然后从前往后目标元素和最大值或最小值交换即可。
• 优点是简单易懂、移动次数较少、时间复杂度确定

private void selectSort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) { // 外层控制排序的元素
        int min = i;
        for (int j = i + 1; j < a.length; j++) { // 找到剩余元素的最小值
            if (a[j] < a[min]) {
                min = j;
            }
        }
        if (min != i) {
            // 交换元素
            int temp = a[i];
            a[i] = a[min];
            a[min] = temp;
        }
    }
}

堆排序

• 堆排序是对选择排序的改进，它使用大顶堆来进行内层元素的选择。
• 优点是时间复杂度改进成了O(nlog(n))。

static class Heap {
    int[] arr;
    int size = 0;

    public Heap(int[] arr) {
        this.arr = arr;
        this.size = arr.length;
        heapify();
    }

    // 堆化
    private void heapify() {
        // 弗洛伊德堆化算法
        int nonLeafIndex = size / 2 - 1;
        for (int i = nonLeafIndex; i >= 0; i--) {
            down(i);
        }
    }

    // 取出元素
    private int poll() {
        if (size == 0) throw new RuntimeException();
        int polled = arr[0];
        // 首先交换最后一个元素和第一个元素，然后下沉即可。
        swap(0, size - 1);
        size--;
        down(0);    // 先size--，再下潜，不然之前删除的那个元素还是会参与比较
        return polled;
    }

    // 下潜
    private void down(int parent) {
        int left = 2 * parent + 1;
        int right = left + 1;
        int max = parent;
        // 比较left和right哪个值更大
        if (left < size && arr[left] > arr[max]) {
            max = left;
        }
        if (right < size && arr[right] > arr[max]) {
            max = right;
        }
        if (max != parent) {    // 如果还需要继续下潜的话
            swap(max, parent);// 交换两个节点
            down(max);  // 继续下潜
        }
    }

    private void swap(int curr, int parent) {
        int temp = arr[curr];
        arr[curr] = arr[parent];
        arr[parent] = temp;
    }

}

// 堆排序的思想很简单，就是把快排里面找最大值或者最小值的方法用堆实现了，这样可以达到nlog(n)的级别
private void heapSort(int[] a) {
    Heap heap = new Heap(a);
    for (int i = a.length - 1; i >= 0; i--) {
        // 拿到最大值
        int max = heap.poll();
        a[i] = max; // 直接赋值，不用交换，因为原始值都存到大顶堆里面了
    }
}

插入排序

• 插入排序是维护一个有序数组，在未排序数组中取出第一个元素插入到有序数组中，直至未排序数组长度为空。
• 优点是在小数据量和近乎有序情况下表现优异，常常用来优化编程语言的内置排序函数。

private void insertSort(int[] a) {
    for (int i = 1; i < a.length; i++) {    // 控制右侧数字
        int num = a[i];
        int j = i - 1;
        // 右移左边数组，直到找到插入位置
        while (j >= 0 && a[j] > num) {  // 当前元素大于要插入的元素
            a[j + 1] = a[j];
            j--;
        }
        if (j != i - 1) {   // 寻找完成后判断j是否改变，当然不判断也可以
            a[j + 1] = num;
        }
    }
}

希尔排序

• 希尔排序是对插入排序算法的改进，改变了任意一个元素移动到它应该在的位置的步长，比如可以一次移动32步而非1步。
• 优点是将插入排序算法的时间复杂度优化到了O(nlog(n))—>O(nlog^2^(n^2^))量级

private void shellSort(int[] a) {
    for (int gap = a.length >> 1; gap >= 1; gap/=2) {
        // 把之前插入排序的默认1改成gap即可，左边比较的步长也是gap，初始化时候也是gap；
        for (int i = gap; i < a.length; i++) {
            int num = a[i], j = i - gap;
            while (j >= 0 && a[j] > num) {
                a[j + gap] = a[j];
                j -= gap;
            }
            if (j != i - gap) {
                a[j + gap] = num;
            }
        }
    }
}

归并排序

• 归并排序的思想是分治合，切分到最小可治单元进行合。常常采用递归实现，称为自顶至下实现。
• 优点是最小、最坏、平均时间复杂度都是O(nlog(n))

private void mergeSort(int[] a) {
    split(a, 0, a.length - 1, new int[a.length]);
}

/**
 * 切分的递归方法
 *
 * @param a     原始数组
 * @param left  切分的左索引
 * @param right 切分的右索引
 * @param temp  临时数组，用于合并
 */
private void split(int[] a, int left, int right, int[] temp) {
    if (left == right) return; // 切分到只有一个元素了，“治”
    // 不停切分，“分”
    int mid = (left + right) / 2;
    split(a, left, mid, temp);
    split(a, mid + 1, right, temp);
    // 合并两个有序数组，“合”
    merge(a, left, mid, temp, mid + 1, right);
    System.arraycopy(temp, left, a, left, right - left + 1);    // 从left开始拷贝回去
}

/**
 * 合并两个有序数组
 *
 * @param a   原始数组
 * @param l1  数组1左索引
 * @param r1  数组1右索引
 * @param res 要合并到的数组
 * @param l2  数组2左索引
 * @param r2  数组2右索引
 */
private void merge(int[] a, int l1, int r1, int[] res, int l2, int r2) {
    int p1 = l1, p2 = l2;   // 双指针分别指向两个数组的起始索引
    int p = l1;  // 新数组的索引
    // 两个数组元素比较
    while (p1 <= r1 && p2 <= r2) {
        if (a[p1] <= a[p2]) {
            res[p++] = a[p1];
            p1++;
        } else {
            res[p++] = a[p2];
            p2++;
        }
    }
    // 处理之前没有处理到的数组
    if (p1 != r1 + 1) System.arraycopy(a, p1, res, p, r1 - p1 + 1); // 第一个数组有残留
    if (p2 != r2 + 1) System.arraycopy(a, p2, res, p, r2 - p2 + 1); // 第二个数组有残留
}

快速排序

• 快速排序也是采用分治的思想，流程是每轮选择一个基准点，将比它小的元素放到左边，比他大的放到右边，紧接着继续对另外两堆进行处理，直到遍历到每堆是一个元素。

• 快排的优点是在大数据量情况下几乎是性能最优异的排序算法

• 快排有两个因为分区十分不均匀导致的缺点

  • 处理反着有序的元素。时间复杂度会达到O(n^2^)，使用随机基准点解决
  • 处理大量重复元素，传统分区算法时间复杂度会达到O(n^2^)，改写分区算法兼容重复元素

• 有一个三向切分快速排序，分成三堆可以解决上面提到的两个问题，还是改写的分区算法。

    public void quickSort(int[] a) {
        quickSort(a, 0, a.length - 1);
    }

    // 递归入口
    private void quickSort(int[] a, int left, int right) {
        if (left >= right) return;  // left>=right
        int idx = partition2(a, left, right);
        quickSort(a, left, idx - 1);
        quickSort(a, idx + 1, right);
    }

    // 基础的分区，随机基准点+双边快排
    private int partition(int[] a, int left, int right) {
        int idx = (int) ((Math.random() * (right - left + 1)) + left);    // 生成[left,right]的随机索引
        swap(a, left, idx);    // 把随机值交换到前面
        int pivot = a[left];
        int i = left, j = right;    // 左右指针，i负责找大于基准点元素的，j负责找小于基准点元素的
        // 关于a[j]>pivot还是a[j]>=pivot，这个不影响，因为无论如何这个实现相等元素都会跑到一边去。但是不要都不相等。
        while (i < j) {
            // 不停找小于等于  基准点元素的
            while (i < j && a[j] >= pivot) {
                j--;
            }
            // 不停找大于基准点元素的
            while (i < j && a[i] <= pivot) {
                i++;
            }
            swap(a, i, j);
        }
        swap(a, left, i);   // 这个边界条件我的建议是背下来，最后把基准点和i的元素交换
        return i;
    }

    /*
     * 改进方法。首先这次左边和右边都是遇到相等的就停下来然后交换。
     * 同时更新i和j，这个时候可以把相等的元素打均匀。
     * */
    private int partition2(int[] a, int left, int right) {
        int randomIndex = (int) ((Math.random() * (right - left + 1)) + left);    // 生成[left,right]的随机索引
        swap(a, randomIndex, left);
        int bv = a[left];   // 每次取基准值为当前排序序列的第一个元素
        // 使用双边快排实现
        int i = left + 1;
        int j = right;
        // i小于j的时候直接开始找
        while (i <= j) {
            // 从左往右找，找到第一个比基准值大的元素(这里需要等于)
            while (i <= j && a[i] < bv) {
                i++;
            }
            // 从右往左找，使用while循环，直到找到一个比基准值小的或等于的元素
            while (i <= j && a[j] > bv) {
                j--;
            }
            // 兜底的判断，用于处理重复元素的情况。这里的两个一个++，一个--
            if (i <= j) {
                // i和j进行交换
                swap(a, i, j);
                i++;
                j--;
            }
        }
        // 当寻找完毕了，就把基准点换到i或者j这边
        swap(a, left, j);
        return j;
    }

    // 交换元素
    private void swap(int[] a, int idx1, int idx2) {
        int temp = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = temp;
    }

三向切分快速排序

public void quickSort(int[] a) {
        quickSort(a, 0, a.length - 1);
}
public static void quickSort(int[] a, int left, int right) {
    // 小数据可以使用插入排序，优化性能
    if (right - left <= 16) {
        insertSort(a, left, right);
        return;
    }
    // 递归出口，注意是left>=right，因为p为0的情况下就会如果相等就会爆栈
    if (left >= right) {
        return;
    }
    // 处理逆序数组
    int randomIndex = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
    swap(a, randomIndex, left);
    // 处理重复元素
    int lt = left, gt = right;  // 声明两个指针
    int pivot = a[left];    // 初始化基准点
    int i = left;   // 初始化指针
    // 6 4 3 2 8 5
    // i=0 gt=5 pivot=6 i=1 4<6 a[1]=a[0] a[0]=a[1] 4 6 3 2 8 5 i=2
    while (i <= gt) {
        // 小于基准点的时候更新lt的索引，并且交换原始数组的元素。更新i指针，
        // 根据上面的过程可以看到，a[lt]一定是已经判断过了（lt<=i），所以可以更新i指针。
        if (a[i] < pivot) {
            swap(a, lt++, i++);
            //  大于基准点的时候仅仅交换一下位置，不要更新i指针，因为当前交换的元素a[gt]还没有判断呢
        } else if (a[i] > pivot) {
            swap(a, i, gt--);
        }
        // 跟基准点相等的元素就直接跳过，不再处理了
        else {
            i++;
        }
    }
    quickSort(a, left, lt - 1);  // 基准点左边的元素
    quickSort(a, gt + 1, right); // 基准点右边的元素
}

// 交换元素
private void swap(int[] a, int idx1, int idx2) {
    int temp = a[idx1];
    a[idx1] = a[idx2];
    a[idx2] = temp;
}

计数排序

基数排序

桶排序