排序和搜索 | zbs's Blog

排序和搜索算法

用来表示待排序和搜索的数据结构

function ArrayList () {
  	var array = [];
  
  	this.insert = function ( item ) {
      	array.push ( item );
  	} ;
  	
  	this.toString = functin () {
      	return array.join ();
  	};
}

插入排序

原理

每次排一个数组项，以此方式构建组后的排序数组
假定第一项已经排序了，接着，它和第二项进行比较
第二项是应该呆在原位还是插入到第一项之前呢？这样，头两项就已正确排序了
接着，和第三项比较（它是改插入到第一、第二还是第三的位置呢？），以此类推

this.insertionSort = function () {
	var length = array.length;
	var j;
	var temp;

	for ( var i = 1; i < length; i++ ) {
		j = i;
		temp = array[i];

		while ( j > 0 && array[j - 1] > temp ) {
			array[j] = array[j - 1];
			j-- ;
		}
		
		array[j] = temp ;
	}
};

归并排序

是第一个可以被实际使用的排序算法

归并排序性能不错，复杂度为 O(nlogn)

归并排序是一种分治算法。

其思想是将原始数组切分成较小数组，直到每个小数组只有一个位置，接着将小数组归并成较大的数组,直到最后只有一个排序完毕的大数组。

this.mergeSort = function () {
	array = mergeSortRec (array);
};
	
// 辅助函数
var mergeSortRec = function (array) {
	var length = array.length;

	if ( length === 1 ) {
		return array;
	}

	var mid = Math.floor ( length/2 ),
		left = array.slice ( 0, mid ),
		right = array.slice ( mid, length );

	return merger( mergeSortRec(left), mergeSortRec(right) );
} ;
	
// 辅助函数
var merger = function(left, right) {
	var result = [],
		il = 0,
		ir = 0;

	while ( il < left.length && ir < right.length ) {

		if ( left[il] < right[ir] ) {
			result.push( left[il] );
			il++;
		}
		else {
			result.push( right[ir] );
			ir++;
		}
	}

	while ( il < left.length ) {
		reult.push( left[il] );
		il++;
	}

	while ( ir < right.length ) {
		resule.push( right[ir] );
		ir++;
	}

	return result;
} ;

快速排序

复杂度为 O(nlogn)，且它的性能通常比其他的复杂度为 O(nlogn) 的排序算法要好

使用分治的方法，将原始数组分为较小的数组（但没有像归并排序那样将它们分割开）

步骤

从数组中选择中间一项作为主元
创建两个指针，
- 左边一个指向数组的第一个项
- 右边一个指向数组最后一个项。
- 移动左指针指到找到一个比主元大的元素
- 接着，移动右指针直到找到一个比主元小的元素
- 然后，交换它们
- 重复这个过程，直到左指针超过了右指针
- 这个过程将使得比主元小的值都排在主元之前，而比主元大的值将都排在主元之后。这一步叫做划分操作。
接着，算法对划分后的小数组（较主元小的值组成的子数组，以及较主元大的值组成的子数组）重复之前的两个步骤，直至数组已完全排序。

this.quickSort = function ( ) {
	quick( array, 0, array.length - 1 );
} ;
      
// 辅助函数 quick
var quick = function ( array, left, right ) {
	
	var index;
	
	if ( array.length > 1 ) {
		index = partition ( array, left, right );
		
		if ( left < index - 1) {
			quick ( array, left, index - 1 );
		}
		
		if ( index < right ) {
			quick ( array, index, right );
		}
	}
} ;
      
// 辅助函数 partition
// 第一件要做的事情是选择主元（pivot）
// 有好几种方式
// 最简单的一种是选择数组的第一项（最左项）。
// 然而，研究表明对于几乎已排序的数组，这不是好的选择，它将导致该算法的最差表现
// 另一种方式是随机选择一个数组项或者是选择中间项。
// 本实例中，选择中间项作为主元。
// 初始化两个指针：
	// left （低），初始化为数组第一个元素；
	// right（高），初始化为数组最后一个元素
// 只要 left 和 right 指针没有相互交错，就执行划分操作。
// 首先，移动 left 指针，直到找到一个元素比主元大
// 对 right 指针，做同样的事情，移动 right 指针，直到找到一个比主元小的元素
// 当左指针指向的元素比主元大，且右指针指向的元素比主元小，并且此时左指针索引没有右指针索引大，意思是左项比右项大（值比较）。交换它们，然后移动两个指针，并且重复此过程
// 在划分操作结束后，返回左指针的索引，用来创建子数组。
var partition = function ( array, left, right ) {
	
	var pivot = array[ Math.floor( ( right + left )/2 ) ],
		i = left,
		j = right;
	
	while ( i <= j ) {
		while ( array [ i ] < pivot ){
			i++;
		}
		while ( array [ j ] > pivot ) {
			j-- ;
		}
		if ( i <= j ) {
			swapQuickStort ( array, i, j ) ;
			i++ ;
			j--;
		}
	}
	return i ;
} ;
  	
// 辅助函数 swapQuickStort
var swapQuickStort = function ( array, index1, index2) {
	var aux = array[index1];
	array[index1] = array[index2];
	array[index2] = aux;
} ;

顺序搜索

this.sequentialSearch = function ( item ) {
	var i = 0,
		len = array.length;

	for ( var i = 0; i < len; i++ ) {
		if ( item === array[i] ) {
			return i;
		}
	}

	return -1;
};

二分搜索

要求被搜索的数据结构已排序

步骤

选择数组的中间值
如果选中值是待搜索值，那么算法执行完毕（值找到了）
如果待搜索值比选中值小，则返回步骤 1 并在选中值左边的子数组中寻找
如果待搜索值比选中值要大，则返回步骤 1 并在选中值右边的子数组中寻找

this.binarySearch = function ( item ) {
	this.quickSort();
	
	var low = 0,
		high = array.length - 1,
		mid, 
		element;
	
	while ( low <= high ) {
		mid = Math.floor ( low + high );
		element = array[mid];

		if ( element < item ) {
			low = mid + 1 ;
		}
		else if ( elememt > item ) {
			high = mid - 1;
		}
		else {
			return mid;
		}
	}

	return -1;
};