近期工作需要,开始复习相关的检索排序算法。对常用的几个算法,自行进行了JavaScript实现:
最朴素的查询
/**
@data 目标元素所在的数组
@target 目标查询元素
@return 目标查询元素所在的下标
*/
function sequenceSearch(data,target){
var resultIndex=-1;
for(var i=0;i<data.length;i++){
if(target==data[i]){
resultIndex=i;
break;
}
}
return resultIndex;
}
注意,适合有序数组中的查找
/**
@data 目标元素所在的数组
@target 目标查询元素
@return 目标查询元素所在的下标
*/
function halfSearch(data,target){
var resultIndex=-1;
//将有序数组分为两部分,使用start,middle与end
var start=0,end=data.length,middle=-1;
while(start<end){
middle=Math.floor((start+end)/2);
if(target>data[middle]){
start=middle+1;
}else if(target<data[middle]){
end=middle-1;
}else{
resultIndex=middle;
break;
}
}
return resultIndex;
}
注意:核心是由前往后,在逐渐排好的前段部分逆向插入元素
/**
@data 目标排序数组
*/
function insertSort(data){
for(var i=1;i<data.length;i++){
var temp=data[i];
if(data[i-1]>temp){
//每次在已经排好序的部分进行插入
for(var j=i-1;j>=0;j--){
if(data[j]>temp){
//向后进行移位,以便当前目标元素可以插入
data[j+1]=data[j];
data[j]=temp;
}
}
}
}
}
注意:逐次将大数向后移,第i个元素需要比较n-i-1次,嵌套循环实现
/**
@data 目标排序数组
*/
function bubbleSort(data){
for(var i=0;i<data.length;i++){
//大数自动向数组大下标处移动
for(var j=0;j<data.length-i;j++){
if(data[j]>data[j+1]){
var temp=data[j+1];
data[j+1]=data[j];
data[j]=temp;
}
}
}
}
注意,使用分段,结合递归
/**
@data 目标排序数组
@start 分段开始
@end 分段结束
*/
function quickSort(data,start,end){
if(start<end){
var i=quickSortPartation(data,start,end);
//递归处理每一段
quickSort(data,start,i-1);
quickSort(data,i+1,end);
}
}
//进行一次快排
function quickSortPartation(data,start,end){
//定义第一个元素为快排标志位
var key=data[start];
while(start<end){
while(start<end && data[end]>=key){
end--;
}
//当小于标志位的元素向前置换
if(start<end){
data[start]=data[end];
start++;
}
while(start<end && data[start]<key){
start++;
}
if(start<end){
data[end]=data[start];
end--;
}
}
data[start]=key;
return start;
}
分享到:
相关推荐
GWT Advanced Table 是一个基于 GWT 框架的网页表格组件,可实现分页数据显示、数据排序和过滤等功能! Google Tag Library 该标记库和 Google 有关。使用该标记库,利用 Google 为你的网站提供网站查询,并且可以...
GWT Advanced Table 是一个基于 GWT 框架的网页表格组件,可实现分页数据显示、数据排序和过滤等功能! Google Tag Library 该标记库和 Google 有关。使用该标记库,利用 Google 为你的网站提供网站查询,并且可以...
与正则表达式相关的几个小工具 你真的了解.NET中的String吗? .NET中的方法及其调用(一) 如何判断ArrayList,Hashtable,SortedList 这类对象是否相等 帮助解决网页和JS文件中的中文编码问题的小工具 慎用const...
WDSsoft的一款免费源代码 JCT 1.0,它是一个Java加密解密常用工具包。 Java局域网通信——飞鸽传书源代码 28个目标文件 内容索引:JAVA源码,媒体网络,飞鸽传书 Java局域网通信——飞鸽传书源代码,大家都知道VB...
GWT Advanced Table 是一个基于 GWT 框架的网页表格组件,可实现分页数据显示、数据排序和过滤等功能! Google Tag Library 该标记库和 Google 有关。使用该标记库,利用 Google 为你的网站提供网站查询,并且可以...
WDSsoft的一款免费源代码 JCT 1.0,它是一个Java加密解密常用工具包。 Java局域网通信——飞鸽传书源代码 28个目标文件 内容索引:JAVA源码,媒体网络,飞鸽传书 Java局域网通信——飞鸽传书源代码,大家都知道VB...
GWT Advanced Table 是一个基于 GWT 框架的网页表格组件,可实现分页数据显示、数据排序和过滤等功能! Google Tag Library 该标记库和 Google 有关。使用该标记库,利用 Google 为你的网站提供网站查询,并且可以...
GWT Advanced Table 是一个基于 GWT 框架的网页表格组件,可实现分页数据显示、数据排序和过滤等功能! Google Tag Library 该标记库和 Google 有关。使用该标记库,利用 Google 为你的网站提供网站查询,并且可以...
GWT Advanced Table 是一个基于 GWT 框架的网页表格组件,可实现分页数据显示、数据排序和过滤等功能! Google Tag Library 该标记库和 Google 有关。使用该标记库,利用 Google 为你的网站提供网站查询,并且可以...
GWT Advanced Table 是一个基于 GWT 框架的网页表格组件,可实现分页数据显示、数据排序和过滤等功能! Google Tag Library 该标记库和 Google 有关。使用该标记库,利用 Google 为你的网站提供网站查询,并且可以...
GWT Advanced Table 是一个基于 GWT 框架的网页表格组件,可实现分页数据显示、数据排序和过滤等功能! Google Tag Library 该标记库和 Google 有关。使用该标记库,利用 Google 为你的网站提供网站查询,并且可以...
GWT Advanced Table 是一个基于 GWT 框架的网页表格组件,可实现分页数据显示、数据排序和过滤等功能! Google Tag Library 该标记库和 Google 有关。使用该标记库,利用 Google 为你的网站提供网站查询,并且可以...
GWT Advanced Table 是一个基于 GWT 框架的网页表格组件,可实现分页数据显示、数据排序和过滤等功能! Google Tag Library 该标记库和 Google 有关。使用该标记库,利用 Google 为你的网站提供网站查询,并且可以...
GWT Advanced Table 是一个基于 GWT 框架的网页表格组件,可实现分页数据显示、数据排序和过滤等功能! Google Tag Library 该标记库和 Google 有关。使用该标记库,利用 Google 为你的网站提供网站查询,并且可以...
GWT Advanced Table 是一个基于 GWT 框架的网页表格组件,可实现分页数据显示、数据排序和过滤等功能! Google Tag Library 该标记库和 Google 有关。使用该标记库,利用 Google 为你的网站提供网站查询,并且可以...
GWT Advanced Table 是一个基于 GWT 框架的网页表格组件,可实现分页数据显示、数据排序和过滤等功能! Google Tag Library 该标记库和 Google 有关。使用该标记库,利用 Google 为你的网站提供网站查询,并且可以...