前面看到有人发了数组排序的代码,想起自己前阵子为了应付xxxxxx公司笔试复习时写下的一些关于比较排序算法
的笔记和代码,拿出来和大家分享一下,攒点RP:
(代码基本是按照《算法导论》的伪代码写的,lgn是以2为底的,西塔估计打不出,我这里都用O了)
1、Insertion Sort
遍历数组,将小的值插在前面。
是原地、
稳定
的排序算法。复杂度O(n^2)
a = [5,2,4,6,1,3]
p a
for j in 1...a.size
key = a[j]
i = j - 1
while i >=0 and a[i] > key
a[i + 1] = a[i]
i -= 1
end
a[i + 1] = key
end
p a
2、Merge Sort
递归排序A[1..n/2] A[n/2+1..n],然后合并两端已排序序列,当n=1时排序完成。
是非原地、非稳定
的排序算法。复杂度O(nlgn)
def merge (arr, s, mid, e)
n1 = mid - s + 1
n2 = e - mid
left = arr[s..mid]
right = arr[mid + 1..e]
i = j = 0
for index in s..e
if i < n1 and j < n2
if left[i] < right[j]
arr[index] = left[i]
i += 1
else
arr[index] = right[j]
j += 1
end
else
arr[index..e] = left[i...n1] if i < n1
arr[index..e] = right[j...n2] if j < n2
end
end
end
def merge_sort(arr, s, e)
if s < e
mid = (s + e) / 2
merge_sort arr, s, mid
merge_sort arr, mid + 1, e
merge arr, s, mid, e
end
end
a = [5,2,4,6,1,3]
p a
merge_sort a, 0, a.size - 1
p a
3、Quick Sort
将数组A[p..r]分成A[p..q-1]和A[q+1..r](可能有空数组),前者小于A[q],后者大于A[q];对两个数组分别进行Quick Sort。
是原地、非稳定
的排序算法,最坏运行时间O(n^2),平均运行时间O(nlgn)。
def partition arr, start_index, end_index
x = arr[end_index]
i = start_index
(start_index...end_index).each do |j|
if arr[j] <= x
arr[j], arr[i] = arr[i], arr[j]
i += 1
end
end
arr[i], arr[end_index] = arr[end_index], arr[i]
p arr
i
end
def quick_sort arr, start_index, end_index
if start_index < end_index
pivot = partition arr, start_index, end_index
quick_sort arr, start_index, pivot - 1
quick_sort arr, pivot + 1, end_index
end
end
a = [5,2,4,6,1,3]
p a
quick_sort a, 0, a.size - 1
p a
4、Heap Sort
堆可以被看作一棵完全二叉树;数组表示时,结点i,parent为[i/2],left为2i,right为2i+1;长度为n的数组表示堆, [n/2]+1到n都为叶结点。([]表示取下底)
堆排序使用最大堆,先构建最大堆,取出堆顶元素放在最后,堆的元素数减1,维护最大堆性质,再取出堆顶元素,直至完全排序。
是原地、非稳定
的排序算法,MAX_HEAPFIER时间为O(lgn),BUILD_MAX_HEAP为O(n),HEAP_SORT为O(nlogn)。
def max_heapfier arr, root_index, heap_size
left_index = root_index * 2
right_index = left_index + 1
max_index = root_index
max_index = left_index if left_index < heap_size && arr[left_index] > arr[root_index]
max_index = right_index if right_index < heap_size && arr[right_index] > arr[max_index]
unless max_index == root_index
arr[root_index], arr[max_index] = arr[max_index], arr[root_index]
max_heapfier arr, max_index, heap_size
end
end
def build_max_heap arr, root_index, heap_size
(heap_size / 2).downto(0) { |i| max_heapfier arr, i, heap_size}
end
def heap_sort arr
build_max_heap arr, 0, arr.size
heap_size = arr.size
(heap_size - 1).downto(1) do |i|
arr[0], arr[i] = arr[i], arr[0]
heap_size -= 1
max_heapfier arr, 0, heap_size
end
end
a = [5,2,4,6,1,3]
p a
heap_sort a
p a
5、Selection Sort
遍历数组,每次取出最小的元素。
是原地、稳定
的排序算法,复杂度O(n^2)。
def get_min(arr, b, e)
min_index = b
for i in b..e
min_index = i if arr[i] < arr[min_index]
end
min_index
end
a = [5,2,4,6,1,3]
p a
for i in 0...a.size
index = get_min a, i, a.size - 1
a[i], a[index] = a[index], a[i]
end
p a
6、Bubble Sort
遍历数组,邻近的两两比较,小的放前面,直到最小的移到最前面,重复这个过程,直至排序完毕。
是原地、稳定
的排序算法,复杂度O(n^2)。
a = [5,2,4,6,1,3]
def bubble_sort arr
(0...arr.size).each do |i|
(arr.size - 1).downto i do |j|
arr[j], arr[j - 1] = arr[j - 1], arr[j] if arr[j] < arr[j - 1]
end
end
end
p a
bubble_sort a
p a
(5出现在习题里,6书上没有讲,都比较简单)
分享到:
相关推荐
这本书是用java讲数据结构和排序算法的,全书只有44页,但是讲的内容很不错,推荐学习或者复习数据结构的童鞋下在看看!
介绍了C语言冒泡排序算法的原理、步骤、实现方法和优化技巧,以及相关的概念和知识,如数组、循环、交换、比较、稳定性、时间复杂度等。本资源适合C语言初学者和考生使用,帮助他们深入理解和掌握冒泡排序算法的原理...
主要有直接插入排序,选择排序,冒泡排序,二分排序,shell排序等等
复习用整理代码。包括直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序。
之前一段时间,由于需要,我复习了一下排序算法,并用Python实现了各种排序算法,放在这里作为参考。 最简单的排序有三种:插入排序,选择排序和冒泡排序。这三种排序比较简单,它们的平均时间复杂度均为O(n^2),在...
内容概要:这是本人在复习数据结构排序算法所写的markdown文档,对各个算法进行了比较,分析其稳定性。通过对六种排序算法的介绍,了解其中的核心原理,手写源码过程中对其代码进行注释讲解。 适用人群:本人文档是...
单源最短路径的实现,活动安排问题代码,矩阵连乘问题C++代码加注释,快速排序代码,旅行售货员问题c++源代码及运行结果,背包问题,栈的应用解决汉诺塔问题,最优二叉搜索树,最优装载问题!
几乎把网上的排序算法小结找遍了,简单地小结一下算法的思路(不含代码,只是用易懂的话说清楚算法是怎么做的),算法时间复杂度和空间复杂的求法(用理解的方式而不是分析代码),各种排序算法的优缺点,稳定与否...
1.欧几里得算法: 2.连续整数检测算法: 3.素数筛选法: 4.矩阵乘积: 6.选择排序: 7.冒泡排序: 8.字符串蛮力匹配: 9.蛮力平面距离最近两点:
5-14 归并排序时间复杂度及排序算法复杂度对比 5-15 二分查找 5-16 二分查找时间复杂度 六、树和树的算法 6-01 树的概念 6-02 二叉树的概念 6-03 二叉树的广度优先遍历 6-04 二叉树的实现 6-05 二叉树的先序...
直接上代码吧! 复制代码 代码如下: <?php /* * 插入排序(一维数组) * 每次将一个待排序的数据元素,插入到前面已经排好序的数列中的适当的位置,使数列依然有序;直到待排序的数据元素全部插入完成为止。 */ ...
、链地址法、开放地址法、第九章排序、直接插入排序、折半插入排序、表插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、固定最大值再构造堆、归并排序、桶排序、基数排序 各种排序方法的综合比较
本压缩资源包含数据结构第二版教材中的全部算法实现代码,按照书中的算法实现,诸如求最小生成树,拓扑排序,二叉树的非递归遍历等等。非常适合初学者学习参考使用,也可以供相关专业大学生学习使用,考研复习使用
快速排序今天复习算法的时候发现并不是当时想的那么难,于是就代码实现了一下!我们都知道快排的效率高低取决于基准元素(这个可能不同的人叫法不一样,就是交换轴,我想你懂的,O(∩_∩)O~)的选择,一般我们选取第...
在代码有集合了所有排序算法的代码,多以template 模板写的,集合了排序算法五大类别:插入、选择、交换、归并、基数 具体分类为: 插入->直接插入 插入->Shell排序(希尔) 选择->直接选择 选择->堆排序 交换->冒泡排序 ...
此项目只是为了在毕业之前复习一下曾经学过的数据结构/算法,初衷是打算仅仅使用Python实现,但写了简单的排序/查找算法之后,觉得对于C/C++我还是应该学习一下,于是就附带了一些之前在BNU上的练习代码。...
☆ 排序算法 五例 ☆ 排序算法一览 ☆ 穷举密码算法 ☆ 如何实现DES算法 ☆ 入栈与出栈的所有排列可能性 ☆ 三维图形的消隐算法分析 ☆ 实用算法(基础算法 递推法) ☆ 数据结构 教程 ☆ 数据结构:哈夫曼树的应用 ☆...
(最新工作比较忙,可能不会及时更新,可以将现有的算法重复复习,也可以自己去网上查找其他自己感兴趣的算法,后面会更新,祝好运!) 学习思路建议: 先理解算法概念,了解其原理,知道其流程 开始敲代码,第一,...
C#中常用-8种初级+高级排序方法 写着拿来复习数据结构和算法,代码编译通过,可以运行!! 就差归并 排序了~~
每个算法都提供了详细的解析和代码实现,帮助读者深入理解算法的原理和应用。 对于初学者,这些算法可以帮助他们掌握Java语言的基本语法和编程技巧,同时了解常见算法的实现方式。对于有一定基础的开发者,可以通过...