以图明志

计算机算法

[专题] 快速排序里的学问:随机化快排

选择随机数作为枢纽元
一般来说随机选取枢纽元这种策略非常安全,除非随机数生成器有问题(这不像你所想象的那么罕见),因为随机的枢纽元不可能总在接连不断地产生劣质的分割。另一方面,随机数的生成一般是昂贵的,根本减少不了算法其余部分的平均运行时间。算法与前面《算法导论》里的例子差不多,只是在调用分割Partition时加入一个随机数,具体可以参看程序。

计算机算法

[专题] 快速排序里的学问:霍尔与快速排序

再次深入理解快速排序
霍尔 (Sir Charles Antony Richard Hoare) 是一位英国计算机科学家,他是著名的快速排序 (QuickSort) 的发明者。在平均状况下,排序 n 个项目要Ο(n log n) 次比较,而且通常明显比其他Ο(n log n) 演算法更快。所以它是一个被广泛使用的算法。在一次采访中,霍尔谈到了发明这个算法的背景。

计算机算法

[专题] 快速排序里的学问:快速排序的过程

理解快速排序的工作机制
通过前面问题以及引入了“信息熵”的概念,我们可以重新来理解排序的本质:一组未排序的N个数字,它们一共有N!种重排,其中只有一种排列是满足题意的(譬如从大到小排列)。换句话说,排序问题的可能性一共有N!种。任何基于比较的排序的基本操作单元都是“比较a和b”,这就相当于猜数字游戏里面的一个问句。

数据结构

单链表排序之选择排序

通过这个理解单链表的排序方法
单链表排序是单链表的常见编程任务之一,也是面试中经常出现的题目。单链表排序的关键是交换算法,需要额外考虑。选择排序是比较直观的排序算法之一,这里就使用选择排序实现单链表的排序。如果需要对选择排序复习一下,传送门:算法导论:选择排序的原理与实现。

数据库技术

最常用的SQL排序、分组与统计的使用方法

Order by/Group by/having等的使用
以一种有意义的方式组织数据可能是一项挑战。有时你需要的可能是一个简单的排序,但是通常你需要做更多,你需要分组来进行分析和统计。幸运的是,SQL提供了大量语句和操作来进行排序,分组和摘要。下面的一些技巧将会帮助你识别什么时候排序,什么时候分组,什么时候以及如何统计。

计算机算法

用递归实现的快速排序

快速排序的两种不同实现
快速排序是对冒泡排序的一种改进。它的基本思想是:通过一次排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一不部分的所有数据都要小,然后再按次方法对这两部分数据分别进行快速排序,整个排序过程可以递归或者非递归进行,以此达到整个数据变成有序序列。

计算机算法

JavaScript各种排序的性能比较

各种排序算法在JavaScript下的表现
排序是经常使用的编程例子,在JavaScript里各种排序的性能又如何呢?每个浏览器测试得出的数据会不一样。比如我用chrome 测试 一般快速排序都会最快,IE 则根据数组长度有可能希尔最快。不要用太大数据去测试冒泡排序(浏览器崩溃了我不管)。

计算机算法

一个优化的堆排序

每次降序提取元素建立从右到左的有序序列
如何生成m个随机数?看了编程珠玑的文章,知道了一些,后来又在csdn上发现了其他人设计的。如果没有头绪,那就按平常来说就是随机生成一个数,然后比较集合中是否存在,不存在放里面,否则再继续生成。每次按降序提取元素,这样建立从右到左的有序序列。n-1 次siftup 和siftdown ,每个操作最多O(logn),故时间是 O(nlogn),很好很强大啊。

计算机算法

C语言/MFC 选择排序

MFC的Edit Control用法
本文的目的是了解C语言下的选择排序,并分别在C与MFC下实现选择排序。关于MFC下Edit Control的换行,可以用下面的方法:sort_result = sort_result + _T("~ \r\n"); 除了使用 \r\n 之外,还要对 CEdit 的属性进行设置: Auto HScroll 设置为 False, MultiLine 设置为 True,Want Return 设置为 True。

C/C++编程语言

各排序算法的C++实现与性能测试

了解下各种排序的效率问题
排序是计算机算法中非常重要的一项,而排序算法又有不少实现方法,那么哪些排序算法比较有效率,哪些算法在特定场合比较有效,下面将用C++实现各种算法,并且比较他们的效率,让我们对各种排序有个更深入的了解。可以看出,计数排序效率很高,插入与冒泡性能不怎么好。

计算机算法

JavaScript排序算法之归并排序

归并排序
归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。归并排序是建立在归并操作上的一种有效的排序算法。

计算机算法

JavaScript排序算法之堆排序

堆排序
堆积排序(Heapsort)是指利用堆积树(堆)这种资料结构所设计的一种排序算法,可以利用数组的特点快速定位指定索引的元素。堆排序(HeapSort)是一树形选择排序。堆排序的特点是:在排序过程中,将R[l..n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系(参见二叉树的顺序存储结构),在当前无序区中选择关键字最大(或最小)的记录。

计算机算法

JavaScript排序算法之希尔排序

希尔排序
希尔排序,也称递减增量排序算法,是插入排序的一种高速而稳定的改进版本。希尔排序是基于插入排序的以下两点性质而提出改进方法的:插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率。但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位。希尔排序按其设计者希尔(Donald Shell)的名字命名,该算法由1959年公布。

计算机算法

JavaScript排序算法之选择排序

选择排序
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾。以此类推,直到所有元素均排序完毕。选择排序的交换操作介于0和(n − 1)次之间。选择排序的比较操作为n(n − 1) / 2次之间。选择排序的赋值操作介于0和3(n − 1)次之间。

计算机算法

JavaScript排序算法之插入排序

插入排序
插入排序(straight insertion sort)的做法是:每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序。第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从前向后扫描,把第三个数按大小插入到有序表中;依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。直接插入排序属于稳定的排序,时间复杂性为o(n^2),空间复杂度为O(1)。

计算机算法

JavaScript排序算法之快速排序

快速排序
快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
1 / 2 首页 < Prev 1 2 Next > 尾页 页码: