芜湖酒店网站建设/获客

冒泡排序

依次比较两个相邻元素大小，如果顺序错误则交换位置，递归此操作。

function bubbleSort(data){var temp=0;for(var i=data.length;i>0;i--){//由于每次执行都会把最大的数移动到数组尾部，//所以每次循环长度减少1，避免不必要比较for(var j=0;j<i-1;j++){// 比较相邻元素if(data[j]>data[j+1]){//交换元素位置temp=data[j];data[j]=data[j+1];data[j+1]=temp;}}}return data;
}

选择排序

遍历找到数据中的最小元素置于首位，剩余元素递归此操作。

function selectionSort(data){for(var i=0;i<data.length;i++){var minValue=data[i];var minIndex = i;for(var j=i+1;j<data.length;j++){if(data[j]<minValue){minValue = data[j]minIndex = j;}}if(minIndex != i){var temp = data[i]data[minIndex]=temp;data[i]=minValue;}}return data
}

插入排序

将数据分为有序区和无序区两组，最初有序区只有一个元素，每次从无序区中选择一个元素，插入到有序区的位置，直到无序区变空。

function insertSort(data){// 将数组首尾分别作为有序区和无序区// 将数组第一个元素作为有序区初始元素for(var i=1;i<data.length;i++){// 从无序区选取元素，此处选取第一个var  temp=data[i];// j 为有序区最后一个（即值最大）元素下标var j=i-1;// 遍历有序区将选取的元素插入到正确位置while(j>=0&&data[j]>temp){data[j+1]=data[j];data[j] = tempj--;}}return data;
}

以上算法时间复杂度O(n²)，空间复杂度O(1)

快速排序

将要数据分割成两组，其中一组所有数据比另外一组所有数据都小，对这两组数据分别递归此操作。

function quickSort(arr){if(arr.length<=1){return arr;}var left=[];var right=[];// 将数组任意元素作为比较对象，此处选取第一个var pivot=arr[0];for(var i=1;i<arr.length;i++){if(arr[i]<pivot){left.push(arr[i]);} else{right.push(arr[i]);}}return quickSort(left).concat(pivot,quickSort(right));
}

时间复杂度 平均O(nlogn)最坏O(n²)，空间复杂度 平均O(logn)最坏O(n)

归并排序

将两个有序分段合并一个有序列表称为一次归并。
归并排序现将数组分为若干个有序分段，对分段进行归并递归，最终合并为一个有序表。

function mergeArr(arr1, arr2){//将两个有序数组合并成一个有序数组var arr = [];var i = 0, j = 0;while( arr1.length || arr2.length){// 分别从两个数组中取较小的值加入到新数组if(arr1[0] === undefined){ // arr1已空，直接取arr2元素arr.push(arr2.shift());} else if(arr2[0] === undefined){// arr2已空，直接取arr1元素arr.push(arr1.shift());} else if(arr1[0] < arr2[0]){// arr1和arr2均不为空，取值较小的元素			arr.push(arr1.shift());} else {// 同上arr.push(arr2.shift());}}return arr;
}
function mergeSort(arr){// 将数组递归划分至元素仅有一个元素的数组，即可视为有序数组if(arr.length > 1){var mid = Math.ceil(arr.length/2);var arr1 = arr.slice(0,mid);var arr2 = arr.slice(mid)// 对划分后的数组进行合并return mergeArr(mergeSort(arr1), mergeSort(arr2));}return arr;
}

时间复杂度O(nlogn)，空间复杂度O(n)