JavaScript 常见排序算法集锦
var arr = [1, 9, 5, 4, 8, 10, 2, 7, 3, 5, 6];
var len = arr.length;
// 排序
// 交换排序：冒泡排序 快速排序
/*
冒泡排序
基本思想：
重复地走访待排记录记录，一次比较两个元素，如果它们大小顺序错误则进行交换。
算法描述：
1.比较相邻的两个元素,如果第一个比第二个大，进行交换；
2.对每一对相邻元素重复步骤1，从开始第一对到结尾的最后一对，最后的元素是最大的数；
3.针对所有的元素重复步骤1~2，除了最后一个；
4.重复步骤1~3，直到排序完成。
时间复杂度：
O(n2) O(n)
平均时间复杂度：
O(n2)
比较次数：
n(n-1)/2 n-1
稳定
*/
function bubbleSort(arr) {
var temp,
len = arr.length;
for (var i = 0; i < len - 1; i++) {
for (j = i + 1; j < len; j++) {
if (arr[i] > arr[j]) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
function bubbleSort(arr) {
var temp,
len = arr.length;
for (var i = 0; i < len - 1; i++) {
for (j = 0; j < len - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
function bubbleSort(arr) {
var len = arr.length;
var temp = null;
var flag = false; //设置标志位，初始值为false
for (var i = 0; i < len - 1; i++) {
for (var j = 0; j < len - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = true; //交换，标识设为true
}
}
if (flag) { //如果进行交换，标识重新设为false
flag = false;
} else { //如果未进行交换，说明数组已经排好序，结束循环
break;
}
}
return arr;
}
// console.log(bubbleSort(arr));
/*
快速排序
基本思想：
递归
通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
算法描述：
1.从数列中挑出一个元素作为基准；
2.重新排序数列，所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准的后面（相同的数可以放到任一边）；在分区退出之后，该基准就处于数列的中间位置，即分区（partition）操作；
3.递归把小于基准值元素的子数列和大于基准值元素的子数列排序。
时间复杂度：
O(n2) O(nlogn)
平均时间复杂度：
O(nlogn)
空间复杂度：
O(nlogn)
不稳定
*/
function quickSort(arr) {
var self = arguments.callee;
if (arr.length <= 1) {
return arr;
}
var left = [],
right = [];
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
for (var i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return self(left).concat([pivot], self(right));
}
// console.log(quickSort(arr));
function quickSort(arr, left, right) {
var self = arguments.callee;
if (left < right) {
var index = partition(arr, left, right);
self(arr, left, index - 1);
self(arr, index + 1, right);
}
return arr;
}
function partition(arr, left, right) {
var pivotIndex = Math.floor((right + left) / 2),
i = left,
j = right;
var pivot = arr[pivotIndex];
arr[pivotIndex] = arr[left];
while (i < j) {
while (i < j && arr[j] > pivot) {
j--;
}
if (i < j) arr[i++] = arr[j];
while (i < j && arr[i] < pivot) {
i++;
}
if (i < j) arr[j--] = arr[i];
}
arr[i] = pivot;
return i;
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function quickSort(arr, left, right) {
var self = arguments.callee;
if (left < right) {
var pivot = arr[left],
i = left,
j = right;
while (i < j) {
while (i < j && arr[j] > pivot) {
j--;
}
if (i < j) arr[i++] = arr[j];
while (i < j && arr[i] < pivot) {
i++;
}
if (i < j) arr[j--] = arr[i];
}
arr[i] = pivot;
self(arr, left, i - 1);
self(arr, i + 1, right);
}
return arr;
}
// console.log(quickSort(arr, 0, len - 1));
// 插入排序：插入排序 希尔排序
/*
插入排序
基本思想：
通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
算法描述：
1.从第一个元素开始，该元素可以认为已经被排序；
2.取出下一个元素，在已经排序的元素序列中从后向前扫描；
3.如果该元素（已排序）大于新元素，将该元素移到下一位置；
4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5.将新元素插入到该位置后；
6.重复步骤2~5。
时间复杂度：
O(n2) O(n)
平均时间复杂度：
O(n2)
比较次数：
n(n-1)/2 n-1
稳定
*/
function insertSort(arr) {
var temp,
j,
len = arr.length;
for (var i = 1; i < len; i++) { //第一个元素不用排序
temp = arr[i]; //temp缓存待插入的元素
for (j = i - 1; j > -1; j--) {
if (arr[j] > temp) {
arr[j + 1] = arr[j];
} else {
break;
}
}
arr[j + 1] = temp; //插入元素
}
return arr;
}
function insertSort(arr) {
var temp,
j,
len = arr.length;
for (var i = 1; i < len; i++) { //第一个元素不用排序
temp = arr[i]; //temp缓存待插入的元素
j = i - 1;
while (arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp; //插入元素
}
return arr;
}
// console.log(insertSort(arr));
/*
希尔排序
基本思想：
先将整个待排记录序列分割成若干个子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
时间复杂度：
O(n1.5) O(n)
平均时间复杂度：
O(n1.5)
不稳定
*/
function shellSort(arr) {
var temp,
len = arr.length,
gap = Math.floor(len / 2);
while (gap > 0) {
for (var i = gap; i < len; i++) {
temp = arr[i];
for (var j = i - gap; j >= 0; j = j - gap) {
if (temp < arr[j]) {
arr[j + gap] = arr[j];
} else {
break;
}
}
arr[j + gap] = temp;
}
gap = Math.floor(gap / 2);
}
return arr;
}
function shellSort(arr) {
var temp,
len = arr.length,
gap = Math.floor(len / 2);
while (gap > 0) {
for (var i = gap; i < len; i++) {
temp = arr[i];
var j = i - gap;
while (j >= 0 && temp < arr[j]) {
arr[j + gap] = arr[j];
j = j - gap;
}
arr[j + gap] = temp;
}
gap = Math.floor(gap / 2);
}
return arr;
}
// console.log(shellSort(arr));
// 选择排序：选择排序 堆排序
/*
选择排序
基本思想：
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
算法描述：
1.初始状态：无序区为R[1..n]，有序区为空；
2.第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个的新无序区。
时间复杂度 O(n2)
不稳定
*/
function selectSort(arr) {
var temp,
k,
len = arr.length;
for (var i = 0; i < len - 1; i++) {
k = i;
for (var j = i + 1; j < len; j++) {
if (arr[j] < arr[k]) {
k = j;
}
}
if (k != i) {
temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
}
return arr;
}
// console.log(selectSort(arr));
/*
堆排序
基本思想：
递归
堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或大于）它的父节点。
其中每个结点的关键字都不大于其孩子结点的关键字，这样的堆称为小根堆。
其中每个结点的关键字都不小于其孩子结点的关键字，这样的堆称为大根堆。
对于n个元素的序列{R0, R1, ... , Rn}当且仅当满足下列关系之一时，称之为堆：
(1) Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)
(2) Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)
将根节点值与左右子树的根节点值进行比较，若不满足堆条件，则将左右树根节点中的大者（或小者）与根节点进行交换，一直到所有子树均为堆。
算法描述：
1.将初始待排序序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序序列；
2.将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序序列(R1,R2,......Rn-1)和新的有序序列(Rn),且满足R[1,2...n-1]<=R[n]；
3.由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序序列(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序序列最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序序列(Rn-1,Rn)。不断重复此过程直到有序序列的元素个数为n-1，则整个排序过程完成。
时间复杂度：
O(nlogn)
不稳定
*/
function heapSort(arr) {
var len = arr.length,
temp;
for (var i = Math.floor(len / 2); i >= 0; i--) {
heapify(arr, i, len - 1); // 建立初始堆
}
for (var j = len - 1; j >= 1; j--) {
temp = arr[0]; // 最后一个元素和第一元素进行交换
arr[0] = arr[j];
arr[j] = temp;
heapify(arr, 0, j);
}
return arr;
}
function heapify(arr, parent, len) {
var child = 2 * parent + 1,
temp = arr[parent]; // 待排序的根节点
while (child < len) {
// 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
if (child + 1 < len && arr[child] < arr[child +
1]) {
child++;
}
if (temp < arr[child]) {
arr[parent] = arr[child]; // 把子结点值赋给父结点
parent = child;
child = 2 * child + 1;
} else {
break;
}
}
arr[parent] = temp;
return arr;
}
function heapify(arr, parent, len) {
var left = 2 * parent + 1,
right = 2 * (parent + 1),
max = parent,
temp;
if (left < len && arr[left] > arr[max]) {
max = left;
}
if (right < len && arr[right] > arr[max]) {
max = right;
}
if (max != parent) {
temp = arr[parent];
arr[parent] = arr[max];
arr[max] = temp;
arguments.callee(arr, max, len - 1);
}
return arr;
}
// console.log(heapSort(arr));
/*
归并排序
基本思想：
分治
将待排序序列R[0...n-1]看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。
算法描述：
1.把长度为n的输入序列分成两个长度为n/2的子序列；
2.对这两个子序列分别采用归并排序；
3.将两个排序好的子序列合并成一个最终的排序序列。
时间复杂度：
O(nlogn)
空间复杂度：
O(n)
稳定
*/
function mergeSort(arr, first, last) {
var self = arguments.callee;
if (first < last) {
var mid = Math.floor((first + last) / 2);
self(arr, first, mid); // 左边有序
self(arr, mid + 1, last); // 右边有序
merge(arr, first, mid, last); // 合并左右有序序列
}
return arr;
}
function merge(arr, first, mid, last) {
var i = first,
j = mid + 1,
k = 0,
temp = [];
while (i <= mid && j <= last) {
if (arr[i] <= arr[j])
temp[k++] = arr[i++];
else
temp[k++] = arr[j++];
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= last) {
temp[k++] = arr[j++];
}
for (i = 0; i < k; i++) {
arr[first + i] = temp[i];
}
return arr;
}
// console.log(mergeSort(arr, 0, len - 1));
/*
基数排序
算法描述：
时间复杂度：
O(d(r+n)) r为基数 d为位数
空间复杂度：
O(n+r)
稳定
*/
// 有序数组二分查找
function binarySearch(arr, key, start, end) {
var self = arguments.callee;
var mid = Math.floor((start + end) / 2);
if (arr[mid] == key) {
return mid;
}
if (key < arr[mid]) {
return self(arr, key, 0, mid - 1);
} else {
return self(arr, key, mid + 1, end);
}
}
// console.log(binarySearch(quickSort(arr), 5, 0, len - 1));
// 查找两个有序数组中相同的元素
function getSame(arr1, arr2) {
var len1 = arr1.length,
len2 = arr2.length;
var i = 0,
j = 0,
result = [];
while (i < len1 && j < len2) {
if (arr1[i] == arr2[j]) {
result.push(arr1[i]);
i++;
j++;
} else if (arr1[i] < arr2[j]) {
i++;
} else {
j++;
}
}
return result;
}
var brr = [1, 5, 19, 6, 12, 14];
// console.log(getSame(quickSort(arr), quickSort(brr)));
// 全排列
var srr = [1, 2, 3, 4];
function perm(arr, end) {
if (end <= 1) {
console.log(arr);
return arr;
} else {
for (var i = 0; i < end; i++) {
swap(arr, i, end - 1);
sortAll(arr, end - 1);
swap(arr, i, end - 1);
}
}
}
// perm(srr, srr.length);
function perm(arr, start, end) {
if (start == end) {
console.log(arr);
} else {
for (var i = start; i <= end; i++) {
swap(arr, start, i);
sortAll(arr, start + 1, end);
swap(arr, start, i);
}
}
}
// perm(srr, 0, srr.length - 1);
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
