这篇文章给大家聊聊关于选择排序的时间复杂度，以及选择排序法举例说明对应的知识点，希望对各位有所帮助，不要忘了收藏本站哦。
本文目录
一、选择排序时间复杂度
1、选择排序时间复杂度：选择排序的基本思想是对待排序的记录序列进行n-1遍的处理，第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样，经过i遍处理之后，前i个记录的位置已经是正确的了。
2、（1）看0～N-1；看N次；（之一个与之一个比较，选择最小值；第二个和最小值比较，以此类推）比较N次，交换一次；结果：最小的放到之一位上；
3、（2）看1～N-1:看N-1次；比较N-1次；交换一次；结果；最小的放到第二位；
4、（3）以此类推直至最后一次，全部比较完成；
二、直接选择排序算法在更好情况下的时间复杂度为多少
1、关键字比较次数永远是n(n-1)/2，记录移动次数最多为3(n-1)，最少0次，前者起主导作用，因此实际上时间复杂度还是O(n^2)。
2、在直接选择排序中，共需要进行n-1次选择和交换，每次选择需要进行 n-i次比较(1<=i<=n-1),而每次交换最多需要3次移动，因此，总的比较次数C=(n*n- n)/2,总的移动次数 3(n-1).由此可知，直接选择排序的时间复杂度为 O(n2)。
3、直接选择排序的基本思想是：之一次从R[0]~R[n-1]中选取最小值，与R[0]交换，第二次从R[1]~R[n-1]中选取最小值，与R[1]交换，....，第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换，.....，第n-1次从R[n-2]~R[n-1]中选取最小值。
4、与R[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。当记录占用字节数较多时，通常比直接 *** 排序的执行速度快些。由于在直接选择排序中存在着不相邻元素之间的互换，因此，直接选择排序是一种不稳定的排序 *** 。
5、参考资料来源：百度百科-直接选择排序
三、直接选择排序的时间复杂度是多少
1、关键字比较次数永远是n(n-1)/2，记录移动次数最多为3(n-1)，最少0次，前者起主导作用，因此实际上时间复杂度还是O(n^2)。
2、在直接选择排序中，共需要进行n-1次选择和交换，每次选择需要进行 n-i次比较(1<=i<=n-1),而每次交换最多需要3次移动，因此，总的比较次数C=(n*n- n)/2,总的移动次数 3(n-1).由此可知，直接选择排序的时间复杂度为 O(n2)。
3、直接选择排序的基本思想是：之一次从R[0]~R[n-1]中选取最小值，与R[0]交换，第二次从R[1]~R[n-1]中选取最小值，与R[1]交换，....，第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换，.....，第n-1次从R[n-2]~R[n-1]中选取最小值。
4、与R[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。当记录占用字节数较多时，通常比直接 *** 排序的执行速度快些。由于在直接选择排序中存在着不相邻元素之间的互换，因此，直接选择排序是一种不稳定的排序 *** 。
5、参考资料来源：百度百科-直接选择排序
四、常见排序算法以及对应的时间复杂度和空间复杂度
排序：将杂乱无章的数据，按照一定的 *** 进行排列的过程叫做排序。
排序大的分类可分为内排序和外排序，不需要访问外存就能进行排序的叫做内排序。
排序也可以分为稳定排序和不稳定排序
稳定排序：假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字，在用某种排序法排序后，若这些相同关键字的元素的相对次序仍然不变，则这种排序 *** 是稳定的。即；若 a[i]=a[j], a[i]在 a[j]之前，经过排序后 a[i]依然在 a[j]之前。冒泡排序、直接 *** 排序、二分 *** 排序、归并排序，基数排序都是稳定排序。
不稳定排序：直接选择排序、堆排序、快速排序、希尔排序，猴子排序。
以升序为例，比较相邻的元素，如果之一个比第二个大，则交换他们两个。如果两个元素一样大，则继续比较下一对。所以冒泡排序是一种稳定排序。
选择一个基准元素,通常选择之一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的 *** 递归地排序划分的两部分。快速排序是不稳定排序。
将序列分为两个部分{{有序序列},{无序}}，每次处理就是将无序数列的之一个元素与有序数列的元素从后往前逐个进行比较，找出 *** 位置，将该元素 *** 到有序数列的合适位置中。如果碰到相等的元素，就会把它 *** 到想等元素后面，顺序不会改变，所以直接 *** 排序是稳定排序。
在直接 *** 排序的基础上，对有序序列进行划分。例如：序列为{{a[0]......a[i-1]},a[i]}其中{a[0]......a[i-1]}为有序序列，取 a[(i-1)/2]，将其与 a[i]比较，即可确定 a[i]的范围(a[0]...a[(i-1)/2]或者 a[(i-1)/2]...a[i-1]),然后继续在已确定的范围内进行二分。范围依次缩小为： 1/2、1/4、1/8、1/16......可快速确定a[i]应该 *** 的位置。二分 *** 排序也是稳定排序。
将整个序列分割成若干个小的子序列，每个子序列内分别进行 *** 排序。一般情况下步长取n/2。直到最后一次步长为1，即所有元素在一个组中进行排序。由于希尔排序是先将整个序列划分为多个子序列进行排序，相同的元素顺序在这个过程中顺序可能会被打乱，所以希尔排序是不稳定排序。
从待排序的数据元素中，选出最小或更大的元素与序列之一个数交换。直到所有数据排完。直接选择排序是不稳定排序。例如：{3，3，1}，之一次排序就将1和之一个3交换，想等元素的顺序改变了。
以n=10的一个数组49, 38, 65, 97, 26, 13, 27, 49, 55, 4为例
堆排序是一种树形选择排序，是对直接选择排序的有效改进。
更大堆:每个节点的值都大于等于它的孩子节点。
最小堆:每个节点的值都小于等于它的孩子节点。
更大堆第0个数据是更大数，最小堆第0个数据是最小数。
归并排序是建立在归并 *** 作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
如何将两个有序序列合并？(升序)
{a[0]......a[i-1]},{b[0]......b[j-1]}
若 b[0]<a[0]，取 b[0]放入数组 c中，然后继续比较数组 a和 b中的之一个元素，直到数组 a和 b中最后一对元素比较完成。
将数组分成二组 a, b如果这二组组内的数据都是有序的，那么就可以按照上述 *** 对这二组数据进行排序。如果这二组数据是无序的？
可以将 a, b组各自再分成二组。递归 *** 作，直到每个小组只有一个数据，每个小组只有一个元素所以我们可以认为它已经是有序序列，然后进行合并。
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。从更低位起从0-9依次扫描序列，一边扫描一边将扫描到的数据加到新的序列中，得到一个序列。然后比较高一位，重复上述 *** 作，直到更高位排序完成。数列就变成一个有序序列。基数排序是稳定排序。
无限猴子定理:指一只猴子随机在打字机键盘上按键，最后必然可以打出法国国家图书馆的每本图书。
时间复杂度更低1次，更高可执行到世界的尽头。。。
五、排序算法的时间复杂度如何
1、排序算法的时间复杂度是若文件的初始状态是正序的，一趟扫描即可完成排序。
2、比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
3、对于一个算法，若其匹配T(n)= o(n)，则其时间复杂度为次线 *** 时间（sub-linear time或sublinear time）。实际上除了匹配以上定义的算法，其他一些算法也拥有次线 *** 时间的时间复杂度。例如有O(n)葛罗佛搜索算法。
4、常见的非合次线 *** 时间算法都采用了诸如平行处理（就像NC1 *** trix行列式计算那样）、非古典处理（如同葛罗佛搜索那样），又或者选择 *** 地对有保证的输入结构作出假设（如幂对数时间的二分搜索）。
5、不过，一些情况，例如在头 log(n)比特中每个字符串有一个比特作为索引的字符串组就可能依赖于输入的每个比特，但又匹配次线 *** 时间的条件。
6、“次线 *** 时间算法”通常指那些不匹配前一段的描述的算法。它们通常运行于传统计算机架构系列并且不容许任何对输入的事先假设。但是它们可以是随机化算法，而且必须是真随机算法除了特殊情况。
好了，本文到此结束，如果可以帮助到大家，还望关注本站哦！
