javaScript排序算法学习笔记

// 用于创建数组
function createNonSortedArray(size) {
	var array = new ArrayList();
	for (var i = size; i > 0; i--) {
		array.insert(i);
	}
	return array;
}

function ArrayList() {
	var array = [];

	this.insert = function(item) {
		console.log(item, 'insert');
		array.push(item);
	};

	this.toString = function() {
		console.log('tostring');
		return array.join();
	};
	/*
	 * 冒泡排序
	 * 冒泡排序比较任何两个相邻的项，如果第一个比第二个大，则交换它们。
	 * 元素项向上移动至正确的顺序，就好像气泡升至表面一样，冒泡排序因此得名。
	 * 第一轮比过之后最后一个就一定是最大的 无需再比较。所以下次要 - i
	 */

	this.bubbleSort = function() {
		var length = array.length;
		for (var i = 0; i < length; i++) {
			for (var j = 0; j < length - 1 - i; j++) {
				if (array[j] > array[j + 1]) {
					swap(array, j, j + 1);
				}
			}
		}
	};

	/*
	 * 选择排序
	 * 选择排序算法是一种原址比较排序算法。选择排序大致的思路是找到数据结构中的最小值
	 * 并将其放置在第一位，接着找到第二小的值并将其放在第二位，以此类推。比如，第一个
	 * 的时候，会遍历后面所有想跟其比较，找到最小的更其交换。所以第一个此时一定是最小的。
	 * 随意第二个的时候，只会循环后面的几个。如果找到一个比第二个更小的，那么交换位置。
	 */

	this.selectionSort = function() {
		var length = array.length,
			indexMin;
		for (var i = 0; i < length - 1; i++) {
			indexMin = i;
			for (var j = i; j < length; j++) {
				if (array[indexMin] > array[j]) {
					indexMin = j;
				}
			}
			if (i !== indexMin) {
				swap(array, i, indexMin);
			}
		}
	};

	/*
	 * 插入排序
	 * 插入排序每次排第一个数组项，以此方式构建最后的排序数组。假定第一项已经排序了，接着，
	 * 它和第二项进行比较，第二项是应该待在原位还是插到第一项之前呢？这样，头两项就已正确
	 * 排序，接着和第三项比较（它是该插入到第一、第二还是第三位置呢？），以此类推。
	 * 简而言之，就是遍历数组的每一项，拿这一项去跟前面的项比较，如果比他小就插入到它前面。
	 */

	this.insertionSort = function() {
		var length = array.length,
			j,
			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;
		}
	};

	// 归并排序
	// 归并排序是一种分治算法。其思想是将原始数组切分成较小的数组，直到每个
	// 小数组只有一个位置，接着将小数组归并成较大的数组，直到最后一个排序完毕的大数组。
	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 merge(mergeSortRec(left), mergeSortRec(right));
	};

	var merge = function(left, right) {
		var result = [],
			il = 0,
			ir = 0;
		// 完成下列操作的前提是left、right数组均已经完成。所以采用递归的形式
		// 在数组长度为1的时候先开始排序，然后在通过merge left与right数组
		while (il < left.length && ir < right.length) {
			if (left[il] < right[ir]) {
				result.push(left[il++]);
			} else {
				result.push(right[ir++]);
			}
		}
		// 上面是将left与right数组排完序，那么其中之一数组必然为空，
		// 下面的操作就是将剩下的right或者left全部推入result数组中
		while (il < left.length) {
			result.push(left[il++]);
		}

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

		return result;
	};

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

	// 简而言之，先分治，不断的细化下去，到最后一个数组无法再交换位置进行排序位置
	this.quickSort = function() {
		quick(array, 0, array.length - 1);
	};

	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);
			}
		}
	};

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

		while (i <= j) {
			while (array[i] < pivot) {
				i++;
			}
			while (array[j] > pivot) {
				j--;
			}
			if (i <= j) {
				swap(array, i, j);
				i++;
				j--;
			}
		}

		return i;
	};

	var swap = function(array, index1, index2) {
		var aux = array[index1];
		array[index1] = array[index2];
		array[index2] = aux;
	};
}

var array = createNonSortedArray(9);
console.log(array.toString());
array.bubbleSort();
// array.selectionSort();
// array.insertionSort();
// array.mergeSort();
// array.quickSort();
console.log(array.toString());