排序专题
sort常用排序模式---------shell基础篇（三）
sort 排序命令使用 表达式意义sort -c test测试文件“test”是否已经经过排序，一般用处不大sort -k1 test.txt按照第1域对文件test.txt进行排序，日常可以用来对合并的日志文件进行时间排序sort -k1 -m log1.txt log2.txt按照第一域进行排序后合并输出到控制台，建议使用“>>” 将合并内容输出到另一个文件中sort -t / -k3 te
冒泡算法及改进（属于交换排序）
冒泡排序（Bubble Sort）是一种交换排序，快速排序也属于一种交换排序。冒泡排序的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。 假设一共共有 n 个数，则会进行 (n-1)趟比较，由1，2......n-1这么多趟，第一趟进行 (n-1)次比较，.......第n-1趟进行1次比较，故有公式：第i趟 + 第i趟的比较次数 = n 时间复杂度为
Lintcode 合并两个排序的链表
将两个排序链表合并为一个新的排序链表 样例 给出 1->3->8->11->15->null，2->null， 返回 1->2->3->8->11->15->null。 递归实现： """Definition of ListNodeclass ListNode(object):def __init__(self, val, next=None):self.val = valself.n
【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置
本节博客主要是通过“在排序数组中查找元素的第一个和最后一个位置”总结关于二分算法的左右界代码模板，有需要借鉴即可。 目录 1.题目2.二分边界算法2.1查找区间左端点2.1.1循环条件2.1.2求中点的操作2.1.3总结 2.2查找区间右端点2.1.1循环条件2.1.2求中点的操作2.1.3总结 2.3总结 3.参考解题代码4.模板总结5.总结 1.题目 题目链接：LIN
对于集合中的自定义对象使用collections.sort 进行排序,需要实现compartor接口
/** * 榜单 业务类 * * @author seawind * */ public class RankService { // 查看榜单 public List<Orderitem> showRank() { RankDAO rankDAO = new RankDAO(); List<O
【数据结构】排序(直接插入排序,希尔排序)
目录 一、排序的概念 二、常见的排序算法 三、插入排序 1.直接插入排序 1.直接插入排序实现 2.直接插入排序特性及复杂度 2.希尔排序 1.排序思路 2.希尔排序实现 3.希尔排序的特性及复杂度 一、排序的概念 排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。 稳定性：假定在待排序的记录序列中，存在
排序之单链表插入排序
//插入排序LinkList* LinkList::Sorting(){LinkNode *p1 = phead->pnext;//前指针LinkNode *p2 = p1->pnext;//当前指针LinkNode *p=phead->pnext;//滚动指针LinkNode *pp=phead;//滚动指针的前一个指针 LinkNode *q=phead->pnext;//始终指向第一个有
从二叉排序树到平衡二叉树再到红黑树系列2
上篇博客主要讲述了二叉排序树的基本概念和插入删除操作，必须再次说明的是：在一棵高度为h的二叉排序树上，实现动态集合操作查询,插入和删除的运行时间均为O(h)。 可见二叉树的基本操作效率取决于树的形态，当然树的高度越低越好，显然树分布越均匀，高度越低。那么，问题来了？对于给定的关键字序列，如何构造一棵形态匀称的二叉排序树。这种匀称的二叉排序树就称为平衡二叉树。 平衡二叉树定义：平衡二叉树或
从二叉排序树到平衡二叉树再到红黑树系列1
最近想写一些关于红黑树的博客，既想写的全面，又直观，但是又不知道从哪里入手。斟酌再三，还是从最简单的二叉排序树开始写。 二叉排序树（Binary Sort Tree）又叫二叉查找树。它是一种特殊结构的二叉树。其或为空树，或具备下列性质： （1）若它的左子树不为空，则左子树上所有结点的值均小于它的根节点的值。 （2）若它的右子树不为空，则左子树上所有结点的值均大于它的根节点的值。 显然，它
简单选择排序与堆排序
选择排序的基本运算都是在n个元素组成的序列中，选择一个关键字最大或最小的元素输出，然后再从剩余的n-1个元素中选择一个关键字最大或最小的元素输出，以此类推，直到排序结束。 以递增排序为例，简单选择排序过程如下：1第一次在数组中查找最小值a[i]，然后将a[i]和a[0]交换位置。 2从a[1]开始，同样从a[1]开始往后找到最小值a[j]，然后与a[1]交换位置，依次类推。 废话不多说，直接贴
Python模块之Numpy（五）-- 排序
Sort排序 NumPy 的排序方式主要可以概括为直接排序和间接排序两种，直接排序是对数值直接进行排序，间接排序是指根据一个或者多个键对数据集进行排序，在 NumPy 中，直接排序经常使用 sort 函数，间接排序经常使用 argsort 函数和 lexsort 函数，使用 sort 函数排序可以指定一个 axis 参数，可以沿着指定的轴对数据进行排序，如下面代码
MYSQL和JAVA中将中文汉字按照拼音首字母排序
一、MYSQL将中文汉字按照拼音首字母排序 数据库使用的字符编码是utf8_general_ci，如下 ORDER BY CONVERT(表名.字段名 USING gbk) COLLATE gbk_chinese_ci ASC; 若是表查询，CONVERT中可以不添加表名。 查询结果如下： 二、JAVA中将中文汉字按照拼音首字母排序 1.String集合排序 List<Str
HashMap按key/value排序
HashMap的key为Date，将其转换为List，并按key排序 Map hm = new HashMap<Date, String>(); 主要利用 Comparator这个接口来实现，我这里是排序list里面的时间 分别取到最大的时间和最小的时间。 要实现里面的函数int compare(Object o1, Object o2) 返回一个基本类型的整型，返回负数表示o1 小于o2，
《算法导论》学习笔记之Chapter8线性时间排序
第8章 线性时间排序 前面介绍的包括归并排序，堆排序和快速排序，最后的次序都依赖于元素之间的比较，叫做比较排序。 归并排序和堆排序都是渐近最优的，且任何已知的比较排序最多就是在常数因子上优于他们。即比较排序的时间复杂度下界就是Ω(nlogn)。 线性时间排序算法，包括：基数排序，计数排序和桶排序，是靠运算不是比较来排序的，下界Ω(nlogn)不是他们的下界。 计数排序：假设n个输入元
《算法导论》学习之关于如何利用排序算法，从1亿个数中，选出最大（小）的100个数
首先声明：本文内容是参考别人的博客，链接为：http://blog.csdn.net/beiyeqingteng/article/details/7534489 前言： 刚刚在CSDN上看到一个网友利用最小堆实现 “ 获取一亿数据获取前100个最大值” 。原帖请看：http://blog.csdn.net/yjflinchong/article/details/7533972。 然后自
《算法导论》学习笔记之Chapter7快速排序
第七章 快速排序 对于包含n个数的数组来说，快速排序是一种最坏情况时间复杂度为θ(n.^2)的排序算法。虽然最坏情况时间复杂度很很差，但快速排序通常是实际排序应用中最好的选择，因为他的平均性能非常好：它的期望时间复杂度为θ(nlogn)，而且θ(nlogn)中隐含的常数因子非常小。同时，快速排序还能够进行原址排序，甚至在虚存环境中也能很好的工作。 其中基于随机抽样的快排算法，期望时间复杂
算法学习笔记（5.0）-基于比较的高效排序算法-归并排序
##时间复杂度O(nlogn) 目录 ##时间复杂度O(nlogn) ##递归实现归并排序 ##原理 ##图例 ##代码实现 ##非递归实现归并排序 ##释 #代码实现 ##递归实现归并排序 ##原理 是一种基于分治策略的基础排序算法。 1.划分阶段：通过不断递归地将数组从中点处分开，将长数组的排序问题转化成段数组的排序问题。 2.合并阶段：当子数组的长度为1
十大排序算法之-＞归并排序
一、归并排序简介 归并排序是一种基于分治策略的有效且稳定的排序算法。归并排序由约翰·冯·诺伊曼提出，是计算机科学中一个非常基础且历史悠久的算法。 归并排序利用分治法的策略，将一个大的数组拆分成几个小的子数组，这些子数组各自独立地排序，然后逐步合并成一个完全有序的大数组。归并排序的时间复杂度为O(n log n)，空间复杂度为O(n)，其中n是待排序元素的数量。这种算法特别适合于数据量大且对稳定
设计非递归算法，编程：在二叉排序树中，打印关键码a, b的公共祖先。注：例，若a是b的祖先，则a不算作公共祖先。反之亦然。
二叉排序树： 代码： #include <iostream>using namespace std;// 定义二叉树节点结构typedef struct BTNode {char show;struct BTNode* left;struct BTNode* right;} BTNode;// 非递归插入节点的函数BTNode* insertNode(BTNode* root, c
【算法面试宝典】十大经典排序算法 - 堆排序
1 解题思路 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序。要使用堆这种数据结构，首先要理清什么是堆？堆可以分为大顶堆和小顶堆。堆是一颗完全二叉树，每个节点的值都大于或等于左右孩子节点的值，称为大顶堆；每个节点都小于或等于左右孩子节点的值，称为小顶堆。如下图所示： 如果使用数组来表示堆，我们对堆中的节点按层次编号，如下图所示： 那么大顶堆和小顶
【算法面试宝典】十大经典排序算法 - 选择排序
1 解题思路 选择排序是逻辑比较简单的一种排序算法，核心思想是遍历无序的元素找到最大或者最小值，放入有序元素的末尾。所有元素遍历一遍即把所有元素完成排序。 示例： 输入 nums = {4,8,1,5,9,2} 输出 nums1 = {1,2,4,5,8,9} 插入排序执行步骤： 第一步：初始的时候整个数组都是无序的，所以假设数组最左端的元素 4 是最小值，
【算法面试宝典】十大经典排序算法 - 希尔排序
1 解题思路 希尔排序是第一个算法复杂度突破 O(n^2) 的排序算法，是在插入排序的基础上做了改进，也称为缩小增量排序。希尔排序会把一个序列拆分成多个子序列，分别对多个子序列进行插入排序，然后在合并排好序的子序列，再进行整体的插入排序。子序列的拆分方法是按下标的一定增量来分组，对每一组使用插入排序进行排序，随着增量逐渐减少，每组包含的关键词逐渐增多，当增量减至1时，所有的元素都
【算法面试宝典】十大经典排序算法 - 插入排序
1 解题思路 给定一个无序数组 nums，使用插入排序使数组中的元素按照升序或者降序排列。插入排序的核心思路是把数组 nums 一分为二，一个是已经排好序的数组 nums1，一个是无序的数组nums2，把无序数组 nums2 中的元素，插入有序数组 nums1 中，就得到了一个有序数组，插入的时候需要通过比较值的大小来判断 nums2 中的元素（carry）放在 nums1中的哪