知识扩充：
时间复杂度：算法的时间复杂度是一个函数，描述了算法的运行时间。时间复杂度越低，效率越高。
自我理解:一个算法，运行了几次时间复杂度就为多少，如运行了n次，则时间复杂度为O(n)。
1.冒泡排序
解析：1.比较相邻的两个元素，如果前一个比后一个大，则交换位置。
2.第一轮的时候最后一个元素应该是最大的一个。
3.按照步骤一的方法进行相邻两个元素的比较，这个时候由于最后一个元素已经是最大的了，所以最后一个元素不用比较。
timg.jpeg
function bubbleSort(elements){
for(var i=0;i<elements.length-1;i++){
for(var j=0;j<elements.length-i-1;j++){
if(elements[j]>elements[j+1]){
var swap=elements[j];
elements[j]=elements[j+1];
elements[j+1]=swap;
}
}
}
}
var elements = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log('before: ' + elements);
bubbleSort(elements);
console.log(' after: ' + elements);
2.快速排序
第一步，选择中间的元素45作为"基准"。（基准值可以任意选择，但是选择中间的值比较容易理解。）
image
第二步，按照顺序，将每个元素与"基准"进行比较，形成两个子集，一个"小于45"，另一个"大于等于45"。
image
第三步，对两个子集不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
image
image
image
image
function quickSort(elements) {
if (elements.length <= 1) { return elements; }
var pivotIndex = Math.floor(elements.length / 2);
var pivot = elements.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
for (var i = 0; i < elements.length; i++){
if (elements[i] < pivot) {
left.push(elements[i]);
} else {
right.push(elements[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
};
var elements=[5,6,2,1,3,8,7,1.2,5.5,4.5];
console.log(quickSort(elements));
function quickSort2(array) {
if (array.length <= 1) { return array; }
var pivot = array[0]; //以数组第1个做为基准点
var left = [];
var right = [];
for (var i = 1; i < array.length; i++){ //从数组第2个元素开始遍历
if (array[i] < pivot) {
left.push(array[i]);
} else {
right.push(array[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
};
3.选择排序
原理：首先在待排序序列中找到最小元素，放入存储有序序列的数组中，同时从待排序序列中删除这个元素；继续从未排序序列中找到最小元素，然后放入有序序列的数组中，直到待排序序列为空，返回有序序列。
function selectSort (array) {
var reSort = [];//存储有序序列
var len = array.length;
var min,i;
for (i = 0; i < len; i ++) {
min = Math.min.apply(null,array);//待排序序列的最小值
reSort.push(min);
array.splice(array.indexOf(min),1);
}
return reSort;
}
4.插入排序
解析：
（1） 从第一个元素开始，该元素可以认为已经被排序
（2） 取出下一个元素，在已经排序的元素序列中从后向前扫描
（3） 如果该元素（已排序）大于新元素，将该元素移到下一位置
（4） 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
（5）将新元素插入到下一位置中
（6） 重复步骤2
image.png
function InsertSort(arr)
{
var i, j;
var n = arr.Length;
var target;
//假定第一个元素被放到了正确的位置上
//这样，仅需遍历1 - n-1
for (i = 1; i < n; i++)
{
j = i;
target = arr[i];
while (j > 0 && target < arr[j - 1])
{
arr[j] = arr[j - 1];
j--;
}
arr[j] = target;
}
}
4.二分查找
解析：二分查找，也为折半查找。首先要找到一个中间值，通过与中间值比较，大的放又，小的放在左边。再在两边中寻找中间值，持续以上操作，直到找到所在位置为止。
（1）递归方法
function binarySearch(data,item,start,end){
var end=end || data.length-1;
var start=start || 0;
var m=Math.floor((start+end)/2);
if(item==data[m]){
return m;
}else if(item<data[m]){
return binarySearch(data,item,start,m-1);
}else{
return binarySearch(data,item,m+1,end);
}
return false;
}
（2）非递归方法
function binarySearch(data, item){
var h = data.length - 1,
l = 0;
while(l <= h){
var m = Math.floor((h + l) / 2);
if(data[m] == item){
return m;
}
if(item > data[m]){
l = m + 1;
}else{
h = m - 1;
}
}
return false;
}
var arr=[34,12,5,123,2,745,32,4];
binarySearch(arr,5);
网友评论