File tree Expand file tree Collapse file tree 7 files changed +9
-9
lines changed
Filter options
Expand file tree Collapse file tree 7 files changed +9
-9
lines changed
Original file line number Diff line number Diff line change 44
55希尔排序是基于插入排序的以下两点性质而提出改进方法的：
66
7- - 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
8- - 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
7+ - 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
8+ - 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
99
1010希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
1111
1212
1313## 1. 算法步骤
1414
15- 1 . 选择一个增量序列 t1，t2，…，tk，其中 ti > tj，tk= 1；
15+ 1 . 选择一个增量序列 t1，t2，…… ，tk，其中 ti > tj, tk = 1；
1616
17172 . 按增量序列个数 k，对序列进行 k 趟排序；
1818
Original file line number Diff line number Diff line change 1010
1111> However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.
1212>
13- > 然而, 在 JavaScript 中这种方式不太可行, 因为这个算法的递归深度对它来讲太深了。
13+ > 然而， 在 JavaScript 中这种方式不太可行， 因为这个算法的递归深度对它来讲太深了。
1414
1515
1616说实话，我不太理解这句话。意思是 JavaScript 编译器内存太小，递归太深容易造成内存溢出吗？还望有大神能够指教。
Original file line number Diff line number Diff line change 66
77快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
88
9- 快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高! 它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n²)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好，可是这是为什么呢，我也不知道。好在我的强迫症又犯了，查了 N 多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案：
9+ 快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！ 它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n²)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好，可是这是为什么呢，我也不知道。好在我的强迫症又犯了，查了 N 多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案：
1010
1111> 快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
1212
1515
16161 . 从数列中挑出一个元素，称为 “基准”（pivot）;
1717
18- 2 . 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作;
18+ 2 . 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
1919
20- 3 . 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序;
20+ 3 . 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
2121
2222递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
2323
Original file line number Diff line number Diff line change 1010
1111## 1. 算法步骤
1212
13- 1 . 创建一个堆 H[ 0.. n-1] ；
13+ 1 . 创建一个堆 H[ 0…… n-1] ；
1414
15152 . 把堆首（最大值）和堆尾互换；
1616
Original file line number Diff line number Diff line change 1212** 关于时间复杂度** ：
1313
14141 . 平方阶 (O(n2)) 排序
15- 各类简单排序: 直接插入、直接选择和冒泡排序。
15+ 各类简单排序： 直接插入、直接选择和冒泡排序。
16162 . 线性对数阶 (O(nlog2n)) 排序
1717 快速排序、堆排序和归并排序；
18183 . O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。
File renamed without changes.
File renamed without changes.
You can’t perform that action at this time.
0 commit comments