十大经典排序算法（上篇）

概述

1.比较排序算法

算法	最好	最坏	平均	空间	稳定	思想	注意事项
冒泡	O(n)	O()	O()	O(1)	Y	比较	最好情况需要额外判断
选择	O()	O()	O()	O(1)	N	比较	交换次数一般少于冒泡
堆	O()	O()	O()	O(1)	N	选择	堆排序的辅助性较强，理解前先理解堆的数据结构
插入	O(n)	O()	O()	O(1)	Y	比较	插入排序对于近乎有序的数据处理速度比较快，复杂度有所下降，可以提前结束
希尔	O(nlogn)	O()	O()	O(1)	N	插入	gap序列的构造有多种方式，不同方式处理的数据复杂度可能不同
归并	O()	O()	O()	O(n)	Y	分治	需要额外的O(n)的存储空间
快速	O()	O()	O()	O(logn)	N	分治	快排可能存在最坏情况，需要把枢轴值选取得尽量随机化来缓解最坏情况下的时间复杂度

2.非比较排序算法

n:数组长度；k:桶长度；d:基数位数

3.稳定性

在排序算法中，稳定性指的是排序算法在处理相同值的元素时，是否能够保持它们的原始顺序。

• 稳定排序算法：如果一个排序算法在排序过程中，能够保证具有相同值的元素在排序后的相对位置与排序前相同，那么这个排序算法就是稳定的。
• 不稳定排序算法：如果一个排序算法在排序过程中，不能保证具有相同值的元素在排序后的相对位置与排序前相同，那么这个排序算法就是不稳定的。

一、冒泡排序

1.介绍

冒泡排序（Bubble Sort）是一种简单的排序算法，其基本原理是通过重复遍历待排序的数列，依次比较相邻的元素，如果它们的顺序错误就交换它们的位置，直到整个数列有序。

2.排序步骤

• 从数列的第一个元素开始，依次比较相邻的两个元素。
• 如果前一个元素大于后一个元素，就交换它们的位置。
• 每次遍历后，最大的元素会“冒泡”到数列的末尾（因此得名“冒泡排序”）。
• 每次遍历完成后，可以减少一个排序的范围，因为最大的元素已经在正确的位置。
• 重复上述过程，直到没有需要交换的元素为止，排序完成。

冒泡排序.png

3.代码实现

迭代实现

    /**
     * 冒泡排序
     * @param arr
     */
    public static void bubble(int[] arr) {
        // 控制总轮数
        for (int i = 0; i < arr.length; i++) {
            // 每次未排序区域交换的次数 在逐渐减少
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    //交换
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

递归实现：

    /**
     * 递归冒泡
     * @param arr
     * @param right
     */
    public static void bubbleRecursion(int[] arr,int right) {
        if (right == 0) {
            return;
        }
        for (int i = 0; i < right; i++) {
            if (arr[i] > arr[i + 1]) {
                swap(arr, i, i + 1);
            }
        }
        bubbleRecursion(arr, right - 1);
    }

4.优化

每次循环时，若能确定更合适的右边界，则可以减少冒泡轮数:
定义变量boundary，用来记录最后交换的索引位置；每次交换都更新变量。如果boundary没有被更新，说明后续的没有发生交换，就是已排好序的了，那么下一轮冒泡，以boundary作为交换次数的边界，就可以减少不必要的遍历次数。
boundary就是未排序和已排序的分界点。

迭代实现：

    /**
     * 冒泡优化：使用变量记录有序区域，下次无需重复比较
     * @param arr
     */
    public static void bubble2(int[] arr) {
        int num = arr.length - 1;
        // 冒泡的轮次
        for (int i = 0; i < arr.length; i++) {
            // 记录已排序和未排序的边界点 boundary左侧为未排序区域，右侧为已排序区域
            int boundary = 0;
            // 具体的每一轮冒泡：每次未排序区域交换的次数 在逐渐减少
            for (int j = 0; j < num; j++) {
                // 当发生了交换，就把boundary更新为j，
                if (arr[j] > arr[j + 1]) {
                    //交换
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    boundary = j;
                }
            }
            // 更新未排序区域的边界 减少比较的次数，只要没交换 就没有更新boundary 说明后面都是有序的
            num = boundary;

            // 如果没有发生任何交换，说明数组已经有序，可以提前退出
            if (boundary == 0) {
                break;
            }
        }
    }

递归实现：

    /**
     * 递归冒泡优化
     * @param arr
     * @param right
     */
    public static void bubbleRecursion1(int[] arr,int right) {
        if (right == 0) {
            return;
        }
        int flag = 0;
        for (int i = 0; i < right; i++) {
            if (arr[i] > arr[i + 1]) {
                swap(arr, i, i + 1);
                // 边界右边的都是有序的
                flag = i;
            }
        }
        bubbleRecursion1(arr, flag);
    }

二、选择排序

1.基本思想

在未排序的部分中找到最大的元素，并将它与当前未排序部分的最后一个元素交换位置。然后继续对剩下的未排序部分重复这个过程，直到整个数组排好序。

选择排序.png

2.代码实现

    /**
     * 选择排序
     * @param arr
     */
    public static void selectSort(int[] arr) {
        // 选择的轮数
        for (int right = arr.length - 1; right > 0; right--) {
            // 假设最后一个元素是最大的 从开头往后遍历，如果遇到比这个数大的，就重新把大的复制给max
            // 选出了最大的元素，把元素交换到a.length依次递减
            int max = right;
            // 每一轮里遍历数组，找出最大值
            for (int i = 0; i < right; i++) {
                if (arr[i] > arr[max]) {
                    max = i;
                }
            }
            // 如果max等于了right 就不需要交换了 说明本身max就是这一轮最大的
            if (max != right) {
                // 找出了最大的元素为max索引位置 把最大的元素交换到最后(随着循环一直递减)第二个交换到的位置为倒数第二个
                int temp = arr[max];
                arr[max] = arr[right];
                arr[right] = temp;
            }
        }
    }

三、堆排序

堆是一棵完全二叉树，具有以下性质：

• 大顶堆（Max-Heap）：父节点的值总是大于或等于子节点的值。
• 小顶堆（Min-Heap）：父节点的值总是小于或等于子节点的值。

1.基本思想

将待排序的数组构建成一个大顶堆。
将堆顶元素（最大元素）与堆的最后一个元素交换，然后减小堆的大小，再对堆进行调整，使其重新符合堆的性质。
重复上述步骤，直到堆的大小为1，此时整个数组就已排序完成。
堆排序的时间复杂度是 O(n log n)，空间复杂度是 O(1)，属于不稳定的排序算法。

2.步骤

• 1.构建堆：首先将待排序的数组构建成一个大顶堆。
• 2.交换堆顶元素与数组的最后一个元素：交换后，堆的大小减1，堆顶元素失去堆的性质。
• 3.重新调整堆：调整堆使其重新满足堆的性质。
• 4.重复步骤2和3，直到堆的大小为1。

堆排序.png

3.代码实现

public class HeapSort {

    /**
     * 堆排序
     *
     * @param arr
     */
    private int[] heapSort(int[] arr) {
        int size = arr.length;
        // 1.建堆 堆顶元素是最大的
        heapify(arr, size);

        while (size > 1) {
            // 2.堆顶元素与堆底交换 升序排列 最大的元素排在最右侧
            swap(arr, 0, size - 1);
            // 缩小堆
            size--;
            // 调整堆
            downToProper(0, arr, size);
        }
        return arr;
    }


    public int[] sort(int[] arr) {
        int size = arr.length;
        // 1.建堆 堆顶元素是最大的
        heapify(arr, size);
        for (int right = arr.length - 1; right > 0; right--) {
            swap(arr, 0, right);
            downToProper(0, arr, right);
        }
        return arr;
    }

    /**
     * 建堆
     */
    public void heapify(int[] arr,int size) {
        int index = size / 2 - 1;
        for (int i = index; i >= 0; i--) {
            downToProper(i, arr, size);
        }
    }


    /**
     * 交换两个元素
     *
     * @param i
     * @param j
     */
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 元素下沉到正确位置
     *
     * @param parentIndex 父节点的索引
     * @param arr         排序数组
     * @param size        数组大小
     */
    private void downToProper(int parentIndex, int[] arr, int size) {
        while (true) {
            // 假设父节点索引的值是最大的
            int maxIndex = parentIndex;
            // 计算出左右孩子节点的索引
            int leftIndex = 2 * parentIndex + 1;
            int rightIndex = leftIndex + 1;
            if (leftIndex < size && arr[leftIndex] > arr[maxIndex]) {
                // 左孩子值比父节点值大，替换为左孩子索引
                maxIndex = leftIndex;
            }
            if (rightIndex < size && arr[rightIndex] > arr[maxIndex]) {
                // 右孩子值比父节点值大，替换为右孩子
                maxIndex = rightIndex;
            }
            if (maxIndex == parentIndex) {
                // 父节点已经是最大的了 没有更大的孩子
                break;
            }
            // 父节点不是最大的，发生了交换
            int temp = arr[maxIndex];
            arr[maxIndex] = arr[parentIndex];
            arr[parentIndex] = temp;

            // 更新parentIndex
            parentIndex = maxIndex;
        }
    }

}

四、插入排序

1.基本思想

将待排序的元素逐一插入到已排序的部分中，直到所有元素有序

2.排序步骤：

• 1.假设第一个元素已经排好序，从第二个元素开始，依次将当前元素与前面已排序的部分进行比较。
• 2.如果当前元素比前面某个元素小，则将这个元素插入到前面已排序部分的合适位置。
• 3.重复这个过程，直到整个数组排好序。

插入排序.png

3.代码实现

要点：

• 将数组分为两部分[0 .. low-1] 和 [low .. a.length-1]
  • 左边[0 .. low-1]是已排序部分
  • 右边[low .. a.length-1]是未排序部分
• 每次从未排序区域取出low位置的元素, 插入到已排序区域

    /**
     * 插入排序
     * @param arr
     */
    public static void insertSort(int[] arr) {
        // low为未排序区域的左边界，依次递增 ，取出来，插入到已排序区域
        for (int low = 1; low < arr.length; low++) {
            // 存入到临时变量中
            int t = arr[low];
            // 依次与左侧的已排序区域的元素比较，如果比左侧区域的小，就把左侧的区域往右移动，空出位置给t插入
            int i = low - 1;
            // i还在有效范围内， i所在元素值比t大，就把元素依次往右移动，空出位置
            while (i >= 0 && arr[i] > t) {
                arr[i + 1] = arr[i];
                i--;
            }
            // 如果左侧的都比当前的t要小 说明t已经是在正确的位置了
            if(i != low-1){
                //i+1的位置就是空出的位置
                arr[i + 1] = t;
            }
        }
    }

五、希尔排序

1.介绍

希尔排序（Shell Sort）是插入排序的一种改进版本。
它通过将数组分成若干个子序列来进行排序，并逐步减少这些子序列的间隔，最终对整个数组进行插入排序。这样可以使元素移动更远，减少了交换次数，从而提高排序效率。

2.基本思想

• 分组：首先将待排序的数组按照一定的步长（gap）分成若干个子数组，对每个子数组进行插入排序。
• 减小步长：然后逐渐减小步长，再进行插入排序。步长一般会从数组长度的一半开始，每次减少为原来的一半，直到步长为 1 时，进行一次标准的插入排序。
• 排序完成：步长减小到 1 时，实际上已经对整个数组进行了有效的排序，最终得到有序的数组。

步骤.png

3.代码实现

分组实现插入，每组元素间隙称为 gap：每轮排序后 gap 逐渐变小，直至 gap 为 1 完成排序

    /**
     * 希尔排序
     * @param arr
     */
    public static void shellSort(int[] arr) {
        // 按照gap分组的元素进行插入排序  逐渐缩小gap 直至为1
        for (int gap = arr.length >> 1; gap > 0; gap = gap >> 2) {
            // 实现插入排序
            for (int low = gap; low < arr.length; low++) {
                // 准备要插入的元素暂存到temp
                int temp = arr[low];
                // 已排序区域的右边界
                int i = low - gap;
                while (i >= 0 && arr[i] > temp) {
                    // 空出插入位置
                    arr[i + gap] = arr[i];
                    i = i - gap;
                }
                if (i != low - gap) {
                    // 往空位插入
                    arr[i + gap] = temp;
                }
            }
        }
    }

对插入排序的优化，让元素更快速地交换到最终位置