- 浏览: 3557542 次
- 性别:
- 来自: 杭州
文章分类
- 全部博客 (1491)
- Hibernate (28)
- spring (37)
- struts2 (19)
- jsp (12)
- servlet (2)
- mysql (24)
- tomcat (3)
- weblogic (1)
- ajax (36)
- jquery (47)
- html (43)
- JS (32)
- ibatis (0)
- DWR (3)
- EXTJS (43)
- Linux (15)
- Maven (3)
- python (8)
- 其他 (8)
- JAVASE (6)
- java javase string (0)
- JAVA 语法 (3)
- juddiv3 (15)
- Mule (1)
- jquery easyui (2)
- mule esb (1)
- java (644)
- log4j (4)
- weka (12)
- android (257)
- web services (4)
- PHP (1)
- 算法 (18)
- 数据结构 算法 (7)
- 数据挖掘 (4)
- 期刊 (6)
- 面试 (5)
- C++ (1)
- 论文 (10)
- 工作 (1)
- 数据结构 (6)
- JAVA配置 (1)
- JAVA垃圾回收 (2)
- SVM (13)
- web st (1)
- jvm (7)
- weka libsvm (1)
- weka屈伟 (1)
- job (2)
- 排序 算法 面试 (3)
- spss (2)
- 搜索引擎 (6)
- java 爬虫 (6)
- 分布式 (1)
- data ming (1)
- eclipse (6)
- 正则表达式 (1)
- 分词器 (2)
- 张孝祥 (1)
- solr (3)
- nutch (1)
- 爬虫 (4)
- lucene (3)
- 狗日的腾讯 (1)
- 我的收藏网址 (13)
- 网络 (1)
- java 数据结构 (22)
- ACM (7)
- jboss (0)
- 大纸 (10)
- maven2 (0)
- elipse (0)
- SVN使用 (2)
- office (1)
- .net (14)
- extjs4 (2)
- zhaopin (0)
- C (2)
- spring mvc (5)
- JPA (9)
- iphone (3)
- css (3)
- 前端框架 (2)
- jui (1)
- dwz (1)
- joomla (1)
- im (1)
- web (2)
- 1 (0)
- 移动UI (1)
- java (1)
- jsoup (1)
- 管理模板 (2)
- javajava (1)
- kali (7)
- 单片机 (1)
- 嵌入式 (1)
- mybatis (2)
- layui (7)
- asp (12)
- asp.net (1)
- sql (1)
- c# (4)
- andorid (1)
- 地价 (1)
- yihuo (1)
- oracle (1)
最新评论
-
endual:
https://blog.csdn.net/chenxbxh2 ...
IE6 bug -
ice86rain:
你好,ES跑起来了吗?我的在tomcat启动时卡在这里Hibe ...
ES架构技术介绍 -
TopLongMan:
...
java public ,protect,friendly,private的方法权限(转) -
贝塔ZQ:
java实现操作word中的表格内容,用插件实现的话,可以试试 ...
java 读取 doc poi读取word中的表格(转) -
ysj570440569:
Maven多模块spring + springMVC + JP ...
Spring+SpringMVC+JPA
快速排序算法的伪代码。
package endual;
public class QuickSortClass {
/**
public void recQuickSort(int left, int right) {
if(right-left <= 0) {
return ;
}else {
int partition = partitionIn(left,right) ; //返回的是关键词的key经过划分以后的位子
recQuickSort(left,partition-1); //左边进行划分算法
recQuickSort(partition+1,right) ; //右边进行划分算法
}
}
1.把数组或者子数组划分为左边和右边的一组
2.调用自身对左边的一组数组进行排序(划分排序)
3.再次调用自身对右边的一组进行排序{划分排序)
这里不需要调用数据项也就是我们说的那个key值。
选择key值,或者叫做枢纽划分排序的key值
选择枢纽(我喜欢叫做key值)
partitionInt()方法应该使用什么样的枢纽
1.应该选择具体的一个数据项的值来作为枢纽,称为数据数列的枢纽可以用单词pivot表示
2.可以选择任意数据项作为枢纽。为了简便,我们假设总是选择待划分的子数组最右边的数据项作为枢纽的
3.划分完成以后,如果枢纽被插入到左边和右边数据之间的划分处,那么枢纽就落在排序之后的最终位子了
听起来虽然似乎不太可能。但是,正因为使用枢纽的关键词的值来划分数组,所以划分之后的左边子数组所包含的
是所有小于枢纽的数据,右边是大于的。枢纽开始时在右边,但是如果以某种方式把它放在两个字数组之间,枢纽
就会在正确的位子上了。也就是说,在它最终的位子上了。
public void recQuickSort(int left, int right) {
if(right-left <= 0) {
return ;
}else {
long provit = theArray[right] ;
int partition = partitionIn(left,right,pivot) ; //返回的是关键词的key经过划分以后的位子
recQuickSort(left,partition-1); //左边进行划分算法
recQuickSort(partition+1,right) ; //右边进行划分算法
}
}
当选择右边数组的最右边的数据项作为枢纽的方案的时候,需要修改partitionIntde 方法。从划分过程中,把最右端
的数据项排除在外面。这个数据项在划分过程中完成之后应该在什么位子已经很清楚了的。
**/
}
划分算法---快速排序算法的核心
快速排序
从划分开始 划分 划分是快速排序的根本机制,但是划分本身也是一个有用的操作,所以我们重点要介绍下划分。 划分数据就是把数据分为两组,使所有关键词大于特定的数据项在一组,使所有关键词小于特定值的数据项在另一组。 很容易想象划分数据的情况: 比如现在有工人的信息。将工人的信息分为两组:家住距离工厂15公里以及15公里内的和家住距离工厂15公里以外的。 比如学习管理者想把学生分成年级平均成绩分为及格和不及格,以此来判定哪些学生应该在主任掌握的名单上。 那么我们来做一个例子吧: 我们在成绩表上会这样的,按照学号排序着,但是现在要把成绩分为60分以上和60分一下吧,比如用60这个作为关键词(划分点, 枢纽)。比关键词大的在右边,比关键字小的在左边(来来来,我们想想希尔排序,这个可比希尔排序的基本排序严格多了哦)。 但是经过划分以后,左边的数据并没排序好的,右边的数据也没排序好的,举个划分好的例子吧: 45,43,54,21,43,【60】,78,98,78,65,67 划分之后的数据还不能称呼为有序的,这只是简单的把数据划分为两组。但是数据还是比没划分之前要更接近有序了。 划分是不稳定的,也就是说,每一组中的数据项并不是按照它原来的顺序排序的。事实上,划分往往会颠倒组中一些数据的顺序。 划分有单独的程序。 划分算法由两个指针开始工作,两个指针分别指向数组的两头。(这里使用指针这个词是指示数组数据项的,而不是C++中所说的指针。 在左边的指针,leftPtr,向右移动,而在右边的指针,rightPtr,向左边移动。 划分算法的效率 划分算法运算的时间复杂度是N
划分算法的代码
package endual;
//划分数据的程序 public class Partition { private long[] theArray ; private int nElems ; public Partition(long[] theArray, int nElems) { super(); this.theArray = theArray; this.nElems = nElems; } public void dispay() { System.out.println("显示划分好以后的数据") ; for (long a : this.theArray) { System.out.println(a); } }// end dispay public int partitionIt(int left, int right, long pivot) { int leftPtr = left - 1 ; int rightPtr = right - 1 ; while (true) { while (leftPtr < right && theArray[++leftPtr] < pivot) { } while (rightPtr < left && theArray[--rightPtr] > pivot) { } if (leftPtr >= rightPtr) { break ; }else { swap(leftPtr, rightPtr) ; } } //end while return leftPtr ; //返回的是枢纽或者key关键词在数组中的位子 } private void swap(int leftPtr, int rightPtr) { long temp ; temp = this.theArray[leftPtr] ; this.theArray[leftPtr] = this.theArray[rightPtr] ; this.theArray[rightPtr] = temp ; } }
快速排序算法理论
快速排序的算法
毫无疑问快速排序是最流行的算法。因为有充足的理由,在大多数情况下,快速排序都是最快得。执行时间是NlogN. 这只是在内排序中或者说事在随机存储器而言的,对于在文件中的排序,可能其他的排序算法更加好。快速排序是1962年发现的。 为了理解快速排序算法,我们要非常理解划分算法。快速排序算法本质上通过把一个数组划分为两个数组,然后递归地调用自身为 每个子数组进行快速的排序来实现的。 但是,对于这个基本的设计还需要进行一些加工。算法还必须需要选择key值以及对于小的划分区域进行排序。看过这个主要算法的简化 代码以后。还需要对其进行求精。 在理解快速排序的道理之前想知道快速排序干的是什么,我们先给出了快速排序的代码吧
代码
发表评论
-
java 归并排序 自己写
2012-02-22 09:03 1455package endual.xier.writeaga ... -
递归思想 汉诺塔的问题
2012-02-09 10:46 1657package endual; public cl ... -
带权图 最短路径 代码自己写
2012-02-09 10:46 3186最短路径问题 可 ... -
带权图的最小生成树 (代码自己写)
2012-02-08 16:02 46591.大理论的一些资料 ... -
数据结构学习的在线好网址
2012-02-07 16:20 1565http://sjjg.js.zwu.edu.cn/SFXX/ ... -
有向无环图 拓扑排序
2012-02-07 15:53 3463package endual.tuopupaixu; ... -
java 图的最小生成树问题 (代码自己写)
2012-02-07 13:51 2792最小生成树是基于无无向图,并且是没有权值的图的。它的实现可以用 ... -
java 图 代码自己写
2012-02-07 13:07 1790图的建立也是基于数组的,但是遍历的话是基于链表或者是矩阵的 ... -
堆 (自己写)
2012-02-06 13:32 1462堆也是基于数组的哦,所以在创建的时候,请先要考虑好数组的大小了 ... -
哈希表的一些概念 代码(自己写)
2012-02-05 18:44 2185首先,我们要明确一点 ... -
红黑树的一些概念
2012-02-05 14:43 2013普通的二叉树作为数 ... -
两个正整数相加
2012-02-05 09:48 1873import java.util.Scanner; i ... -
二叉树代码
2012-02-05 09:51 1725package endual; /** * 树 ... -
java 二叉树
2012-02-04 14:17 1577为什么要用二叉树 通常我们去实现数据结构有两种方式,一 ... -
桶排序(代码自己写)
2012-02-04 13:24 2036简单来说,就是把数据分组,放在一个个的桶中,然后对每个桶 ... -
各类排序算法
2012-02-04 13:19 1482隐藏▲ 查 · 论 -
java 希尔排序算法(自己写)
2012-02-04 10:26 1872希尔排序算法是对插入算法的应用吧,就是多次的使用了插入算法多排 ... -
递归 字符串的全排列
2012-02-03 15:29 2459package endual; public class ... -
java递归的一个问题
2012-02-03 13:56 1869据说比达格斯理论家,又称一群在必达格斯领导下工作的古希腊数学家 ... -
java 实现链表(自己写的)
2012-02-03 11:03 1661今天用java写了下的链表, 还是有点糊涂的。这和C语言写的链 ...
相关推荐
自己写的三个排序算法的比较。快速排序、归并排序、简单排序 对三个排序算法所消耗时间进行统计,比较时间效率 程序是在Linux下用C写的,vc下并未做测试。
主要采用快速排序实现(串行,openmp、mpi、openmp+mpi)排序算法,所需环境为VS2019+openmp+mpi,cmd命令 (1)完成了CPU串行程序和三种并行程序在各种规模的运行,并作出时间对比图 (2)完成了串行,openmp使用...
面试必考的排序算法!该算法是本人自己写的,符合面试的规则,而且是数据结构的重要算法!
本文将详细探讨标题为"各种自己写的排序算法,做个备份"的压缩包中可能包含的知识点,并对描述中提及的"略微做个备份"进行解析。 首先,我们关注到两个文件名:"拆分排序.cpp"和"SieveSort.cpp",它们分别代表两种...
当然,为了学习和理解,我们也可以自己编写这些基本排序算法的C++代码。 例如,快速排序的C++实现可能如下: ```cpp void quickSort(int arr[], int left, int right) { if (left ) { int pivotIndex = ...
"自己写的排序算法,还有点小问题"这个标题表明作者已经尝试实现了一个排序算法,但可能遇到了一些挑战或bug。描述中提到的“只有个框架,递归计算”暗示了作者可能使用了递归的方式来实现排序,这是一种常见的编程...
本项目中,你提供了六种不同的排序算法的C#实现:冒泡排序、选择排序、快速排序、哈希排序、堆排序以及插入排序。下面将详细解释这些排序算法的原理和特点。 1. **冒泡排序**: 冒泡排序是最简单的排序算法之一,...
自学算法导论中前几章,并自己写的排序算法源码包括gtest的测试用例。 详细介绍看我博客 http://blog.csdn.net/ceofit 一、选择法排序、冒泡排序、插入法排序 http://blog.csdn.net/ceofit/article/details/7397020 ...
冒泡排序是一种简单的排序算法。它重复地遍历要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来...
本文实例为大家分享了C/C++实现双路快速排序算法的具体代码,供大家参考,具体内容如下 看了刘宇波的视频,讲双路快速排序的,原理讲的很直观,程序讲解也一看就懂。这里写一下自己的理解过程,也加深一下自己的理解...
内部排序算法是指在内存中进行排序的算法,常见的内部排序算法有冒泡排序、选择排序、插入排序、归并排序、快速排序等。 在JavaScript中,我们可以使用onsubmit事件和onblur事件来实现表单校验。在下面的例子中,...
- **作为其他排序算法的基础**:插入排序是其他更复杂排序算法(如希尔排序、快速排序的尾递归部分)的基础。 ### 总结 插入排序虽然在最坏情况下时间复杂度较高,但其简单性、稳定性和在特定条件下的高效性使其在...
总之,"自己写的排序2.0版本"是一个使用递归方法实现的排序算法,可能是基于快速排序的变体或者是受到埃拉托斯特尼筛法启发的原创算法。C++源代码和编译后的可执行文件为我们提供了实现细节和验证算法功能的可能性。...
自己写的排序代码,用c语言实现,包含:直接插入排序,希尔排序,快速排序, 简单选择排序,堆排序,归并排序。
内容概要:这是本人在复习数据结构排序算法所写的markdown文档,对各个算法进行了比较,分析其稳定性。通过对六种排序算法的介绍,了解其中的核心原理,手写源码过程中对其代码进行注释讲解。 适用人群:本人文档是...
4. **快速排序算法**:理解快速排序的基本原理,如何选择基准元素,如何分割和合并子数组。 5. **并发控制**:考虑到多进程多线程环境,需要理解锁、信号量等并发控制机制,以防止数据竞争问题。 通过分析这个项目...
快速排序是一种非常高效的排序算法,其基本思想是通过分治法将待排序数组分为较小和较大的两个子数组,然后递归地对这两个子数组进行排序。本章将深入探讨快速排序的细节。 #### 7. Sorting in Linear Time(线性...
首先,我编写了一个经典的快速排序算法。这个算法通过计算样本的平均值来估计整个数组的中心点,然后用作初始枢轴。 我借鉴了一些Java的思路来适当改进我的快速排序,修改后的算法在对小数组进行排序的时候...
排序算法包括快速排序、归并排序、堆排序等,这些是每个程序员必备的基础知识。搜索算法则可能包括二分查找、广度优先搜索(BFS)和深度优先搜索(DFS),它们在处理大量数据时非常有效。 其次,书中可能深入到图论和树...