-
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
-
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
-
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
-
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
交换（使用解构赋值）
arr1=[1,2];
arr2=[2,3];
[arr1,arr2]=[arr2,arr1];
console.log(arr1);//2,3
检查是否为数组，交换位置
function checkArr(arr){
return Array.isArray(arr);
}
function swap(arr,left,right){
[arr[left],arr[right]]=[arr[right],arr[left]];
}
冒泡排序
- 冒泡排序的原理如下，从第一个元素开始，把当前元素和下一个索引元素进行比较。如果当前元素大，那么就交换位置，重复操作直到比较到最后一个元素，那么此时最后一个元素就是该数组中最大的数。下一轮重复以上操作，但是此时最后一个元素已经是最大数了，所以不需要再比较最后一个元素，只需要比较到 length - 2 的位置。
function bubble(arr){
if(!checkArr(arr)){
console.log("not arr");
}
for(let i=0;i<arr.length-1;i++){
//写在第一个for循环里，是为了，每轮比较初始化bool变量变为true。
let flag=true;
for(let j=0;j<arr.length-1-i;j++){//每一轮都会比较出一个最大值，然后后一轮没有必要再比较了，所以没比较一轮，就少比较一次
if(arr[j]>arr[j+1]){
swap(arr,j,j+1);
flag=false
}
}
if(flag){//，如果本轮比较没有任何元素相互交换位置，那么说明已经比较完成，可以跳出循环
break;
}
}
return arr;
}
var arr=[2,1,5,6,3];
console.log(bubble(arr));
- 该算法的操作次数是一个等差数列 n + (n - 1) + (n - 2) + 1 ，去掉常数项以后得出时间复杂度是 O(n * n)
选择排序
- 选择排序的原理如下。遍历数组，设置最小值的索引为 0，如果取出的值比当前最小值小，就替换最小值索引，遍历完成后，将第一个元素和最小值索引上的值交换。如上操作后，第一个元素就是数组中的最小值，下次遍历就可以从索引 1 开始重复上述操作。
function select(arr){
if(!checkArr(arr)){
console.log("not arr");
}
for(let i=0;i<arr.length-1;i++){
let minindex=i;
for(j=i+1;j<arr.length;j++){
minindex=arr[j]<arr[minindex]?j:minindex;
}
swap(arr,i,minindex);
}
return arr;
}
var arr=[2,1,5,6,3];
console.log(select(arr));
快排
var quickSort = function(arr) {
if (arr.length <= 1) { return arr; }
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++){
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
};
归并排序
- 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
function mergeSort(arr){
//设置终止的条件
if(arr.length<2){
return arr;
}
//设置中间值
var middle=Math.floor(arr.length/2);
var left=arr.slice(0,middle);
var right=arr.slice(middle);
if(left=="undefined"&&right=="undefined"){
return false;
}
return merge(mergeSort(left),mergeSort(right));
}
function merge(left,right){
var result=[];
while(left.length&&right.length){
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;
}
// 测试数据
var nums=[6,10,1,9,4,8,2,7,3,5];
console.log(mergeSort(nums));
image
二分查找
- 二分查找，折半查找（有序数组中查找特定元素）
- 首先，从有序数组的中间的元素开始搜索，如果该元素正好是目标元素（即要查找的元素），则搜索过程结束，否则进行下一步。
- 如果目标元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半区域查找，然后重复第一步的操作。
//如果某一步数组为空，则表示找不到目标元素
//二分查找，折半查找（有序数组中查找特定元素）
//首先，从有序数组的中间的元素开始搜索，如果该元素正好是目标元素（即要查找的元素），则搜索过程结束，否则进行下一步。
//如果目标元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半区域查找，然后重复第一步的操作。
//如果某一步数组为空，则表示找不到目标元素。
function binSearch(arr,data){
var low=0;
var high=arr.length-1;
while(low<=high){
var middle=Math.floor((low+high)/2);
if(arr[middle]<data){
low=middle+1;
}else if(arr[middle>data]){
high=middle-1;
}else{
return middle;
}
}
return -1;
}
var arr=[3,6,9,10,70];
console.log(binSearch(arr, 10))
网友评论