目录
排序算法是将一系列的值按照顺序进行排列的方法。
冒泡排序(Bubble Sort)是最易懂的排序算法,但是效率较低,生产环境中很少使用。
它的基本思想是:
由于每进行一次这个过程,在该次比较的最后一个位置上,正确的数会自己冒出来,就好像 "冒泡" 一样,这种算法因此得名。
以对数组 [3, 2, 4, 5, 1] 进行从小到大排序为例,步骤如下:
第一轮排序完成,可以看到最后一位的 5,已经是正确的数了。然后,再对剩下的数 [2, 3, 4, 1] 重复这个过程,每一轮都会在本轮最后一位上出现正确的数。直至剩下最后一个位置,所有排序结束。
先定义一个交换函数,作用是交换两个位置的值。
- function swap(myArray, p1, p2){
- var temp = myArray[p1];
- myArray[p1] = myArray[p2];
- myArray[p2] = temp;
- }
然后定义主函数。
- function bubbleSort(myArray){
- var len = myArray.length;
- var i;
- var j;
- var stop;
- for (i = 0; i < len - 1; i++){
- for (j = 0, stop = len - 1 - i; j < stop; j++){
- if (myArray[j] > myArray[j + 1]){
- swap(myArray, j, j + 1);
- }
- }
- }
- return myArray;
- }
选择排序(Selection Sort)与冒泡排序类似,也是依次对相邻的数进行两两比较。不同之处在于,它不是每比较一次就调换位置,而是一轮比较完毕,找到最大值(或最小值)之后,将其放在正确的位置,其他数的位置不变。
以对数组 [3, 2, 4, 5, 1] 进行从小到大排序为例,步骤如下:
这一轮比较结束后,最小值 "1" 已经排到正确的位置了,然后对剩下的 [2, 4, 5, 3] 重复上面的过程。每一轮排序都会将该轮的最小值排到正确的位置,直至剩下最后一个位置,所有排序结束。
先定义一个交换函数。
- function swap(myArray, p1, p2){
- var temp = myArray[p1];
- myArray[p1] = myArray[p2];
- myArray[p2] = temp;
- }
然后定义主函数。
- function selectionSort(myArray){
- var len = myArray.length,
- min;
- for (i=0; i < len; i++){
- // 将当前位置设为最小值
- min = i;
- // 检查数组其余部分是否更小
- for (j=i+1; j < len; j++){
- if (myArray[j] < myArray[min]){
- min = j;
- }
- }
- // 如果当前位置不是最小值,将其换为最小值
- if (i != min){
- swap(myArray, i, min);
- }
- }
- return myArray;
- }
插入排序(insertion sort)比前面两种排序方法都更有效率。它将数组分成 "已排序" 和 "未排序" 两部分,一开始的时候,"已排序" 的部分只有一个元素,然后将它后面一个元素从 "未排序" 部分插入 "已排序" 部分,从而 "已排序" 部分增加一个元素,"未排序" 部分减少一个元素。以此类推,完成全部排序。
以对数组 [3, 2, 4, 5, 1] 进行从小到大排序为例,步骤如下:
算法的实现如下:
- function insertionSort(myArray) {
- var len = myArray.length, // 数组的长度
- value, // 当前比较的值
- i, // 未排序部分的当前位置
- j; // 已排序部分的当前位置
- for (i=0; i < len; i++) {
- // 储存当前位置的值
- value = myArray[i];
- /*
- * 当已排序部分的当前元素大于value,
- * 就将当前元素向后移一位,再将前一位与value比较
- */
- for (j=i-1; j > -1 && myArray[j] > value; j--) {
- myArray[j+1] = myArray[j];
- }
- myArray[j+1] = value;
- }
- return myArray;
- }
前面三种排序算法只有教学价值,因为效率低,很少实际使用。合并排序(Merge sort)则是一种被广泛使用的排序方法。
它的基本思想是,将两个已经排序的数组合并,要比从头开始排序所有元素来得快。因此,可以将数组拆开,分成 n 个只有一个元素的数组,然后不断地两两合并,直到全部排序完成。
以对数组 [3, 2, 4, 5, 1] 进行从小到大排序为例,步骤如下:
这里的关键是如何合并两个已经排序的数组。具体实现请看下面的函数。
- function merge(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++]);
- }
- }
- return result.concat(left.slice(il)).concat(right.slice(ir));
- }
上面的 merge 函数,合并两个已经按升序排好序的数组。首先,比较两个数组的第一个元素,将其中较小的一个放入 result 数组;然后,将其中较大的一个与另一个数组的第二个元素进行比较,再将其中较小的一个放入 result 数组的第二个位置。以此类推,直到一个数组的所有元素都进入 result 数组为止,再将另一个数组剩下的元素接着 result 数组后面返回(使用 concat 方法)。
有了 merge 函数,就可以对任意数组排序了。基本方法是将数组不断地拆成两半,直到每一半只包含零个元素或一个元素为止,然后就用 merge 函数,将拆成两半的数组不断合并,直到合并成一整个排序完成的数组。
- function mergeSort(myArray){
- if (myArray.length < 2) {
- return myArray;
- }
- var middle = Math.floor(myArray.length / 2),
- left = myArray.slice(0, middle),
- right = myArray.slice(middle);
- return merge(mergeSort(left), mergeSort(right));
- }
上面的代码有一个问题,就是返回的是一个全新的数组,会多占用空间。因此,修改上面的函数,使之在原地排序,不多占用空间。
- function mergeSort(myArray){
- if (myArray.length < 2) {
- return myArray;
- }
- var middle = Math.floor(myArray.length / 2),
- left = myArray.slice(0, middle),
- right = myArray.slice(middle),
- params = merge(mergeSort(left), mergeSort(right));
- // 在返回的数组头部,添加两个元素,第一个是0,第二个是返回的数组长度
- params.unshift(0, myArray.length);
- // splice用来替换数组元素,它接受多个参数,
- // 第一个是开始替换的位置,第二个是需要替换的个数,后面就是所有新加入的元素。
- // 因为splice不接受数组作为参数,所以采用apply的写法。
- // 这一句的意思就是原来的myArray数组替换成排序后的myArray
- myArray.splice.apply(myArray, params);
- // 返回排序后的数组
- return myArray;
- }
快速排序(quick sort)是公认最快的排序算法之一,有着广泛的应用。
它的基本思想很简单:先确定一个 "支点"(pivot),将所有小于 "支点" 的值都放在该点的左侧,大于 "支点" 的值都放在该点的右侧,然后对左右两侧不断重复这个过程,直到所有排序完成。
具体做法是:
以对数组 [3, 2, 4, 5, 1] 进行从小到大排序为例,步骤如下:
首先部署一个 swap 函数,用于互换两个位置的值。
- function swap(myArray, firstIndex, secondIndex){
- var temp = myArray[firstIndex];
- myArray[firstIndex] = myArray[secondIndex];
- myArray[secondIndex] = temp;
- }
然后,部署一个 partition 函数,用于完成一轮排序。
- function partition(myArray, left, right) {
- var pivot = myArray[Math.floor((right + left) / 2)],
- i = left,
- j = right;
- while (i <= j) {
- while (myArray[i] < pivot) {
- i++;
- }
- while (myArray[j] > pivot) {
- j--;
- }
- if (i <= j) {
- swap(myArray, i, j);
- i++;
- j--;
- }
- }
- return i;
- }
接下来,就是递归上面的过程,完成整个排序。
- function quickSort(myArray, left, right) {
- if (myArray.length < 2) return myArray;
- left = (typeof left !== "number" ? 0 : left);
- right = (typeof right !== "number" ? myArray.length - 1 : right);
- var index = partition(myArray, left, right);
- if (left < index - 1) {
- quickSort(myArray, left, index - 1);
- }
- if (index < right) {
- quickSort(myArray, index, right);
- }
- return myArray;
- }
来源: http://www.open-open.com/lib/view/open1488254629635.html