文件名称：属于不稳定排序-arcgis中可达性的实现
文件大小：3.89MB
文件格式：PDF
更新时间：2024-07-16 14:45:46
牛客网 面试题 测试
均排序完毕。他的时间复杂度是 O（n^2）,空间复杂度是 O（1）属于不稳定排序 4、shell 排序，是插入排序的升级版，属于不稳定排序，希尔排序通过将比较的全部元素 分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。 然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步， 需排序的数据几乎是已排好的了（此时插入排序较快）。 假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为 O(n^2)的排 序（冒泡排序或直接插入排序），可能会进行 n次的比较和交换才能将该数据移至正确位置。而 希尔排序会用较大的步长移动数据，所以小数据只需进行少数比较和交换即可到正确位置。希尔 排序的时间复杂度根据步长序列的不同而不同，空间复杂度 O（1） 5、归并排序，归并排序的实现分为递归实现与非递归(迭代)实现。属于稳定排序，递归实 现的归并排序是算法设计中分治策略的典型应用，我们将一个大问题分割成小问题分别解决，然 后用所有小问题的答案来解决整个大问题。非递归(迭代)实现的归并排序首先进行是两两归并， 然后四四归并，然后是八八归并，一直下去直到归并了整个数组。他的时间复杂度是 O（nlogn） 空间复杂度是 O（n） 6、堆排序，其实现原理为首先将数组构造成一个最大/最小堆，将堆顶元素和堆尾元素互换， 调出堆顶元素，重新构造堆，重复步骤直至堆中元素都被调出。堆排序的时间复杂度为 O（nlogn） 空间复杂度为 O（1），属于不稳定排序。 7、快速排序，快排使用分治策略，首先从序列中挑出一个元素作为基准，然后把比基准小 的元素放在一边，把比基准大的元素放在另一边，重复这个步骤，直至子序列的大小是 0/1.快 排的时间复杂度是 O（nlogn）空间复杂度是 O（logn）属于不稳定算法，对于快排的基准元素选