- 排序对比
- 冒泡排序（Bubble Sort）
重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。时间复杂度O(N^2)
// 方法1：暴力循环,每次循环找到一个最大或者最小值
function bubbleSort(array) {
const length = array.length;
for (let i = 0; i < length; i++) {
for (let j = 0; j < length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
let temp = array[j + 1];
array[j + 1] = array[j];
array[j] = temp;
}
}
}
return array;
}
// 方法2：设置一个标志性变量pos，用于记录每趟排序中最后一次进行交换的位置.减少循环次数
function bubbleSort(array) {
let i = array.length - 1;
while (i > 0) {
let pos = 0;
for (let j = 0; j < i; j++) {
if (array[j] > array[j + 1]) {
pos = j;
let temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
i = pos;
}
return array;
}
// 方法3：利用在每趟排序中进行正向和反向两遍冒泡的方法一可以得到里那个个最终值（最大及最小），从而使排序趟数至少减少一半
function bubbleSort(array) {
let low = 0;
let high = array.length - 1;
while (low < high) {
for (let j = low; j < high; j++) {
if (array[j] > array[j + 1]) {
const temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
--high;
}
return array;
}
- 选择排序（Selection Sort）
表现最稳定的排序算法之一，因为无论什么数据进去都是O(n2)的时间复杂度……所以用它的时候数据规模越小越好，唯一的好处就是不占用额外的内存空间
function selectionSort(array) {
let length = array.length;
for (let i = 0; i < length - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < length; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
let temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
return array;
}
- 插入排序（Insertion Sort）
它的工作原理是通过构建有序序列，对未排序的数据，在已排序的序列中从后向前扫描，找到相应的位置并插入
// 从后往前插入
function insertionSort(array) {
for (let i = 1; i < array.length; i++) {
let key = array[i];
let j = i - 1;
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = key;
}
return array;
}
// 基于二分法
function insertionSort(array) {
for (let i = 1; i < array.length; i++) {
let key = array[i], left = 0, right = i - 1;
// 二分法left,right之前最小的项
while (left <= right) {
let middle = parseInt((left + right) / 2);
if (key < array[middle]) {
right = middle - 1;
} else {
left = middle + 1;
}
}
for (let j = i - 1; j >= left; j--) {
array[j + 1] = array[j];
}
array[left] = key;
}
return array;
}
- 希尔排序（Shell Sort）
希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态定义间隔序列(需要仔细理解下)。
function shellSort(array) { let gap = 1; while (gap < array.length / 5) { gap = gap * 5 + 1; } for (gap; gap > 0; parseInt(gap / 5)) { for (let i = gap; i < array.length; i++) { const temp = array[i]; for (let j = i - gap; j >= 0 && array[j] > temp; j -= gap) { array[j + gap] = array[j]; } array[j + gap] = temp; } } return array; } - 归并排序（Merge Sort）
归并排序是建立在归并操作的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。归并排序是一种稳定的排序算法，将已有序的子序列合并，得到一个完全有序的序列。
function mergeSort(array) { if (array.length < 2) { return array; } const middle = parseInt(array.length / 2); const left = array.slice(0, middle); const right = array.slice(middle); return merge(test_run(left), test_run(right)); } function merge(left, right) { const newArray = []; while (left.length && right.length) { if (left[0] <= right[0]) { newArray.push(left.shift()); } else { newArray.push(right.shift()); } } while (left.length) { newArray.push(left.shift()); } while (right.length) { newArray.push(right.shift()); } return newArray; } - 快速排序
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
// 方法一
const quickSort = function (array) {
if (array.length <= 1) {
return array;
}
const pivotIndex = parseInt(array.length / 2);
const pivot = Number(array.splice(pivotIndex, 1));
const left = []; const right = [];
for (let i = 0; i < array.length; i++) {
if (array[i] < pivot) {
left.push(array[i]);
} else {
right.push(array[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
};
// 方法2： left = 0; right = array.length-1
function quickSort(array, left, right) {
if (left < right) {
let x = array[right], i = left - 1;
for (let j = left; j <= right; j++) {
if (array[j] <= x) {
i++;
const temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
quickSort(array, left, i - 1);
quickSort(array, i + 1, right);
}
return array;
}
- 堆排序（Heap sort）
是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。(时间复杂度O (nlgn)多理解)
function heapSort(array) {
let length = array.length;
for (let i = parseInt(array.length / 2) - 1; i >= 0; i--) {
heap(array, i, length);
}
for (let j = length - 1; j >= 1; j--) {
const temp = array[0];
array[0] = array[j];
array[j] = temp;
heap(array, 0, --length);
}
return array;
}
function heap(array, x, length) {
let l = 2 * x + 1, r = 2 * x + 2, largest = x;
if (l < length && array[l] > array[largest]) {
largest = l;
}
if (r < length && array[r] > array[largest]) {
largest = r;
}
if (largest != x) {
const temp = array[x];
array[x] = array[largest];
array[largest] = temp;
heap(array, largest, length);
}
}
- 计数排序（Counting Sort）
计数排序的核心在于输入的数据值转换为键存储在额外开辟的数组空间中。计数排序是一种很稳定的排序算法，需要用到一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数，然后根据数字C将A中的元素排到正确的位置上个，它只能对数组进行排序
function countSort(array) {
const newArray = [], C = [];
let min = array[0];
let max = array[0];
for (let i = 0; i < array.length; i++) {
if (min >= array[i]) {
min = array[i];
}
if (max <= array[i]) {
max = array[i];
}
if (C[array[i]] = C[array[i]]) {
C[array[i]]++;
} else {
C[array[i]] = 1;
}
}
for (let j = min; j < max; j++) {
C[j + 1] = (C[j + 1] || 0) + (C[j] || 0);
}
for (let k = array.length - 1; k >= 0; k--) {
newArray[C[array[k]] - 1] = array[k];
C[array[k]]--;
}
return newArray;
}
- 排列相关示例
// 在已经排好序的数组中寻找这个数的位置（通过快速查找，二分查找）
function binarySearch(target,arr,start,end) {
var start = start || 0;
var end = end || arr.length-1;
var mid = parseInt(start+(end-start)/2);
if(target==arr[mid]){
return mid;
}else if(target>arr[mid]){
return binarySearch(target,arr,mid+1,end);
}else{
return binarySearch(target,arr,start,mid-1);
}
return -1;
}
// 找出数组中第k大的数出现多少次
// 思路：对数组进行排序，找到第k大的数，然后看第k大的数有几个，返回
