Javascript排序与查找 #10
Description
排序
Javascript除了系统默认排序sort()方法外，常用的排序方法还有 直接插入排序，希尔排序，选择排序，冒泡排序和快速排序。其中前两种都属于 插入排序，希尔排序是在直接插入排序的基础上演变的;而后者冒泡排序和快速排序都属于 交换排序。
希尔排序和快速排序略微复杂，由于算法相差很大倒是很容易区分，反倒是直接插入排序，选择排序和冒泡排序容易搞迷糊。实际上要区分这三种排序方法还是蛮简单的，就得 咬文嚼字。冒泡排序属于交换排序重在相邻两对象位置的交换选出最大的沉到最后;选择排序则是从待选数组中选出最大或者最小的对象后同待选数组中第一位进行交换；而插入排序则强调将当前对象插入到已排好顺序数组的适当位置，具体区别如下:
- 冒泡排序的思想为：每一次排序过程，通过相邻元素的交换，将当前没有排好序中的最大（小）移到数组的最右（左）端。
- 选择排序的思想也很直观：每一次排序过程，我们获取当前没有排好序中的最大（小）的元素和数组最右（左）端的元素交换，循环这个过程即可实现对整个数组排序。
- 插入排序思想：和前面已排好的序列中每个元素的对比，插入到合适的位置，对比过程中将两者中大的向后移动。
这三种排序算法代码如下：
冒泡排序
function bubbleSort(arr){
var length = arr.length;
for(var i = 0;i < length;i++){
var left = length - i;
for(var j = 0;j<left-1;j++){
var temp = arr[j];
if(temp > arr[j+1]){
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr;
}
选择排序
function selectSort(arr){
var length = arr.length;
for(var i = 0;i<length;i++){
var j = i,base = arr[j],index = j;
while(j<length-1){
if(base > arr[j+1]){
base = arr[j+1];
index = j+1;
}
j++;
}
arr[index] = arr[i];
arr[i] = base;
}
return arr
}
直接插入排序
//参数d是为希尔排序准备的，默认d为1
function insertSort(arr,d){
var length = arr.length,d = !d?1:d;
for(var i = d;i < length;i += d){
var temp = arr[i];
if(temp < arr[i-d]){
var j = i - d;
while(j >= 0 && temp < arr[j]){
arr[j+d] = arr[j];
j -= d;
}
arr[j+d] = temp;
}
}
return arr;
}
希尔排序属于插入排序，是直接插入排序的改进。通过选择小于n的一个数d作为增量，将相隔距离为d的对象放入一个数组中进行直接插入排序，然后减小增量d的值重复上面操作，直到d为1。一般情况下，取d = n/2,要保证结果为奇数，如果是偶数则加1。具体算法：
function shellSort(arr){
var d = parseInt(arr.length/2);
while(d != 0){
d = (d%2 == 0?d+1:d);
insertSort(arr,d);
d = parseInt(d/2);
}
return arr;
}
快速排序是一个比较典型的排序算法，属于交换排序。和希尔排序一样，它通过分治法将数组拆分，然后排序。基本思想是：从待排序的数组中选择一个对象作为基准将数组分成两组，左边的小于改对象，右边全部大于改对象。然后递归的将拆分后的数组递归的重复上面的操作。一般情况下，会选第一个作为基准，然后通过和最后一个进行对比，如果大于最后一个对象就交换位置开始和前面第二个对比，否则位置不变继续和倒数第二个对比，依次类推。具体算法：
function quickSort(arr,l,h){
var l = (!l?0:l),h = (!h?arr.length - 1:h),base;
if(l < h){
var i = l,j = h,base = arr[i];
while(i != j){
while(i != j && arr[j] >= base) j--;
if(i != j) arr[i++] = arr[j];
while(i != j && arr[i] <= base) i++;
if(i != j) arr[j--] = arr[i];
}
arr[i] = base;
if(l < i-1) quickSort(arr,l,i-1);
if(i+1 < h) quickSort(arr,i+1,h);
}else{
return;
}
return arr;
}
注：所有排序源码可查看SORT.js:https://github.com/abcrun/sack.git
查找
ECMAScript 5中新增了两个方法： indexOf(),lastIndexOf()可以用来数组的查找，但是之前的标准却不支持查找。实际上查找的对象的过程相比排序还是简单一点的，Javascript中常用的查找方法可以分为：顺序查找，二分法查找和分块查找。
顺序查找很简单，顾名思义就是按照顺序依次对比。二分法查找又称折半查找，效率较高但是有个前提就是当前数组是一个 有序的队列，基本思路：查找当前数组的中间位置的对象进行对比，如果小则取右边区间中间位置的对象再次进行对比，如此递归直到查到或者查无结果为止。分块排序查找性能介于顺序查找和二分法查找之间，基本算法：首先将数组分成b块，然后取每块的最大对象按索引(1->b)构成一个索引表，这里虽然不要求数组为有序队列，但是却要求前一块的最大值必须小于后一块的最小值，所以索引表是个有序表，可以通过顺序查找或者二分法查找查找 待查对象 在索引表的位置，然后按索引找出对应的块数组，通过 顺序查找 算法找出位置（注：这时不能用二分法查找，因为之前说了，数组并非是有序的）。
二分法查找
//假设arr是有序队列
function dichotomySearch(arr,data){
var low = 0,high = arr.length - 1,mid;
while(low <= high){
//Optimize By @fhefh2015
if (arr[low] == data) return low;
if (arr[high] == data) return high;
var tmp;
mid = Math.ceil((low + high)/2);
tmp = arr[mid];
if(tmp == data) return mid;
else if(tmp < data) low = mid + 1;
else high = mid - 1;
}
return null;
}