排序和搜索算法
排序算法
// 排序
function ArrayList() {
var arr = [];
this.insert = function(item) {
arr.push(item);
};
this.toString = function() {
return arr.join();
};
// 冒泡排序
// 从运行时间的角度来看，冒泡排序是最差的一个，复杂度O(n^2)
this.bubbleSort = function() {
var len = arr.length;
// 如果从内循环减去外循环已跑过的轮数，就可以避免内循环中所有不必要的比较
for (var i = 0; i < len; i++) {
for (var j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(j, j + 1);
}
}
}
};
function swap(m, n) {
var tmp = arr[m];
arr[m] = arr[n];
arr[n] = tmp;
}
// 选择排序
// 思路：找到数据中的最小值并将其放在第一位，接着找到第二小的放在第二位，以此类推
// 时间复杂度也是O(n^2)
this.selectionSort = function() {
var len = arr.length,
indexMin;
for (var i = 0; i < len - 1; i++) {
indexMin = i;
for (var j = i; j < len; j++) {
if (arr[indexMin] > arr[j]) {
indexMin = j;
}
}
if (i !== indexMin) {
swap(i, indexMin);
}
}
}
// 插入排序
// 排序小型数组时，比冒泡和选择排序性能要好
this.insertionSort = function() {
var len = arr.length,
j, tmp;
for (var i = 1; i < len; i++) {
j = i;
tmp = arr[i];
while (j > 0 && arr[j - 1] > tmp) {
arr[j] = arr[j - 1];
j--;
}
arr[j] = tmp;
}
}
// 归并排序
// 是第一个可以被实际使用的排序算法，性能比前三个算法好，复杂度为O(nlog^n)
// 归并排序是一种分治算法。其思想是将原始数组切分成较小的数组，直到每个小数组只有一个位置，
// 接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组
this.mergeSort = function() {
arr = mergeSortRec(arr);
};
var mergeSortRec = function(arr) {
var len = arr.length;
if (len === 1) {
return arr;
}
var mid = Math.floor(len / 2),
left = arr.slice(0, mid),
right = arr.slice(mid, len);
return merge(mergeSortRec(left), mergeSortRec(right));
};
var merge = function(left, right) {
var res = [],
l = 0,
r = 0;
while (l < left.length && r < right.length) {
if (left[l] < right[r]) {
res.push(left[l++]);
} else {
res.push(right[r++]);
}
}
while (l < left.length) {
res.push(left[l++]);
}
while (r < right.length) {
res.push(right[r++]);
}
return res;
};
// 快速排序
// 快排是最常用的排序算法，复杂度为O(nlog^n),且它的性能通常比其他的复杂度为O(nlog^n)的要好
// 也使用分治的方法，将原始数组分成较小的数组
this.quickSort = function() {
quick(arr, 0, arr.length - 1);
};
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);
}
}
};
var partition = function(arr, left, right) {
var pivot = arr[Math.floor((left + right) / 2)],
i = left,
j = right;
while (i <= j) {
while (arr[i] < pivot) {
i++;
}
while (arr[j] > pivot) {
j--;
}
if (i <= j) {
swapQuick(arr, i, j);
i++;
j--;
}
}
return i;
};
function swapQuick(arr, m, n) {
var tmp = arr[m];
arr[m] = arr[n];
arr[n] = tmp;
}
// 搜索算法
// 1.顺序搜索
// 将每一个数据结构中的元素和我们要找的元素作比较。顺序搜索是最低效的一种搜索算法
this.lowSearch = function(item) {
for (var i = 0; i < arr.length; i++) {
if (item === arr[i]) {
return i;
}
}
return -1;
};
//2.二分搜索
/*
这个算法要求被搜索的数据结构已排序
步骤：
1.选择数组的中间值
2.如果选中的值是待搜索值，那么算法是执行完毕
3.如果待搜索值比选中值要小，则返回步骤1并在选中值左边的子数组中寻找
4.如果待搜索值比选中值要大，则返回步骤1并在选中值右边的子数组中寻找
*/
this.binarySearch = function(item) {
this.quickSort();
var low = 0,
high = arr.length - 1,
mid, ele;
while (low <= high) {
mid = Math.floor((low + high) / 2);
ele = arr[mid];
if (ele < item) {
low = mid + 1;
} else if (ele > item) {
high = mid - 1;
} else {
return mid;
}
}
return -1;
};
}
// 创建未排序的数组
function createNonSortedArray(size) {
var arr = new ArrayList();
for (var i = size; i > 0; i--) {
arr.insert(i);
}
return arr;
}
var arr = createNonSortedArray(5);
console.log(arr.toString());
// arr.bubbleSort();
// arr.selectionSort();
// arr.insertionSort();
// arr.mergeSort();
arr.quickSort();
console.log(arr.toString());
