排序算法-冒泡、选择排序
冒泡排序(升序为例)
思路:
1. 从头开始比较每一对相临的元素,其后者比前者大则交换,直到一轮比较结束
2. 排除1中找到最大的元素,重复1的步骤
class BubbleSort { var array = [5, 7, 2, 8, 9, 4, 7, 3, 2] // 基本版本 func sort() { for end in (1 ..< array.count).reversed() { for begin in 1 ... end { if array[begin] < array[begin - 1] { let tmp = array[begin] array[begin] = array[begin - 1] array[begin - 1] = tmp } } } } // 如果在某一趟比较后,序列就变得完全有序,此时就没有必要再继续比较下去 func sort2() { for end in (1 ..< array.count).reversed() { var sorted = true for begin in 1 ... end { if array[begin] < array[begin - 1] { let tmp = array[begin] array[begin] = array[begin - 1] array[begin - 1] = tmp // 如果来到这里表明数列不是完全有序 sorted = false } } if sorted { break } } } // 如果数列在尾部已经有序(部分有序) func sort3() { for var end in (1 ..< array.count).reversed() { var endIndex = 1 for begin in 1 ... end { if array[begin] < array[begin - 1] { let tmp = array[begin] array[begin] = array[begin - 1] array[begin - 1] = tmp // 如果不到这里表明在上次比较后,begin后面就是全部有序 endIndex = begin } } end = endIndex } } }
* 最坏、平均时间复杂度:O(n^2),最好时间复杂度:O(n)
* 空间复杂度: O(1)
* 稳定性: 稳定
选择排序(升序为例)
思路:
1. 选择从第一个到倒数第二个与最后一个进行比较,大则交换放到最后
2. 重复第一步,与倒数第二个数比较
class SelectionSort { var array = [5, 7, 2, 8, 9, 4, 7, 3, 2] func sort() { for end in (1 ..< array.count).reversed() { var maxValueIndex = 0 for begin in 1 ... end { if array[maxValueIndex] < array[begin] { maxValueIndex = begin } } let tmp = array[maxValueIndex] array[maxValueIndex] = array[end] array[end] = tmp } } }
* 最好、最坏、平均时间复杂度:O(n^2)
* 空间复杂度: O(1)
* 稳定性: 不稳定
相关推荐
randy0 2020-11-17
lixiaotao 2020-10-07
美丽的泡沫 2020-09-08
nongfusanquan0 2020-08-18
hang0 2020-08-16
earthhouge 2020-08-15
算法改变人生 2020-07-28
troysps 2020-07-19
Broadview 2020-07-19
chenfei0 2020-07-18
风吹夏天 2020-07-07
yangjingdong00 2020-07-05
数据与算法之美 2020-07-05
shawsun 2020-07-04
数据与算法之美 2020-07-04
要知道时间复杂度只是描述一个增长趋势,复杂度为O的排序算法执行时间不一定比复杂度为O长,因为在计算O时省略了系数、常数、低阶。实际上,在对小规模数据进行排序时,n2的值实际比 knlogn+c还要小。
Evankaka 2020-07-04
田有朋 2020-06-28