算法刷题记录：排序算法（包含冒泡排序，选择排序，插入排序，快速排序等）附上踩坑记录-摩杜云开发者社区

算法刷题记录：排序算法（包含冒泡排序，选择排序，插入排序，快速排序等）附上踩坑记录_数组

排序算法刷题笔记

本文介绍了常见的排序算法，并提供了解题思路和踩坑记录。通过学习这些排序算法，你将能够更好地理解它们的原理和实现方式，同时掌握在刷题过程中遇到的一些常见问题和解决方法。以下是各个排序算法的详细内容。

冒泡排序（Bubble Sort）

解题思路

冒泡排序是一种简单直观的排序算法。它的基本思想是通过相邻元素之间的比较和交换，将较大的元素逐渐"冒泡"到最后。

遍历数组，比较相邻元素的大小。
如果前一个元素大于后一个元素，交换它们的位置。
继续遍历数组，重复步骤1和步骤2，直到没有需要交换的元素为止。

踩坑记录

注意循环的次数，每一轮冒泡操作都会将当前未排序部分的最大元素放到末尾，因此外层循环需要执行n-1次，n为数组的长度。
内层循环的范围随着外层循环的进行而逐渐减小，因为每一轮冒泡操作都会确定一个最大元素的位置，所以内层循环的结束位置应为n-1-i，其中i为外层循环的迭代变量。

// 冒泡排序示例代码

public void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换元素
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

选择排序（Selection Sort）

解题思路

选择排序是一种简单直观的排序算法。它的基本思想是每一次从未排序的部分中选择最小的元素，将其放到已排序部分的末尾。

遍历数组，找到未排序部分的最小元素。
将最小元素与未排序部分的第一个元素交换位置，将其放到已排序部分的末尾。
继续遍历数组，重复步骤1和步骤2，直到所有元素都放到已排序部分。

踩坑记录

注意循环的次数，选择排序需要执行n-1次循环，n为数组的长度。
内层循环从当前位置的下一个元素开始，找到未排序部分的最小元素的索引。

// 选择排序示例代码

public 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;
            }
        }
        // 交换元素
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

当然！接下来我将继续介绍其他常见的排序算法的解题思路和踩坑记录。

插入排序（Insertion Sort）

解题思路

插入排序是一种简单直观的排序算法。它的基本思想是将未排序部分的元素逐个插入到已排序部分的合适位置。

从第二个元素开始，将其视为已排序部分。
将未排序部分的第一个元素与已排序部分的元素进行比较，找到合适的位置插入。
插入元素后，已排序部分扩大一位，未排序部分减小一位。
重复步骤2和步骤3，直到所有元素都插入到已排序部分。

踩坑记录

注意循环的起始位置，插入排序从第二个元素开始，因此外层循环的索引应从1开始。
在内层循环中，需要将当前元素与已排序部分的元素进行比较，并找到合适的位置插入。
插入元素时，需要将已排序部分中比当前元素大的元素向后移动，为当前元素腾出位置。

// 插入排序示例代码

public 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--;
        }
        arr[j + 1] = key;
    }
}

快速排序（Quick Sort）

解题思路

快速排序是一种高效的排序算法。它的基本思想是通过选择一个基准元素，将数组划分为两个子数组，其中一个子数组的所有元素都小于基准元素，另一个子数组的所有元素都大于基准元素。然后对这两个子数组分别进行快速排序。

选择一个基准元素。
将数组划分为两个子数组，一个子数组中的元素小于基准元素，另一个子数组中的元素大于基准元素。
对两个子数组分别进行快速排序，递归地应用上述步骤。
合并排序后的子数组，得到最终的排序结果。

踩坑记录

选择基准元素时，可以选择数组的第一个元素、最后一个元素或者任意一个元素作为基准。不同的选择可能会影响快速排序的性能。
在划分子数组时，需要将小于基准元素的元素放在基准元素的左边，大于基准元素的元素放在基准元素的右边。可以使用双指针法实现划分。
递归地应用快速排序时，需要注意结束条件，即子数组的长度小于等于1时无需继续排序。

// 快速排序示例代码

public void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
    }
}

private int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr, i, j);
        }
    }
    swap(arr, i + 1, high);
    return i + 1;
}

private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

当然！以下是更多排序算法的解题思路和踩坑记录。

归并排序（Merge Sort）

解题思路

归并排序是一种稳定的排序算法。它的基本思想是将数组分成两个子数组，分别对这两个子数组进行排序，然后合并两个有序子数组，得到最终的排序结果。

将数组递归地划分为两个子数组，直到每个子数组的长度为1。
对每个子数组进行排序，可以使用递归或迭代的方式。
合并两个有序子数组，得到一个更大的有序数组。可以使用双指针法实现合并。

踩坑记录

在合并两个有序子数组时，需要创建一个临时数组来保存合并后的结果。
合并过程中，可以使用两个指针分别指向两个子数组的起始位置，比较指针所指的元素，将较小的元素放入临时数组，并移动指针。
合并完成后，需要将临时数组中的元素复制回原数组的对应位置。

// 归并排序示例代码

public void mergeSort(int[] arr, int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2;
        mergeSort(arr, low, mid);
        mergeSort(arr, mid + 1, high);
        merge(arr, low, mid, high);
    }
}

private void merge(int[] arr, int low, int mid, int high) {
    int n1 = mid - low + 1;
    int n2 = high - mid;
    int[] leftArray = new int[n1];
    int[] rightArray = new int[n2];

    for (int i = 0; i < n1; i++) {
        leftArray[i] = arr[low + i];
    }
    for (int j = 0; j < n2; j++) {
        rightArray[j] = arr[mid + 1 + j];
    }

    int i = 0, j = 0, k = low;
    while (i < n1 && j < n2) {
        if (leftArray[i] <= rightArray[j]) {
            arr[k] = leftArray[i];
            i++;
        } else {
            arr[k] = rightArray[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = leftArray[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = rightArray[j];
        j++;
        k++;
    }
}

堆排序（Heap Sort）

解题思路

堆排序是一种原地的排序算法。它的基本思想是通过构建最大堆（或最小堆），将堆顶元素与最后一个元素交换，然后调整堆，重复这个过程，直到所有元素都有序。

将数组构建成一个最大堆（或最小堆）。
将堆顶元素与最后一个元素交换位置，将最大（或最小）元素放到已排序部分。
调整堆，使其满足堆的性质。
重复步骤2和步骤3，直到所有元素都有序。

踩坑记录

堆排序中使用的堆可以通过数组来表示，数组的索引与堆中的节点之间有一定的关系。
构建最大堆（或最小堆）的过程可以通过从最后一个非叶子节点开始，逐个向上调整节点的方式实现。
调整堆的过程可以通过比较节点与其子节点的大小，并根据需要交换节点的位置来实现。

// 堆排序示例代码

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

    // 构建最大堆
    for (int i = n / 2 - 1; i >=抱歉，我的回答中断了。以下是堆排序的完整示例代码：

```java
// 堆排序示例代码

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

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

    // 逐个将堆顶元素与最后一个元素交换，并调整堆
    for (int i = n - 1; i > 0; i--) {
        swap(arr, 0, i);
        heapify(arr, i, 0);
    }
}

private 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) {
        swap(arr, i, largest);
        heapify(arr, n, largest);
    }
}

private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

希望这些解题思路和踩坑记录对你有所帮助！如果你还有其他需要了解的排序算法或其他主题，请随时告诉我。