MAQI' blog

念两句诗

八大排序算法

2024-08-22 浏览 面试必备 2596字 12 min read 繁

插入排序

直接插入排序

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

时间复杂度：O(N^2) 空间复杂度：O(1) 稳定

public static void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;

        // 将选中的元素与已排序的元素进行比较，并将较大的元素向后移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        // 将选中的元素插入到正确的位置
        arr[j + 1] = key;
    }
}
直接插入排序

希尔排序

希尔排序在直接排序之前，进行预排列，将某些极端数据更快的排列到数列前面，构成一个接近排列好的序列，最后再进行一次直接插入排序。预排列的原理也是插入排列，只不过这里的将数组分成了gap组，分别对每一个小组进行插入排序。希尔排序是对直接插入排序的优化，当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。

时间复杂度：O(N*logN) 空间复杂度O(1) 不稳定

public static void shellSort(int[] arr) {
    int n = arr.length;
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i += 1) {
            int key = arr[i];
            int j = i;

            // 将arr[i]插入到前面已经排好的序列中
            while (j >= gap && arr[j - gap] > key) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = key;
        }
    }
}
希尔排序

选择排序

直接选择排序

每一次遍历待排序的数据元素从中选出最小（或最大）的一个元素，存放在序列的起始（或者末尾）位置，直到全部待排序的数据元素排完。

时间复杂度：O(N^2) 空间复杂度：O(1) 不稳定

public static void selectionSort(int[] arr) {
    int n = arr.length;

    // 外层循环控制排序的轮数
    for (int i = 0; i < n - 1; i++) {
        // 假设当前位置是最小值
        int minIndex = i;
        // 内层循环用于找到最小值的索引
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j; // 更新最小值的索引
            }
        }
        // 将找到的最小值和当前位置的值交换
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}
直接选择排序

这里我们还可以对直接选择排序做一个优化：每次遍历待排序数据找出最大和最小的数据，分别排列到序列起始和末尾。

public static void optimizedSelectionSort(int[] arr) {
    int n = arr.length;

    // 外层循环控制排序的轮数
    for (int i = 0; i < n / 2; i++) {
        int minIndex = i;
        int maxIndex = i;
        // 内层循环用于找到最小值和最大值的索引
        for (int j = i + 1; j < n - i; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j; // 更新最小值的索引
            }
            if (arr[j] > arr[maxIndex]) {
                maxIndex = j; // 更新最大值的索引
            }
        }
        // 将找到的最小值和当前位置的值交换
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
        // 将找到的最大值和末尾位置的值交换
        if (maxIndex != n - i - 1) {
            temp = arr[n - i - 1];
            arr[n - i - 1] = arr[maxIndex];
            arr[maxIndex] = temp;
        }
    }
}

堆排序

堆排序是指利用堆（数据结构）进行选择数据的一种排序算法。基本思想：

  1. 原则：先将原数组建成堆，需要注意的是升序需要建大堆，降序需要建立小堆
  2. 建堆：一个根节点与子节点数据如果不符合大堆结构，那么则对根节点数据进行向下调整，而向下调整的前提是左右子树也符合大堆结构,所以从堆尾数据的根节点位置开始向下调整建大堆
  3. 排序：大堆堆顶数据一定是待排数据中最大的，将堆顶数据与堆尾数据交换,交换后将除堆尾数据看成新堆，对现堆顶数据进行向下调整成大堆,以此循环直至排列完毕
  4. 向下调整：找到子节点中的较大数据节点比较，如果父节点数据比子节点小则交换，直到不符合则停止向下交换，此时再次构成了一个大堆结构

时间复杂度：O(N*logN) 空间复杂度O(1) 不稳定

// 构建最大堆
public static void buildMaxHeap(int[] arr, int n) {
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
}

// 堆调整
public static void heapify(int[] arr, int n, int i) {
    int largest = i; // 初始化最大值为根
    int left = 2 * i + 1; // 左子节点
    int right = 2 * i + 2; // 右子节点

    // 如果左子节点比根大，则更新最大值
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    // 如果右子节点比最大值还大，则更新最大值
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    // 如果最大值不是根，交换它们并继续堆调整
    if (largest != i) {
        int swap = arr[i];
        arr[i] = arr[largest];
        arr[largest] = swap;

        // 递归地堆调整子树
        heapify(arr, n, largest);
    }
}

// 堆排序
public static void heapSort(int[] arr) {
    int n = arr.length;
    buildMaxHeap(arr, n);

    // 一个个从堆顶取出元素
    for (int i = n - 1; i >= 0; i--) {
        // 将当前的根（最大值）与最后一个元素交换
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // 堆调整剩下的元素
        heapify(arr, i, 0);
    }
}
堆排序

交换排序

冒泡排序

每次遍历待排序数组，对相邻数据进行比较，不符合排序要求则交换

时间复杂度：O(N^2) 空间复杂度：O(1) 稳定

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            // 遍历数组，比较相邻元素，如果顺序错误就交换
            if (arr[j] > arr[j + 1]) {
                // 交换arr[j]和arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
冒泡排序

快排

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列。左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值。

时间复杂度：O(N*logN) 空间复杂度：O(logN) 不稳定

/*
  left:数组左边界
  right：数组右边界
*/
//递归版本
public void quickSort(int[] arr, int left, int right){
    if(left < right){
        int pos = partition(arr, left, right);
        quickSort(arr, left, pos - 1);
        quickSort(arr, pos + 1, right);
    }
}
//非递归版本
public static void quickSort(int[] arr, int low, int high) {
    Stack<Integer> stack = new Stack<>();
    stack.push(low);
    stack.push(high);

    while (!stack.isEmpty()) {
        // 弹出高和低索引
        high = stack.pop();
        low = stack.pop();

        // 找到分区点
        int partitionIndex = partition(arr, low, high);

        // 如果分区点的左边有元素，那么将其推入栈中
        if (partitionIndex > low) {
            stack.push(low);
            stack.push(partitionIndex - 1);
        }

        // 如果分区点的右边有元素，那么将其推入栈中
        if (partitionIndex < high) {
            stack.push(partitionIndex + 1);
            stack.push(high);
        }
    }
}

public int partition(int[] arr, int left, int right){
    int base = arr[left];
    while(left < right){
        //从右向左找，比base大，right--
        while(left < right && arr[right] >= base){
            right--;
        }
        arr[left] = arr[right];
        //从左向右找，比base小，left++
        while(left < right && arr[left] <= base){
            left++;
        }
        arr[right] = arr[left];       
    }
    arr[left] = base;
    return left;
}
快排

归并排序

归并排序

归并排序是建立在归并操作上的一种有效的排序算法，采用分治法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

// 主归并排序函数
public static void mergeSort(int[] array, int left, int right) {
    if (left < right) {
        int middle = (left + right) / 2;

        // 递归地对左半部分排序
        mergeSort(array, left, middle);
        // 递归地对右半部分排序
        mergeSort(array, middle + 1, right);
        // 合并两个已排序的子数组
        merge(array, left, middle, right);
    }
}

// 合并两个已排序的子数组
public static void merge(int[] array, int left, int middle, int right) {
    // 计算子数组的大小
    int n1 = middle - left + 1;
    int n2 = right - middle;

    // 创建临时数组
    int[] leftArray = new int[n1];
    int[] rightArray = new int[n2];

    // 拷贝数据到临时数组
    System.arraycopy(array, left, leftArray, 0, n1);
    System.arraycopy(array, middle + 1, rightArray, 0, n2);

    // 合并临时数组到原数组
    int i = 0, j = 0;
    int k = left;
    while (i < n1 && j < n2) {
        if (leftArray[i] <= rightArray[j]) {
            array[k++] = leftArray[i++];
        } else {
            array[k++] = rightArray[j++];
        }
    }

    // 拷贝剩余的元素
    while (i < n1) {
        array[k++] = leftArray[i++];
    }
    while (j < n2) {
        array[k++] = rightArray[j++];
    }
}
归并排序
归并排序

计数排序

计数排序是一种非比较排序，又称为鸽巢原理，是对哈希直接定址法的变形应用。在排序数组中找到最大最小的数据，算出对应范围并创建对应长度个数组用来计数，遍历排序数组，根据每个出现的数据值与计数数组下标构建的相对映射关系进行统计数据出现次数，最后将统计的出的数据按次序赋值给原数组。

// 计数排序函数
public static void countingSort(int[] array) {
    if (array.length == 0) return;

    // 在单次遍历中找到最大值和最小值
    int max = array[0];
    int min = array[0];
    for (int num : array) {
        if (num > max) {
            max = num;
        }
        if (num < min) {
            min = num;
        }
    }

    // 创建计数数组
    int[] count = new int[max - min + 1];

    // 统计每个元素的出现次数
    for (int num : array) {
        count[num - min]++;
    }

    // 根据计数数组填充排序后的结果数组
    int index = 0;
    for (int i = 0; i < count.length; i++) {
        while (count[i] > 0) {
            array[index++] = i + min;
            count[i]--;
        }
    }
}
计数排序

桶排序

桶排序（Bucket Sort）是一种基于分布的排序算法，适用于数据分布比较均匀的情况。它将数据分到若干个桶中，然后对每个桶内的数据进行排序，最后将桶中的数据合并。

 // 桶排序函数
public static void bucketSort(int[] array) {
    if (array.length == 0) return;

    // 1. 找到数据范围
    int min = array[0];
    int max = array[0];
    for (int num : array) {
        if (num < min) min = num;
        if (num > max) max = num;
    }

    // 2. 创建桶
    int bucketCount = (max - min) / array.length + 1;
    List<Integer>[] buckets = new ArrayList[bucketCount];
    for (int i = 0; i < bucketCount; i++) {
        buckets[i] = new ArrayList<>();
    }

    // 3. 将数据分配到桶中
    for (int num : array) {
        int bucketIndex = (num - min) / array.length;
        buckets[bucketIndex].add(num);
    }

    // 4. 对每个桶内的数据进行排序
    for (List<Integer> bucket : buckets) {
        Collections.sort(bucket);
    }

    // 5. 合并桶中的数据
    int index = 0;
    for (List<Integer> bucket : buckets) {
        for (int num : bucket) {
            array[index++] = num;
        }
    }
}

性能比较

性能比较

参考链接：https://www.nowcoder.com/discuss/353159614696988672

EOF