常用排序算法之归并排序和快速排序代码实例

常用排序算法之归并排序和快速排序代码实例

function ArrayList() {
	var arr = [];

	this.insert = function (value) {
		arr.push(value);
	}

	this.toString = function () {
		return arr.join(" ");
	}

	/*归并排序*/
	this.mergeSort = function () {
		arr = mergeSortRec(arr);
		return this;
	}

	function mergeSortRec(arr) {
		var len = arr.length;
		if(len == 1) {
			return arr;
		}

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

		return merge(mergeSortRec(left), mergeSortRec(right));
	}

	function merge(left, right) {
		var result = [],
			il = 0,
			ir = 0;

		while(il < left.length && ir 1) {
			index = partition(arr, left, right);

			if(left < index -1) {
				quick(arr, left, index - 1);
			}

			if(index < right) {
				quick(arr, index, right);
			}
		}
	}

	function partition(arr, left, right) {
		var pivot = arr[Math.floor((right + left) / 2)],
			i = left,
			j = right;

		while(i <= j) {
			while(arr[i] < pivot) {
				i++;
			}

			while(arr[j] > pivot) {
				j--;
			}

			if(i <= j) {
				swapQuickSort(arr, i, j);
				i++;
				j--;
			} 
		}
		return i;
	}

	function swapQuickSort(arr, index1, index2) {
		var temp = arr[index1];
		arr[index1] = arr[index2];
		arr[index2] = temp;
	}
}


function test() {
	//          0  1  2  3  4   5
	// len = 6
	var arr = [10, 2, 3, 7, 20, 4];
	var arr_list = new ArrayList();
	for(var i=0; i