/*
	Shell Sort 希尔排序
 */
function ShellSort(arr, comparator) {
	var increment = arr.length;
	do {
		increment = (increment / 3 | 0) + 1;
		arr = ShellPass(arr, increment, comparator);
	} while (increment > 1);
	return arr;
}

//希儿排序分段执行函数
function ShellPass(arr, d, comparator) {
	var temp, j;
	comparator = comparator || defaultComparator;
	for (var i = d; i < arr.length; i++) {
		if (comparator(arr[i], arr[i - d]) < 0) {
			temp = arr[i];
			j = i - d;
			do {
				arr[j + d] = arr[j];
				j = j - d;
			} while (j > -1 &&  (comparator(temp, arr[j]) < 0));
			arr[j + d] = temp;
		}
	}
	return arr;
}

/*
	默认比较器，只能比较数字类型的数据。或者支持减号（-）操作的对象
	v1 > v2 --> > 0
	v1 = v2 --> = 0
	v1 < v2 --> < 0
 */
function defaultComparator(v1, v2) {
	if (v1 == undefined && v2 != undefined)
		return -1;
	else if (v1 != undefined && v2 == undefined) {
		return 1;
	} else if (v1 == undefined && v2 == undefined) {
		return 0;
	}
	
	return (v1 - v2);
}