《算法基础》——3.6　链表的选择排序

3.6　链表的选择排序

该选择排序算法背后的基本思想是：搜寻输入链表中所包含的最大项，然后将其添加到一个不断增长的有序链表的前面。
下面的伪代码显示了选择排序算法的单向链表实现方法（默认其中的项是整数类型）：

如果将寻找输入链表中最大单元格的代码抽取出来，作为一个新的算法，然后在原有算法中调用该新算法，则可以使得上面的算法变得更加简化。
若输入链表包含K个项，则寻找链表中的最大项需要花费K步。在算法进行的过程中，输入链表将会缩小规模。因此，如果它最初拥有N个项，步骤的总数是N＋(N－1)＋(N－2)＋…＋2＋1＝N×(N＋1)÷2＝O(N2)，这和插入排序的运行时间相同。

时间： 2024-09-27 00:56:10

《算法基础》——3.6　链表的选择排序的相关文章

C++实现八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序等_C 语言

本文实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 .快速排序.归并排序.堆排序和LST基数排序 首先是算法实现文件Sort.h,代码如下: /* * 实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 * 以及快速排序.归并排序.堆排序和LST基数排序 * @author gkh178 */ #include <iostream> template<class T> void swap_value(T &a, T &b) { T t

《算法基础》——3.5　链表算法

3.5 链表算法 到目前为止,本章描述了一些用于建立和维护链表的算法,包括在链表的开头.结尾和中间添加项的算法,查找链表中项的算法和从链表中删除项的算法. 以下各节描述了利用其他方式来操作链表的算法.3.5.1 复制链表 一些算法重新排列链表.本节和下一节将描述一些对链表中的项进行排序的算法.如果想保持原来链表的顺序,就必须在排序之前就做一个该链表的副本. 下面的伪代码演示了如何复制一个单链表: 该算法相当简单,但有一点值得一提:该算法使用last_added来跟踪最新被加入到链表副本中的单元格

Java数据结构及算法实例：选择排序 Selection Sort_java

/** * 选择排序的思想: * 每次从待排序列中找到最小的元素, * 然后将其放到待排的序列的最左边,直到所有元素有序 * * 选择排序改进了冒泡排序,将交换次数从O(N^2)减少到O(N) * 不过比较次数还是O(N) */ package al; public class SelectSort { public static void main(String[] args) { SelectSort selectSort = new SelectSort(); int[] elements

《算法基础》——导读

**前言**算法是使高效的程序成为可能的方法.它们解释了如何排列记录.搜索项.计算数值(比如质因子分解).查找一个街道网络中的最短路径.确定可能通过通信网络的最大流.算法好坏的差别可能意味着是在一秒.一个小时内解决问题,还是永远也不能解决问题.学习算法使你能建立有用的方法工具来解决具体的问题.它能帮助你理解在不同的情况下,哪个算法是最有效的,所以对于一个特定的问题,你就能选择最适合的算法.对某些数据而言性能优异的算法可能对其他的数据而言表现糟糕.所以知道如何选择一个最适合当前情况的算法是很重要的

《算法基础》——3.10　练习

3.10 练习 3.2.5节"在尾部添加单元格"中给出了在单向链表尾部添加单元格的一个时间复杂度为O(N)的算法.如果使用另一个变量bottom来指向链表最后一个单元格,则可以用O(1)时间向链表尾添加项.写出这样的算法.添加变量后会使在首尾添加项.寻找项.删除项变得怎样复杂?写一个从这样链表中移除项的算法.2.写出一个在整数组成的.未排序的单向链表中找出最大项的算法. 3.写出一个在双向链表首部添加一个项的算法.4写出一个在双向链表尾部添加一个项的算法.5.如果把练习3.4的算法与&

数据结构教程 第三十六课 选择排序、归并排序

教学目的: 掌握选择排序,归并排序算法 教学重点: 选择排序之堆排序,归并排序算法 教学难点: 堆排序算法 授课内容: 一.选择排序 每一趟在n-i+1(i=1,2,...n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录. 二.简单选择排序 算法: Smp_Selecpass(ListType &r,int i) { k=i; for(j=i+1;j<n;i++) if (r[j].key<r[k].key) k=j; if (k!=i) { t=r[i];r[i]=r[k

《算法基础：打开算法之门》一3.2 选择排序

3.2 选择排序 现在让我们将注意力转向排序:重排数组中的所有元素--也称为重排数组--以便每个元素小于或者等于它的后继.我们要看到的第一种排序算法是选择排序,这是我能想到的最简单的算法,在设计一个排序算法时,我最先能想到的就是选择排序,虽然它远远不是最快的算法. 下面我们用依据作者名字对书架上的书排序这个例子来说明选择排序是如何运行的.从左向右查找整个书架,并且找到作者名字最先在字母表中出现的书籍.假定这本排序在字母表中最前的书籍是由Louisa May Alcott所写的(如果书架上包含由该

常用内部排序算法之四：简单选择排序、直接插入排序和冒泡排序

前言 之所以把这三类算法放在一块,是因为除此之外的算法都是在这三类算法的基础上进行优化的.简单选择排序的思想是每一趟n−i+1(i=1,2,...,n−1)个记录中选择最小的记录作为有序序列的第i个记录.直接插入排序的思想是将一个记录插入到已经排好序的有序序列中,从而得到一个新的.记录数增加1的有序表.冒泡排序的算法思想是不断在交换,通过交换完成最终的排序,每一趟的交换就会把最大的记录取出来,下一趟则会把第二大的记录取出来,这样每进行一趟交换就把一个记录取出来的过程称为冒泡. 简单选择排序算法

C#的四种排序算法：冒泡排序、选择排序、插入排序和希尔排序

插入|排序|算法 本文介绍了C#的四种排序算法:冒泡排序.选择排序.插入排序和希尔排序 冒泡排序 using System: namespace BubbleSorter { public class BubbleSorter { public void Sort(int [] list) { int i,j,temp: bool done=false: j=1: while((j<list.Length)&&(!done)) { done=true: for(i=0:i<li