内部排序和外部排序以及常见算法和时间复杂度
内部排序和外部排序是数据排序的两种基本类型，它们的主要区别在于数据在排序过程中是否全部存储在内存中。
内部排序
内部排序是指待排序列（或文件）的数据记录完全存放在内存中所进行的排序过程。也就是说，整个排序过程不需要访问外部存储器（如硬盘）便能完成。内部排序算法有多种，包括但不限于：
- 冒泡排序：通过重复遍历要排序的数列，比较相邻元素的值，若发现顺序错误则交换它们的位置，直到整个数列有序。
- 插入排序：将未排序的数据逐个插入到已排序的序列中的适当位置，从而得到一个新的、记录数增1的有序表。
- 选择排序：每次从待排序的元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的元素排完。
- 归并排序：采用分治法策略，将待排序的数组分成两个子序列，分别排序后再合并成一个最终的排序序列。
- 快速排序：通过选择一个基准元素，将数组分成两个子数组，一个子数组的元素都比基准元素小，另一个子数组的元素都比基准元素大，然后递归地对这两个子数组进行排序。
- 希尔排序：是插入排序的一种改进版本，通过比较相距一定间隔的元素来工作，然后逐渐缩小间隔，直到整个序列有序。
- 堆排序：利用堆这种数据结构所设计的一种排序算法，堆是一个近似完全二叉树的结构，并同时满足堆积的性质。
内部排序算法的选择通常取决于数据的规模、数据的初始状态以及所需的稳定性和时间复杂度等因素。
外部排序
外部排序则用于数据量过大，无法全部装入内存，需要借助外部存储（如硬盘）的排序过程。外部排序算法主要包括：
- 归并排序的外部版本：将大文件分成若干个小文件，每个小文件都能完全装入内存，然后在内存中分别进行排序，最后将排序好的小文件合并成一个有序的大文件。
- 多路平衡归并：是归并排序外部版本的一种优化，通过同时归并多个有序的小文件来减少归并的次数。
- 败者树：在外部排序中，败者树常用于实现多路归并，它是一种特殊的二叉树结构，用于高效地找出多个元素中的最小值或最大值。
- 置换-选择排序：在外部排序中，置换-选择排序算法可用于将初始文件分为数量较少的长度不等的初始归并段，从而减少后续归并的次数。
外部排序算法的主要影响因素在于读写内存（或外部存储器）的次数，因为内存读写速度快，而外存读写速度慢，所以减少读写外存的次数可以显著提高外部排序的效率。
内部排序算法的时间复杂度
-
冒泡排序：
- 最好情况：O(n)（当数据已经有序时，通过优化可以减少比较和交换次数）
- 最坏情况：O(n^2)
- 平均情况：O(n^2)
-
插入排序：
- 最好情况：O(n)（当数据已经有序时，只需遍历一遍即可）
- 最坏情况：O(n^2)（当数据为逆序时，每次插入都需要比较和移动大量元素）
- 平均情况：O(n^2)
-
选择排序：
- 最好情况：O(n^2)（无论数据是否有序，都需要进行n-1轮选择）
- 最坏情况：O(n^2)
- 平均情况：O(n^2)
-
归并排序：
- 最好情况：O(n log n)
- 最坏情况：O(n log n)
- 平均情况：O(n log n)
-
快速排序：
- 最好情况：O(n log n)（当每次划分都平衡时）
- 最坏情况：O(n^2)（当每次划分都极不平衡时，如每次只划分出一个元素）
- 平均情况：O(n log n)（在实际应用中，通过随机选择基准元素或三数取中法等方法，可以接近平均情况）
-
希尔排序：
- 最好情况：O(n log^2 n)（取决于增量序列的选择）
- 最坏情况：O(n2)）
- 平均情况：通常认为是O(n log n)，但实际性能可能因增量序列的不同而有所差异
-
堆排序：
- 最好情况：O(n log n)
- 最坏情况：O(n log n)
- 平均情况：O(n log n)
外部排序算法的时间复杂度
外部排序算法的时间复杂度通常涉及多个阶段，包括初始划分、排序和归并等步骤。由于外部排序需要频繁地读写外部存储器，因此其时间复杂度通常较高，且受到多种因素的影响，如外部存储器的读写速度、内存大小等。
-
归并排序的外部版本：
- 时间复杂度主要取决于归并的次数和每次归并时的数据规模。在理想情况下，可以认为是O(n log n)，但实际情况可能因外部存储器的读写速度而有所差异。
-
多路平衡归并：
- 通过同时归并多个有序的小文件来减少归并的次数，从而可能降低时间复杂度。具体时间复杂度取决于多路归并的实现方式和外部存储器的性能。
-
败者树：
- 在外部排序中用于实现多路归并的一种数据结构。其时间复杂度通常与多路归并的时间复杂度相关，且受到外部存储器读写速度的影响。
-
置换-选择排序：
- 主要用于将初始文件分为数量较少的长度不等的初始归并段。其时间复杂度取决于初始划分的方式和后续归并的策略。
原文地址：https://blog.csdn.net/buwangchuxinking/article/details/143747568
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！