`
DigitalSonic
  • 浏览: 214710 次
社区版块
存档分类
最新评论

比较排序算法的简单复习(说明+代码)

阅读更多

前面看到有人发了数组排序的代码,想起自己前阵子为了应付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书上没有讲,都比较简单)

 

3
1
分享到:
评论

相关推荐

    排序算法实现代码与伪代码

    **冒泡排序**是一种简单的比较型排序算法,通过重复遍历待排序的元素列表,每次比较相邻的两个元素并根据需要交换它们的位置,直到整个列表完全排序。这个过程就像水底下的气泡一样,较大的元素逐渐“浮”到列表的...

    算法设计配套资源+复习作业

    - **排序算法**:如冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序等,以及它们的时间复杂度比较。 - **查找算法**:如线性查找、二分查找、哈希查找等,以及适用场景的讨论。 - **图论算法**:包括...

    算法复习算法复习资料

    综上所述,算法复习资料涵盖了IT领域的诸多重要概念,包括但不限于数据结构、排序算法、搜索算法、图论、动态规划以及问题求解策略。通过深入学习和实践,你可以提升自己的编程能力,更好地应对复杂的编程挑战。

    排序算法复习大全(Java实现).doc

    排序算法复习大全(Java 实现) 本文档旨在详细介绍排序算法的各种实现方式,包括插入排序、冒泡排序、选择排序、Shell 排序和快速排序等,所有算法都使用 Java 语言实现。本文档首先引入了一个基础类 Sorter,用于...

    数据结构与算法总复习(知识点+习题+关键代码)

    数据结构与算法是计算机科学的基础,它涉及到如何高效地存储和处理数据,是解决复杂问题的关键。本复习资料涵盖了多项核心知识点,旨在帮助学生...在复习过程中,结合习题和关键代码加深理解,对通过期末考试至关重要。

    C语言冒泡排序算法详解:从原理到代码的完整教程

    介绍了C语言冒泡排序算法的原理、步骤、实现方法和优化技巧,以及相关的概念和知识,如数组、循环、交换、比较、稳定性、时间复杂度等。本资源适合C语言初学者和考生使用,帮助他们深入理解和掌握冒泡排序算法的原理...

    (希尔排序算法).doc计算机系算法分析

    希尔排序是一种基于插入排序的快速排序算法,由Donald Shell于1959年提出。它的主要思想是将待排序的数组元素按照一定的间隔分组,然后对每组进行插入排序,随着间隔逐渐减小,直到间隔为1时,整个数组成为一个组,...

    《数据结构与算法》复习代码.zip

    这里的Sort部分可能包含了各种排序算法的实现,可以帮助你理解它们的工作原理并进行性能比较。 通过这些复习代码,你可以加深对数据结构和算法的理解,同时提高编程能力。实践是掌握这些概念的关键,所以不妨动手...

    leetCode一线大厂算法详解+代码

    《leetCode一线大厂算法详解+代码》是一个针对程序员面试准备的重要资源,它涵盖了大量算法题目及对应的解题代码,旨在帮助求职者提升算法能力,顺利通过一线大厂的面试。这里的“一线大厂”通常指的是如阿里巴巴、...

    常见排序算法复习及代码

    主要有直接插入排序,选择排序,冒泡排序,二分排序,shell排序等等

    MoreWindows白话经典算法之七大排序第2版(高清)

    冒泡排序是最基础的排序算法之一,其原理简单直观,通过不断比较相邻两个元素的大小并交换位置来实现排序。书中提供了冒泡排序的三种实现方式: - **冒泡排序1**:基本版本,通过双重循环完成排序。 - **冒泡排序2*...

    排序算法动态演示

    在计算机科学领域,排序算法是数据结构中至关重要的一部分,它涉及到如何有效地重新排列一组数据,使其按照特定顺序存储。...对于编程初学者或想要复习排序算法的开发者来说,这是一个非常实用的工具。

    Java基础复习笔记11基本排序算法

    ### Java基础复习笔记11基本排序算法 #### 内容概览 本文档主要介绍了Java中的几种基本排序算法,包括冒泡排序、快速排序、选择排序、堆排序等,并通过具体的代码实例对每种排序算法进行了详细的解释。文档旨在...

    算法期末代码+简答123123

    1. **排序算法**:排序是算法学习的基础,可能会包括快速排序、归并排序、冒泡排序、插入排序、选择排序等。每个算法都有其独特的工作原理和效率,学习者需要理解它们的时间复杂度和空间复杂度。 2. **查找算法**:...

    C# 经典排序算法大全和二分查找算法

    在编程领域,排序和查找是两个非常基础且重要的概念,特别是在C#这样的面向对象编程语言中。...这份“C#经典排序算法大全和二分查找算法”的资源,无疑为学习和复习这些核心概念提供了宝贵的材料。

    算法期末代码+简答123

    1. **排序算法**:包括冒泡排序、选择排序、插入排序、快速排序、归并排序等,这些是基础且常见的算法,用于对一组数据进行排列。 2. **搜索算法**:如线性搜索、二分查找,以及图遍历算法(深度优先搜索DFS和广度...

    通过使用python语言实现的快速排序算法

    介绍: 该资源详细介绍了如何使用Python语言实现快速排序算法(Quick Sort)。快速排序是一种高效的...面试准备:对于准备参加技术面试的候选人,快速排序算法是一个常见的面试题目,本资源可以帮助候选人复习和准备。

    浙教算法与程序设计VB排序复习PPT课件.pptx

    冒泡排序是一种简单的排序算法,其工作原理是通过重复遍历待排序的序列,比较相邻元素并根据需要交换它们的位置,使得较大的元素逐渐“浮”到序列的末尾,就像水中的气泡一样上升。在PPT的第2页和第6页,冒泡排序的...

    1-11天Tc++代码

    10. **STL(Standard Template Library)**:向量、链表、映射、集合等容器的使用,以及算法如排序、查找等。 11. **内存管理**:动态内存分配(new/delete),理解堆栈和堆的区别。 通过分析和理解这些代码,初学...

Global site tag (gtag.js) - Google Analytics