前端常用排序算法

1.时间复杂度

• n*n：冒泡排序、选择排序、插入排序
• nlogn：快速排序、归并排序、堆排序

2.冒泡排序

• 定义：每次都是相邻元素比较，第一个元素比第二个元素大则交换位置直到最后一个元素为最大，继续循环
• 代码实现：

function bubbleSort(arr) {var len = arr.length;for (var i = 0; i < len - 1; i++) {for (var j = 0; j < len - 1 - i; j++) {if (arr[j] > arr[j+1]) {        // 相邻元素两两对比var temp = arr[j+1];        // 元素交换arr[j+1] = arr[j];arr[j] = temp;}}}return arr;
}

3.选择排序

• 定义：遍历未排序数组找出最小元素放到未排序数组的起始位置
• 代码实现：

function selectionSort(arr) {var len = arr.length;var minIndex, temp;for (var i = 0; i < len - 1; i++) {minIndex = i;for (var j = i + 1; j < len; j++) {if (arr[j] < arr[minIndex]) {     // 寻找最小的数minIndex = j;                 // 将最小数的索引保存}}temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}return arr;

4.插入排序

• 定义：遍历未排序数组，将未排序元素与排序数组逐个比较，插入到对应位置
• 代码实现：

function insertionSort(arr) {var len = arr.length;var preIndex, current;for (var i = 1; i < len; i++) {preIndex = i - 1;current = arr[i];while (preIndex >= 0 && arr[preIndex] > current) {arr[preIndex + 1] = arr[preIndex];    // 数组往前移preIndex--;                           // 获取数组下标}arr[preIndex + 1] = current;}return arr;
}

5.归并排序

• 定义：利用递归的思想，数组不断拆分成小数组，小数组内部排序完成返回有序数组，根据返回结果递归形成完整有序数组
• 代码实现：

function mergeSort(arr) {var len = arr.length;if (len < 2) {return arr;}var middle = Math.floor(len / 2),left = arr.slice(0, middle),right = arr.slice(middle);return merge(mergeSort(left), mergeSort(right));
}function merge(left, right) {var result = [];while (left.length>0 && right.length>0) {if (left[0] <= right[0]) {result.push(left.shift());} else {result.push(right.shift());}}while (left.length)result.push(left.shift());while (right.length)result.push(right.shift());return result;
}

6.快速排序

• 定义：
  • 将第一个元素作为基准值，遍历数组，比基准小的放在左边，最后将第一个元素与最后一个左边元素调换位置
  • 以此类推，在左边以及右边的数组中重复该操作直至全部数组排序完成
• 代码实现：

function quickSort(arr, left, right) {var len = arr.length,partitionIndex,left = typeof left != 'number' ? 0 : left,right = typeof right != 'number' ? len - 1 : right;if (left < right) {partitionIndex = partition(arr, left, right);quickSort(arr, left, partitionIndex-1);quickSort(arr, partitionIndex+1, right);}return arr;
}function partition(arr, left ,right) {     // 分区操作var pivot = left,                      // 设定基准值（pivot）index = pivot + 1;for (var i = index; i <= right; i++) {if (arr[i] < arr[pivot]) {swap(arr, i, index);index++;}       }swap(arr, pivot, index - 1);return index-1;
}function swap(arr, i, j) {var temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}