冒泡排序

**冒泡排序(Bubble Sort)**是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

算法描述

• 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
• 针对所有的元素重复以上的步骤，除了最后一个；
• 重复步骤1~3，直到排序完成。

演示动画

代码实现

function bubbleSort(arr) {
	for(var i = 0; i < arr.length; i++) {
		for (var j= 0; j < arr.length-1-i; j++) {
			if (arr[j] > arr[j+1]) {
				var tmp = arr[j+1];
				arr[j+1] = arr[j];
				arr[j] = tmp;
			}
		}
	}
}

算法分析

最佳情况：T(n) = O(n) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)

选择排序

**选择排序(Selection Sort)**是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

算法描述

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

• 初始状态：无序区为R[1..n]，有序区为空；
• 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
• n-1趟结束，数组有序化了。

演示动画

代码实现

function selectionSort(arr) {
	for (var i=0; i < arr.length-1; i++) {
		var minIndex = i;
		for (var j=i; j < arr.length; j++) {
			if (arr[j] < arr[minIndex]) {
				minIndex = j;
			}
		}
		var tmp = arr[minIndex];
		arr[minIndex] = arr[i];
	 	arr[i] = tmp;
	}
}

算法分析

最佳情况：T(n) = O(n2) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)

插入排序

**插入排序(Insertion Sort)**的算法描述是一种简单直观的排序算法。如果有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。

算法描述

• 从第一个元素开始，该元素可以认为已经被排序；
• 取出下一个元素，在已经排序的元素序列中从后向前扫描；
• 如果该元素（已排序）大于新元素，将该元素移到下一位置；
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
• 将新元素插入到该位置后；
• 重复步骤2~5。

演示动画

代码实现

function insertionSort(arr) {
	var current;
	for (var i = 0; i < arr.length-1; i++) {
		current = arr[i+1];
		var preIndex = i;
		while (preIndex >= 0 && current < arr[preIndex]) {
			arr[preIndex+1] = arr[preIndex];
			preIndex--;
		}
		arr[preIndex+1] = current;
	}
}

算法分析

最佳情况：T(n) = O(n) 最坏情况：T(n) = O(n2) 平均情况：T(n) = O(n2)。

归并排序

**归并排序(Merge Sort)**是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

算法描述

• 把长度为n的输入序列分成两个长度为n/2的子序列；
• 对这两个子序列分别采用归并排序；
• 将两个排序好的子序列合并成一个最终的排序序列。

演示动画

代码实现

function mergeSort(arr) {
	return mergeSortRec(arr);
}

var mergeSortRec = function(arr) {
	if (arr.length == 1) return arr;
	var mid = Math.floor(arr.length/2);
	var left = arr.slice(0, mid);
	var right = arr.slice(mid, arr.length);

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

var merge = 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++]);
		} else {
			result.push(right[ir++]);
		}
	}

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

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

	return result;
}

算法分析

最佳情况：T(n) = O(n) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)

快速排序

**快速排序(Quick Sort)**的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

算法描述

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

• 从数列中挑出一个元素，称为 “基准”（pivot）；
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

演示动画

代码实现

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

	while(i <= j) {
		while (arr[i] < privot) {
			i++;
		}
		while (arr[j] > privot) {
			j--;
		}

		if (i <= j) {
			tmp = arr[i];
			arr[i] = arr[j];
			arr[j] = tmp;
			i++;
			j--;
		}
	}

	return i;
}

var quick = function(arr, left, right) {
	var index;
	if (arr.length > 1) {
		index = partition(arr, left, right);

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

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

function quickSort(arr) {
	quick(arr, 0, arr.length-1);
}

算法分析

最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(nlogn)

堆排序

**堆排序(Heap Sort)**是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

算法描述

• 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
• 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
• 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

演示动画

代码实现

var heapify = function(arr, heapSize, i) {
	var left = i*2+1, right = i*2+2, largest = i;

	if (left < heapSize && arr[left] > arr[largest]) {
		largest = left;
	}

	if (right < heapSize && arr[right] > arr[largest]) {
		largest = right;
	}

	if (largest != i) {
		var tmp = arr[largest];
		arr[largest]= arr[i];
		arr[i] = tmp;

		heapify(arr, heapSize, largest);
	}
}

var buildHeap = function(arr) {
	var heapSize = arr.length;
	for(var i = Math.floor(arr.length/2); i>=0; i--) {
		heapify(arr, heapSize, i);
	}
}

function heapSort(arr) {
	var heapSize = arr.length;
	buildHeap(arr);

	while(heapSize>1) {
		heapSize--;
		tmp = arr[heapSize];
		arr[heapSize] = arr[0];
		arr[0] = tmp;
		heapify(arr, heapSize, 0);
	}
}

算法分析

最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)