function CArray(numElements) {
	this.dataStore = [];
	this.pos = 0;
	this.numElements = numElements;
	this.insert = insert;
	this.toString = toString;
	this.clear = clear;
	this.setData = setData;
	this.swap = swap;
	this.bubbleSort = bubbleSort;  //  冒泡排序
	this.selectionSort = selectionSort;  // 选择排序
	this.insertSort = insertSort;  //插入排序
	this.shellSort = shellSort;  //希尔排序
	this.shellSortAutoCaclPart = shellSortAutoCaclPart;  //希尔排序，自动计算间隔
	this.mergeArrays = mergeArrays;  //
	this.mergeSort = mergeSort;  // 归并排序
	this.gaps = [5, 3, 1];  // 希尔排序的间隔序列
	//  默认初始化数据
	for (var i = 0; i < this.numElements; i++) {
		this.dataStore[i] = i;
	}
}

function setGaps(arr) {
	this.gaps = arr;
}

function setData() {
	for (var i = 0; i < this.numElements; i++) {
		this.dataStore[i] = Math.floor(Math.random() * (this.numElements + 1));
	}
}

//  清空其实只是全部置为 0
function clear() {
	for (var i = 0; i < this.numElements; i++) {
		this.dataStore[i] = 0;
	}
}

function insert(e) {
	this.dataStore[this.pos++] = e;
}

function toString() {
	var retStr = "";
	for (var i = 0; i < this.dataStore.length; i++) {
		retStr += this.dataStore[i] + " ";
		if (i > 0 & i % 10 == 0) {
			retStr += "\n";
		}
	}

	return retStr;
}

function swap(arr, index1, index2) {
	var tmp = arr[index1];
	arr[index1] = arr[index2];
	arr[index2] = tmp;
}

//  计算算法执行的时间
// var start = new Date().getTime();

// 冒泡排序
function bubbleSort() {
	var e = this.dataStore.length;
	// var tmp = 0;
	for (var i = e; i >= 2; i--) {
		for (var j = 0; j <= i - 1; j++) {
			if (this.dataStore[j] > this.dataStore[j+1]) {
				swap(this.dataStore, j, j+1);
			}
		}
		print(this.toString());
	}
}
// print("算法执行的时间：" + (new Date().getTime()-start));



/**
 * 选择排序，选择排序从数组的头开始，将第一个元素和其他元素比较， 
 * 检查完所有元素后,最小的元素会被放到数组的第一个位置,然后算法会从 第二个位置继续。
 * 这个过程一直进行,当进行到数组的倒数第二个位置时,所有的数据便 完成了排序。
 */
function selectionSort() {
	var min, tmp;
	for (var outer = 0; outer <= this.dataStore.length-2; ++outer) {
		min = outer;
		for (var inner = outer + 1; inner <= this.dataStore.length-1; ++inner) {
			if (this.dataStore[inner] < this.dataStore[min]) {
				min = inner;
			}
			swap(this.dataStore, outer, min);
		}
		print(this.toString());
	}
}

/** 
 * 自己根据思路编写的选择排序算法
 */
function my_selectorSort() {
	for (var i = 0; i < arr.length-1; i++) {
		tmp = arr[i];
		var flag = false;
		for(var j = i+1; j < arr.length; j++) {
			if (tmp > arr[j]) {
				tmp = arr[j];
				minIndex = j;
				flag = true;  //
			}
		}
		if (flag) {  //  只有出现后面数据比前面的大才调换
			//  调换最小值到第i 位置
			arr[minIndex] = arr[i];  
			arr[i] = tmp;
		}
		
		print(arr.toString());
	}
}



/** 
 * 插入排序
 */
function insertSort() {
	var tmp, inner;
	for (var i = 1; i <= this.dataStore.length; i++) {
		tmp = this.dataStore[i];
		inner = i;
		while (inner > 0 && this.dataStore[inner-1] >= tmp) {
			this.dataStore[inner] = this.dataStore[inner-1];
			inner--;
		}
		this.dataStore[inner] = tmp;
		print(this.toString());
	}
}

/** 
 * 希尔排序
 */
function shellSort() {
	var start = new Date().getTime();

	// setGaps(new Array(5, 3, 1));
	for (var g = 0; g < this.gaps.length; g++) {  //  比较的序列间隔
		for (var i = this.gaps[g]; i < this.dataStore.length; i++) {  //从序列间隔大的开始
			var tmp = this.dataStore[i];  //
			for (var j = i; 
				j >= this.gaps[g] && this.dataStore[j-this.gaps[g]] > tmp; 
				j -= this.gaps[g]) {  //  遍历的步幅与序列间隔一致
				this.dataStore[j] = this.dataStore[j-this.gaps[g]];
			}
			//  为了便于理解把 if 拆开
			// var j = i;
			// if (this.dataStore[j-this.gaps[g]] > tmp) {
			// 	for (; j >= this.gaps[g]; j -= this.gaps[g]) {  //  遍历的步幅与序列间隔一致
				
			// 		this.dataStore[j] = this.dataStore[j-this.gaps[g]];
			// 	}
			// }
			this.dataStore[j] = tmp; // 后面的比前面的大不用调换 	
		}		

		// print(this.dataStore);
	}
	print("算法执行的时间：" + (new Date().getTime()-start));
}


function shellSortAutoCaclPart() {
    var N = this.dataStore.length;
    var h = 1;
    while (h < N/3) {  // 计算分隔的间隔
		h = 3 * h + 1; 
	}
    while (h >= 1) {
       for (var i = h; i < N; i++) {
          for (var j = i; j >= h && this.dataStore[j] < this.dataStore[j-h];
               j -= h) {
             swap(this.dataStore, j, j-h);
          }
      }
	}
	h = (h-1)/3;
}


/**
 * 归并排序
 */
function mergeSort2(arr) {
	if (arr.length < 2)
		return;

	var step = 1;
	var left, right;
	while (step < arr.length) {
		left = 0;
		right = step;
		while (right + step <= arr.length) {
			mergeArrays(arr, left, left+step, right, right+step);
			left = right + step;
			right = left + step;
		}
		if (right < arr.length) {
			mergeArrays(arr, left, left+step, right, arr.length);
		}
		step *= 2;
	}
}
function mergeSort() {
	if (this.dataStore.length < 2)
		return;

	var step = 1;
	var left, right;
	while (step < this.dataStore.length) {
		left = 0;
		right = step;
		while ((right + step) <= this.dataStore.length) {
			mergeArrays(this.dataStore, left, left+step, right, right+step);
			left = right + step;
			right = left + step;
		}
		if (right < this.dataStore.length) {
			mergeArrays(this.dataStore, left, left+step, right, this.dataStore.length);
			step *= 2;
		}
	}
}
function mergeArrays(arr, startLeft, stopLeft, startRight, stopRight) {
	var rightArr = new Array(stopRight-startRight+1);
	var leftArr = new Array(stopLeft-startLeft+1);
	var k = startRight;
	for (var i = 0; i < (rightArr.length-1); i++) {
		leftArr[i] = arr[k];
		k++;
	}
	k = startLeft;
	for (var i = 0; i < (leftArr.length-1); i++) {
		leftArr[i] = arr[k];
		k++;
	}
	rightArr[rightArr.length-1] = Infinity;  //哨兵值
	leftArr[leftArr.length-1] = Infinity;  //哨兵值
	var m = 0;
	var n = 0;
	for (var k = startLeft; k < stopRight; k++) {
		if (leftArr[m] <= rightArr[n]) {
			arr[k] = leftArr[m];
			m++;
		} else {
			arr[k] = rightArr[n];
			n++;
		}
	}
	print("left array - ", leftArr);
	print("right array - ", rightArr);
}

/*
快速排序是处理大数据集最快的排序算法之一。它是一种分而治之的算法,通过递归的方 式将数据依次分解为包含较小元素和较大元素的不同子序列。该算法不断重复这个步骤直 到所有数据都是有序的。
这个算法首先要在列表中选择一个元素作为基准值(pivot)。数据排序围绕基准值进行, 将列表中小于基准值的元素移到数组的底部,将大于基准值的元素移到数组的顶部。
*/
function qSort(arr) {
	if (0 == arr.length) {
		return [];
	}

	var left = [];
	var right = [];
	var pivot = arr[0];
	for (var i = 1; i < arr.length; i++) {
		if (arr[i] < pivot) {
			left.push(arr[i]);
		} else {
			right.push(arr[i]);
		}
	}

	return qSort(left).concat(pivot, qSort(right));  //递归调用
}

// var a = [];
// for (var i = 0; i < 100; ++i) {
// 	a[i] = Math.floor((Math.random()*100)+1); 
// }
// print(a);
// print();
// print(qSort(a));

/*
 * 二分查找
*/
function binSearch(arr, data) {
	var upperBound = arr.length - 1;
	var lowerBound = 0;
	while (lowerBound <= upperBound) {
		var mid = Math.floor((upperBound + lowerBound) / 2);
		if (arr[mid] > data) {
			upperBound = mid - 1;
		} else if (arr[mid] < data) {
			lowerBound = mid + 1;
		} else {
			return mid;  // 返回匹配元素的位置
		}
	}

	return -1;  //表示元素不存在
}


/**
 * 动态规划解决背包问题
 */
function max(a, b) {
	return (a > b) ? a : b;
}
function dKnapsack(capacity, size, value, n) {
	var k = [];  //定义一个多维数组，并初始化为空
	for (var i = 0; i <= capacity; i++) {
		k[i] = [];
	}
	for (var i = 0; i <= n; i++) {
		for (var w = 0; w <= capacity; w++) {
			if (0 == i || 0 == w) {
				k[i][w] = 0;
			} else if (size[i - 1] <= w) {
				k[i][w] = max(value[i - 1] + k[i - 1][w - size[i - 1]], k[i - 1][w]);
			} else {
				k[i][w] = k[i - 1][w];
			}
			putstr(k[i][w] + " ");
		}
		print();
	}
	return k[n][capacity];
}
var value = [4,5,10,11,13];
var size = [3,4,7,8,9];
var capacity = 16;
var n = 5;
print(dKnapsack(capacity, size, value, n));
print("dKnapsack(e, size, value, n)");

/**
 * 贪心算法案例:找零问题
 */
function makeChange(ora, coins) {
	var remainAmt = 0;
	if (ora % 0.25 < ora) {
		coins[3] = parseInt(ora / .25);
		remainAmt = ora % .25;
		ora = remainAmt;
	}
	if (ora % .1 < ora) {
		coins[2] = parseInt(ora / .1);
		remainAmt = ora % .1;
		ora = remainAmt;
	}
	if (ora % .05 < ora) {
		coins[1] = parseInt(ora / .05);
		remainAmt = ora % .05;
		ora = remainAmt;
	}
	coins[0] = parseInt(ora / .01);
}
function showChange(coins) {
        if (coins[3] > 0) {
print("25 美分的数量 - " + coins[3] + " - " + coins[3] * .25); }
if (coins[2] > 0) {
print("10 美分的数量 - " + coins[2] + " - " + coins[2] * .10);
        }
        if (coins[1] > 0) {
print("5 美分的数量 - " + coins[1] + " - " + coins[1] * .05); }
if (coins[0] > 0) {
print("1 美分的数量 - " + coins[0] + " - " + coins[0] * .01);
} }
 var origAmt = .63;
 var coins = [];
 makeChange(origAmt, coins);
 showChange(coins);


/**
 * 背包问题的贪心算法解决方案
 */
function ksack(values, weights, capacity) {
	var load = 0;
	var i = 0;
	var w = 0;
	while (load < capacity && i < 4) {
		if (weights[i] < (capacity - load)) {
			w += values[i];
			load += weights[i];
		} else {
			var r = (capacity - load) / weights[i];
			w += r * values[i];
			load += weights[i];
		}
		i++;
	}
	return w;
}

var items = ['A', 'B', 'C', 'D'];
var values = [50, 140, 60, 60];
var weights = [5, 20, 10, 12];
var capacity = 30;
print(ksack(values, weights, capacity));