前面看到有人发了数组排序的代码,想起自己前阵子为了应付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书上没有讲,都比较简单)
分享到:
相关推荐
**冒泡排序**是一种简单的比较型排序算法,通过重复遍历待排序的元素列表,每次比较相邻的两个元素并根据需要交换它们的位置,直到整个列表完全排序。这个过程就像水底下的气泡一样,较大的元素逐渐“浮”到列表的...
- **排序算法**:如冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序等,以及它们的时间复杂度比较。 - **查找算法**:如线性查找、二分查找、哈希查找等,以及适用场景的讨论。 - **图论算法**:包括...
综上所述,算法复习资料涵盖了IT领域的诸多重要概念,包括但不限于数据结构、排序算法、搜索算法、图论、动态规划以及问题求解策略。通过深入学习和实践,你可以提升自己的编程能力,更好地应对复杂的编程挑战。
排序算法复习大全(Java 实现) 本文档旨在详细介绍排序算法的各种实现方式,包括插入排序、冒泡排序、选择排序、Shell 排序和快速排序等,所有算法都使用 Java 语言实现。本文档首先引入了一个基础类 Sorter,用于...
数据结构与算法是计算机科学的基础,它涉及到如何高效地存储和处理数据,是解决复杂问题的关键。本复习资料涵盖了多项核心知识点,旨在帮助学生...在复习过程中,结合习题和关键代码加深理解,对通过期末考试至关重要。
介绍了C语言冒泡排序算法的原理、步骤、实现方法和优化技巧,以及相关的概念和知识,如数组、循环、交换、比较、稳定性、时间复杂度等。本资源适合C语言初学者和考生使用,帮助他们深入理解和掌握冒泡排序算法的原理...
希尔排序是一种基于插入排序的快速排序算法,由Donald Shell于1959年提出。它的主要思想是将待排序的数组元素按照一定的间隔分组,然后对每组进行插入排序,随着间隔逐渐减小,直到间隔为1时,整个数组成为一个组,...
这里的Sort部分可能包含了各种排序算法的实现,可以帮助你理解它们的工作原理并进行性能比较。 通过这些复习代码,你可以加深对数据结构和算法的理解,同时提高编程能力。实践是掌握这些概念的关键,所以不妨动手...
《leetCode一线大厂算法详解+代码》是一个针对程序员面试准备的重要资源,它涵盖了大量算法题目及对应的解题代码,旨在帮助求职者提升算法能力,顺利通过一线大厂的面试。这里的“一线大厂”通常指的是如阿里巴巴、...
主要有直接插入排序,选择排序,冒泡排序,二分排序,shell排序等等
冒泡排序是最基础的排序算法之一,其原理简单直观,通过不断比较相邻两个元素的大小并交换位置来实现排序。书中提供了冒泡排序的三种实现方式: - **冒泡排序1**:基本版本,通过双重循环完成排序。 - **冒泡排序2*...
在计算机科学领域,排序算法是数据结构中至关重要的一部分,它涉及到如何有效地重新排列一组数据,使其按照特定顺序存储。...对于编程初学者或想要复习排序算法的开发者来说,这是一个非常实用的工具。
### Java基础复习笔记11基本排序算法 #### 内容概览 本文档主要介绍了Java中的几种基本排序算法,包括冒泡排序、快速排序、选择排序、堆排序等,并通过具体的代码实例对每种排序算法进行了详细的解释。文档旨在...
1. **排序算法**:排序是算法学习的基础,可能会包括快速排序、归并排序、冒泡排序、插入排序、选择排序等。每个算法都有其独特的工作原理和效率,学习者需要理解它们的时间复杂度和空间复杂度。 2. **查找算法**:...
在编程领域,排序和查找是两个非常基础且重要的概念,特别是在C#这样的面向对象编程语言中。...这份“C#经典排序算法大全和二分查找算法”的资源,无疑为学习和复习这些核心概念提供了宝贵的材料。
1. **排序算法**:包括冒泡排序、选择排序、插入排序、快速排序、归并排序等,这些是基础且常见的算法,用于对一组数据进行排列。 2. **搜索算法**:如线性搜索、二分查找,以及图遍历算法(深度优先搜索DFS和广度...
介绍: 该资源详细介绍了如何使用Python语言实现快速排序算法(Quick Sort)。快速排序是一种高效的...面试准备:对于准备参加技术面试的候选人,快速排序算法是一个常见的面试题目,本资源可以帮助候选人复习和准备。
冒泡排序是一种简单的排序算法,其工作原理是通过重复遍历待排序的序列,比较相邻元素并根据需要交换它们的位置,使得较大的元素逐渐“浮”到序列的末尾,就像水中的气泡一样上升。在PPT的第2页和第6页,冒泡排序的...
10. **STL(Standard Template Library)**:向量、链表、映射、集合等容器的使用,以及算法如排序、查找等。 11. **内存管理**:动态内存分配(new/delete),理解堆栈和堆的区别。 通过分析和理解这些代码,初学...