当前位置：首页 > news >正文

【归纳总结】常见排序算法及其实现：直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快排、归并排序

news 来源：原创 2024/9/19 9:22:11

思维导图：

一、插入排序

1.直接插入排序：

a:基本思想：

b:基本步骤：

c:复杂度分析

d:Java代码实现：

2.希尔排序（缩小增量排序）

a:基本思想：

c:基本步骤

c:复杂度分析

d:Java代码实现：

二、选择排序

1.选择排序

a:基本思想：

b:基本步骤:

c:复杂度分析:

d:Java代码实现:

2.堆排序

a:基本思想:

b:基本步骤:

c:复杂度分析:

d:Java代码实现:

三、交换排序

1.冒泡排序

a:基本思想：

b:基本步骤:

c:复杂度分析:

d:Java代码实现:

2.快速排序

a:基本思想：

b:基本步骤:

c:代码的主要框架

d:常见分区方法：

(1).Hoare版

(2).挖坑法

c:复杂度分析:

四、归并排序

a:基本思想:

b:基本步骤:

c:复杂度分析:

d:Java代码实现:

五、复杂度总结和性质对比（精华）

一、插入排序

1.直接插入排序：

每摸到一张新的牌（假设这个牌是10），我们就找一个位置插入，这个位置的前面一张牌应是<=10，后面一张牌比10大。

a:基本思想：

对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常在原数组上进行操作，因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为新元素提供插入空间。

b:基本步骤：

初始状态：假设第一个元素是有序的。
从第一个未排序元素开始，依次从后向前扫描已排序的部分。
依次比较：将未排序元素与已排序元素进行比较，找到其在已排序部分中的合适位置。
插入元素：将该未排序元素插入到合适位置。
重复：对所有未排序元素重复步骤 2 到 4，直到所有元素都被排序。

c:复杂度分析

时间复杂度：

最优时间复杂度：O(n)（数组已经是有序的情况）
最坏时间复杂度：O(n²)（数组是逆序的情况）
平均时间复杂度：O(n²)

空间复杂度：O(1)（因为是在原数组上进进行位置的挪动，只需要额外定义几个局部变量）

稳定性：稳定排序。

d:Java代码实现：

public class InsertSort {//升序排序public static void insertionSort(int[] array) {int n = array.length;//第一个元素默认有序，因此从第二个元素开始for (int i = 1; i < n; i++) {int key = array[i];int j = i - 1;// 将大于key的元素向后移动while (j >= 0 && array[j] > key ) {array[j + 1] = array[j];j--;}//j停下的地方，array[j]<=keyarray[j + 1] = key; // 插入key}}public static void main(String[] args) {int[] array = {12, 11, 13, 5, 6};insertionSort(array);System.out.println("Sorted array:");for (int num : array) {System.out.print(num + " ");}}}

2.希尔排序（缩小增量排序）

希尔是直接插入排序的优化。根据上面的学习我们知道，直接插入排序：O(n)（数组已经是有序的情况），O(n²)（数组是逆序的情况），两种情况相差很大。若数组完全逆序，所需的时间成本太大。因此我们要在直接插入排序前对数组做些调整。因此希尔排序可以理解为先做一些操作，让数组较为有序，再最后来一次直接插入排序。

a:基本思想：

它通过对间隔较大的元素进行比较和交换，逐渐减少间隔，最终实现数组的整体有序。

前面的预排序本质上也是在做插入排序。只不过只是在相差间隔一样的元素之间做。最后一趟gap=1，就是真正的直接插入排序。

c:基本步骤

选择增量序列：

选择一个初始增量 gap（通常为数组长度的一半）。
每次循环将增量缩小（通常是减半），直到 gap 等于 1。

分组排序：

按照当前的增量 gap，将数组元素分为多个子序列，每个子序列由间隔为 gap 的元素组成。
对每个子序列分别进行插入排序。

缩小增量：

将 gap 缩小到原来的某个比例（通常是减半，如 gap = gap / 2）。
重复分组和插入排序，直到 gap 等于 1 时进行最后一次插入排序。

完成排序：

当 gap 缩小到 1 时，进行最后一次插入排序，确保数组最终有序。

c:复杂度分析

1.时间复杂度：

希尔排序的时间复杂度取决于增量序列的选择，不同的增量序列会影响算法的性能。希尔排序的时间复杂度是一个较难精确分析的问题。

一般情况下：希尔排序比简单排序算法（如插入排序、选择排序）的性能要好得多，特别是在中小规模数据集上。

时间复杂度范围：希尔排序的时间复杂度取决于增量序列和数组初始状态，通常介于 O(n^1.3)~ O(n^2)之间。

实际表现：由于实际应用中的数据集通常不会是完全随机的，希尔排序在许多情况下能提供接近 O(nlog⁡n) 的性能，特别是在使用优化增量序列时。

空间复杂度：希尔排序是一种原地排序算法，空间复杂度为 O(1)。

稳定性：不稳定排序

d:Java代码实现：

 // 希尔排序方法public static void shellSort(int[] array) {int n = array.length;// 初始增量为数组长度的一半for (int gap = n / 2; gap > 0; gap /= 2) {// 对每个子序列进行插入排序for (int i = gap; i < n; i++) {int temp = array[i];int j;// 在子序列中找到合适的位置进行插入for (j = i; j - gap >= 0 && array[j - gap] > temp; j -= gap) {array[j] = array[j - gap];}// 插入元素array[j] = temp;}}}

二、选择排序

1.选择排序

a:基本思想：

每一轮从未排序的部分中选出最小（或最大）的元素，将其与未排序部分的第一个元素交换位置，逐步扩大已排序部分的范围，直到整个数组有序。

b:基本步骤:

1.初始化已排序部分和未排序部分：已排序部分初始为空，未排序部分为整个数组。

2.选择最小（或最大）元素：从未排序部分中选择最小（或最大）的元素。

3.交换位置：将选中的最小（或最大）元素与未排序部分的第一个元素交换位置。

4.更新范围：将该元素归入已排序部分，缩小未排序部分的范围。

5.重复：重复步骤 2 到 4，直到未排序部分为空

c:复杂度分析:

时间复杂度: 选择排序的时间复杂度为 O(n^2)。因为每次找最大的元素时，都要遍历完所有的未排序序列，才能知道哪个是最大的。即当数组已经有序时，其时间复杂度依然很高。
空间复杂度: 选择排序的空间复杂度为 O(1)。
稳定性: 选择排序是不稳定的，因为在交换时可能会破坏相同元素的相对顺序。

d:Java代码实现:

public static void selectSort(int[] array) {int n = array.length;for (int i = 0; i < n - 1; i++) {// 假设当前元素是最小的int minIndex = i;// 找到剩余部分中的最小元素for (int j = i + 1; j < n; j++) {if (array[j] < array[minIndex]) {minIndex = j;}}// 将最小元素与当前元素交换if (minIndex != i) {int temp = array[i];array[i] = array[minIndex];array[minIndex] = temp;}}}

2.堆排序

对堆还不清楚的小伙伴，墙裂建议看这篇博客，超详细~
【数据结构】一篇讲清楚什么是堆? 带图食用超详细~https://blog.csdn.net/weixin_71246590/article/details/141396025?spm=1001.2014.3001.5501

a:基本思想:

堆排序的基本思想是利用堆这种完全二叉树的特性进行排序。具体来说，假设要升序排序，构建一个最大堆（获取最大值），然后逐步将堆顶元素的最大值与堆的最后一个元素交换，并缩小堆的范围，使得最大值可以被固定在数组后面，并在新的堆中进行堆化调整，直到整个堆排序完成。

b:基本步骤:

1.构建初始堆：将待排序数组构建成一个最大堆（或最小堆），这一步的复杂度为 O(n)。

2.堆顶元素与最后一个元素交换：将堆顶元素（当前最大值或最小值）与堆的最后一个元素交换位置，此时堆的大小减少 1。

3.重新调整堆：对交换后的堆顶元素进行向下调整，使其重新成为最大堆或最小堆。调整的时间复杂度为 O(log n)。

4.重复步骤 2 和 3：继续重复上述操作，直到堆的大小为 1，此时数组已经有序。

c:复杂度分析:

时间复杂度：O(n log n)

分析：建堆时间复杂度为：O(n)，
向下调整：O(logn),，则排序过程中需要对n-1个节点向下调整：O（nlog），
因此:时间复杂度：O(n)+O(nlogn)=O(nlogn)

空间复杂度：O(1)（堆排序是一种原地排序算法，不需要额外的存储空间）

稳定性：不稳定（因为在堆化过程中，可能会改变相同元素的相对位置）

d:Java代码实现:

//升序 - 建大堆
public class HeapSort {//向下调整public void heapifyDonw(int[] heap, int i, int size) {int left = 2 * i + 1;int right = 2 * i + 2;int largest = i;//找三者中最大下标if (left < size && heap[left] > heap[largest]) {largest = left;}if (right < size && heap[right] > heap[largest]) {largest = right;}if (i != largest) {//交换元素swap(heap, largest, i);//继续向下调整heapifyDonw(heap, largest, size);}}public void heapSort(int[] heap) {//初始化堆为大根堆int size = heap.length;//从最后一个叶子结点开始向下调整for (int i = size / 2 - 1; i >= 0; i--) {heapifyDonw(heap, i, size);}//开始排序：逐步交换堆顶元素到末尾，并缩小堆范围for (int i = size - 1; i > 0; i--) {swap(heap, 0, i);heapifyDonw(heap, 0, i);}}public void swap(int[] heap, int i, int j) {if (i == j) {return;}int temp = heap[i];heap[i] = heap[j];heap[j] = temp;}public static void main(String[] args) {int[] arr = {5, 4, 3, 2, 1};HeapSort t1 = new HeapSort();t1.heapSort(arr);for (int num : arr) {System.out.print(num + " ");}}
}

三、交换排序

1.冒泡排序

冒泡排序之所以被称为“冒泡排序”，是因为其排序过程中，较大的元素像气泡一样逐步向上“冒”到数组的末尾。

以下讲解，以升序排序为主，降序排序思想类似。

a:基本思想：

冒泡排序是一种简单且直观的排序算法，主要通过多次遍历待排序的数组，对相邻的元素进行比较并交换，使得较大的元素逐渐向数组的末尾“冒泡”，并固定住末尾，最终使整个数组有序。

b:基本步骤:

1. 逐步冒泡的过程

比较和交换：从数组的起始位置开始，逐一比较相邻的两个元素。如果前一个元素比后一个元素大，则交换这两个元素的位置，使较大的元素向后移动。

每次遍历的效果：每次遍历后，当前未排序部分的最大元素会被“冒”到该部分的最后一个位置。相当于每次遍历都将当前的最大值放在了它在最终排序中正确的位置。

2. 逐步减少的未排序部分

在第一次完整遍历之后，最大的元素已经移动到了数组的末尾，所以在接下来的遍历中，不再需要考虑这个元素。

这样，每次遍历都会将一个元素放在正确的位置，并缩小未排序部分的范围，直到数组完全有序。

3. 提前终止条件

在某次遍历中，如果没有发生任何交换，说明数组已经是有序的，可以提前终止排序。这是冒泡排序的一种优化，可以避免不必要的比较操作。

c:复杂度分析:

时间复杂度：

最优情况：O(n) （数组已经有序时，仅需一次遍历即可完成排序）
最坏情况：O(n²) （数组是逆序的，需要进行 n-1 次遍历，每次需要进行 n-i 次比较）
平均情况：O(n²)

空间复杂度：O(1) （只需要常数级的额外空间）

稳定性：冒泡排序是稳定的排序算法，因为在交换过程中不会改变相等元素的相对顺序。

d:Java代码实现:

public class BubbleSort {//冒泡排序（升序）public static void bubbleSort(int[] arr){int n=arr.length;boolean isSwap;//对于n个元素，只需要把n-1个冒到后面，剩下的自然有序for(int i=0;i<n-1;i++){isSwap=false;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;isSwap=true;}}if (!isSwap){return;}}}public static void main(String[] args) {int[] arr = {5, 3, 8, 4, 2};bubbleSort(arr);// 输出排序后的数组for (int num : arr) {System.out.print(num + " ");}}
}

2.快速排序

a:基本思想：

任取待排序元素序列中的某元素作为基准值，将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，此时基准值定在中间。然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

b:基本步骤:

1.选择基准（Pivot）: 从数组中选择一个元素作为基准，一般可以选择第一个元素、最后一个元素或中间元素。

2.分区（Partion）: 将数组划分为两部分，使得左侧部分的所有元素都小于等于基准值，而右侧部分的所有元素都大于基准值。

3.递归排序: 对划分后的两个子数组分别递归地进行快速排序，直到子数组的长度为0或1，即不可再分。

c:代码的主要框架

1.递归版

void QuickSort(int[] array, int left, int right) {if (left < right) {//按照基准值对array数组的[left,right]区间的元素进行划分int div = partition(array, left, right);//划分成功后以div为便捷形成了左右两部分[left,div)和[div+1,right]QuickSort(array, left, div - 1);QuickSort(array, div + 1, right);}
}

2.非递归版

// 快速排序非递归版框架void quickSortNonR(int[] arr, int left, int right) {if (left >= right) {return;}Stack<Integer> stack = new Stack<>();stack.push(left);stack.push(right);while (!stack.empty()) {right = stack.pop();left = stack.pop();if (left < right) {int div = partition(arr, left, right);stack.push(left);stack.push(div - 1);stack.push(div + 1);stack.push(right);}}}

partition分区方法（将区间按照基准值划分为左右两半部分）是其中的核心部分，将重点介绍。

d:常见分区方法：

(1).Hoare版

public static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}// 1. Hoare版partionpublic static int HoarePartition(int[] array, int left, int right) {//初始化指针int i = left;  //i:左指针int j = right; //j:右指针//pivot:选择 array[left] 作为基准值int pivot = array[left];while (i < j) {//右指针移动:从右向左移动 j，寻找第一个小于 pivot 的元素。while (i < j && array[j] >= pivot) {j--;}//左指针移动:从左向右移动 i，寻找第一个大于 pivot 的元素。while (i < j && array[i] <= pivot) {i++;}//每次交换后，i 左边的元素都会小于等于基准值，j 右边的元素都会大于等于基准值。//继续上述过程，直到 i 和 j 相遇（即 i >= j）。if (i < j) {swap(array, i, j);}}//当 i 和 j 相遇后，交换 array[i] 和 array[left]，将基准值放在最终的位置上。// 此时，基准值左边的元素都小于等于它，右边的元素都大于等于它。swap(array, i, left);return i;}

思路讲解：

宏观上来说：就是从后面找比基准小的，从前面找比基准大的值。而这些值都是不符合规则的值。因为本来应该是比基准小的值在前面，比基准大的值在后面，基准值夹在中间。就把这两个不符合规则的值交换。让序列相对符合规则。

代码细节上来讲：当j脚底下的元素大于等于基准时，它就会往左移，它想找第一个小于基准的。当i脚底下的元素小于等于基准时，它就会往右移，它想找第一个大于基准的。假设i、j都找到合理的值了，此时交换它们的元素的位置，就可以让元素相对有序一点了（大于基准的往后靠，小于基准的往前靠）。

要注意到，代码是让右指针（j）先找？为什么？

这与我们基准选择的值有关，我们基准选值选了最左边的值。这样设计是为了，当i==j时，array[i] <= array[left]恒成立。

原因：代码设计是让右指针j先走，而j会马不停蹄的一直走，直到找到array[i]<array[left]，或者一直找不到，此时走到左边尽头，array[i]==array[left]。也就是说，咱们的array[i]一旦动起来，就会产生array[i] <= array[left]这种情况，所以当i、j相遇时，array[i] <= array[left]恒成立。

为什么最后swap(array, i, left)？

相遇点的性质：当i、j相遇时，相遇点右边的土地，都是j走过的，都是确保array[j]>=array[left]，相遇点的左边，都是i走过的土地，都是确保array[j]<=array[left]的。在这种情况下，交换array[left]和array[i]，基准值被放到合适的位置，结束此次的分区，返回交换后所在的下标i。

(2).挖坑法

 // 2.挖坑法partionprivate static int HolePartition(int[] array, int left, int right) {int i = left;               // 左指针初始化为数组的起始位置int j = right;              // 右指针初始化为数组的结束位置int pivot = array[left];    // 选择左边第一个元素作为基准值，并将其视为“坑”while (i < j) {   // 只要 i 和 j 不相遇// 右指针左移，寻找第一个小于 pivot 的元素while (i < j && array[j] >= pivot) {j--;}// 将右边找到的小于 pivot 的元素填入左边的坑array[i] = array[j];// 左指针右移，寻找第一个大于 pivot 的元素while (i < j && array[i] <= pivot) {i++;}// 将左边找到的大于 pivot 的元素填入右边的坑array[j] = array[i];}// 将基准值填入最终位置array[i] = pivot;// 返回基准值的位置return i;}

有了hoare分区法做铺垫，挖坑法理解起来容易很多。个人觉得比hoare法容易理解。

思路讲解：

先把基准值记录下来（挖空首元素，形成了坑），下面就开始酣畅淋漓的交换了，j指针找比基准值小的（挖走），填在i的坑，i找比基准值大的（挖走），填在j指针的坑。此时重复上述挖填过程。

当 i 和 j 相遇时脚底有一个坑，就用基准值填，因为其：

左侧的元素（从左指针 i 的起始位置到 i 相遇点）已经经过了检查，确保这些元素要么小于等于基准值，要么是在左边找到的比基准值大的元素。

右侧的元素（从右指针 j 的起始位置到 j 相遇点）已经经过了检查，确保这些元素要么大于等于基准值，要么是在右边找到的比基准值小的元素。

c:复杂度分析:

时间复杂度分析：

最佳情况： O(nlog⁡n)

在最佳情况下，每次分割都能将数组均匀地分成两部分，即每次选择的基准值（pivot）将数组分成两个大致相等的部分。对于大小为 n 的数组，最佳情况的递归树的深度为 logn，每一层的工作量为O(n)。因此，时间复杂度: O(nlog⁡n)。

最坏情况：O(n^2)

在最坏情况下，每次选择的基准值都位于数组的极端位置（如最小或最大），导致一部分子数组包含 n−1个元素，而另一个子数组为空。这种情况使得递归树的深度为 n，每层的工作量为 O(n)。因此，时间复杂度: O(n^2)。 ps：最坏情况通常发生在数组已经是有序或者每次选择的基准值是数组的最小或最大元素。为了减少这种情况的发生，可以使用随机选择基准值或三数取中法）来改进基准值选择。

平均情况：O(nlog⁡n)

在平均情况下，假设基准值能够将数组大致均匀地分割成两个部分。递归树的深度为 log⁡n，每层的工作量为 O(n)。

空间复杂度分析：

快速排序的空间复杂度主要取决于递归调用的深度。最坏情况下，递归树的深度为 n，因此空间复杂度为 O(n)。然而，在平均情况下，递归树的深度为 log⁡n，因此空间复杂度为 O(log⁡n)。

稳定性分析：不稳定

元素交换破坏了相对顺序： 当数组中存在与基准元素相等的元素时，这些元素可能会在分区过程中被移动到数组的另一部分。

总结：

最佳情况时间复杂度: O(nlog⁡n)
最坏情况时间复杂度: O(n^2)
平均情况时间复杂度: O(nlog⁡n)
空间复杂度: O(log⁡n)（平均情况）; O(n)（最坏情况）
通过选择合适的基准值策略和优化递归深度，可以在实践中将快速排序的性能提高到接近其平均情况的时间复杂度。

四、归并排序

a:基本思想:

归并排序是一种分治算法，它的基本思想是将待排序数组分成两个子数组，对每个子数组递归地进行排序，然后将两个已排序的子数组合并成一个最终的排序数组。

b:基本步骤:

分割（Divide）： 将数组从中间分成两部分，直到每部分只剩下一个元素。
递归（Recursion）： 对每个子数组递归地应用归并排序。
合并（Merge）： 合并两个已排序的子数组，生成一个排序后的数组。

c:复杂度分析:

时间复杂度： O(nlog⁡n)。
分析：
1.分解过程：对于一个大小为 n的数组，递归分解的深度为 log⁡n。每次将数组大小减半，直到数组大小为 1。
2.合并过程：每一层的合并操作涉及到处理整个数组，因此每一层的合并时间复杂度是 O(n)。
3.综合考虑：总的时间复杂度为每层的时间复杂度O(n)乘以层数log⁡n。

空间复杂度： 归并排序需要额外的存储空间来存放合并后的数组，空间复杂度为 O(n)。
稳定性：稳定排序

d:Java代码实现:

public class MergeSort {//归并排序方法入口public static void mergeSort(int[] array) {if (array == null || array.length <= 1) {return;}mergeSort(array, 0, array.length - 1);}private static void mergeSort(int[] array, int left, int right) {if (left < right) {int mid = left + (right - left) / 2; // 这里为什么不用mid=(left+right)/2 ? 一会讲mergeSort(array, left, mid);//归mergeSort(array, mid + 1, right);//归merge(array, left, mid, right);//并}}//将两个有序数组合并:是大家很熟悉的顺序表oj题的变种~~private static void merge(int[] array, int left, int mid, int right) {int[] temp = new int[right - left + 1];  // 创建临时数组 temp，大小为当前待排序的元素int i = left, j = mid + 1, k = 0; // 初始化i、j 分别指向两个子数组的起始位置，k 为 temp 数组的索引// 合并两个子数组，将较小的元素依次放入 temp 数组while (i <= mid && j <= right) {temp[k++] = (array[i] <= array[j]) ? array[i++] : array[j++];}// 如果左边子数组还有剩余元素，依次将其放入 temp 数组while (i <= mid) {temp[k++] = array[i++];}// 如果右边子数组还有剩余元素，依次将其放入 temp 数组while (j <= right) {temp[k++] = array[j++];}// 将临时数组 temp 中的元素复制回原数组 array 的相应位置System.arraycopy(temp, 0, array, left, temp.length);}public static void main(String[] args) {int[] array = {38, 27, 43, 3, 9, 82, 10};mergeSort(array);for (int num : array) {System.out.print(num + " ");}}
}

整数溢出问题：