北京网站设计外包公司价格,网站404怎么做的,网站开发公司广告文案,枣庄网页制作公司文章目录 一、冒泡排序二、快速排序三、选择排序四、插入排序五、计算排序六、归并排序七、希尔排序八、堆排序九、桶排序十、基数排序 一、冒泡排序
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列#xff0c;一次比较两个元素#xff0c;如果它们的顺序错误就… 文章目录 一、冒泡排序二、快速排序三、选择排序四、插入排序五、计算排序六、归并排序七、希尔排序八、堆排序九、桶排序十、基数排序 一、冒泡排序
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列一次比较两个元素如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
算法步骤
比较相邻的元素。如果第一个比第二个大就交换他们两个。对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对。这步做完后最后的元素会是最大的数。针对所有的元素重复以上的步骤除了最后一个。持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较。 function bubbleSort(arr) {var len arr.length;for (var i 0; i len; i) {for (var j 0; j len - 1 - i; j) {if (arr[j] arr[j1]) { //相邻元素两两对比var temp arr[j1]; //元素交换arr[j1] arr[j];arr[j] temp;}}}return arr;
}
var arr[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(bubbleSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]二、快速排序
快速排序的基本思想通过一趟排序将待排记录分隔成独立的两部分其中一部分记录的关键字均比另一部分的关键字小则可分别对这两部分记录继续进行排序以达到整个序列有序。
实现
从数列中挑出一个元素称为 “基准”pivot重新排序数列所有元素比基准值小的摆放在基准前面所有元素比基准值大的摆在基准的后面相同的数可以到任一边。在这个分区退出之后该基准就处于数列的中间位置。这个称为分区partition操作递归地recursive把小于基准值元素的子数列和大于基准值元素的子数列排序。
/*方法说明快速排序
param array 待排序数组*/
//方法一
function quickSort(array, left, right) {if (Object.prototype.toString.call(array).slice(8, -1) Array typeof left number typeof right number) {if (left right) {var x array[right], i left - 1, temp;for (var j left; j right; j) {if (array[j] x) {i;temp array[i];array[i] array[j];array[j] temp;}}quickSort(array, left, i - 1);quickSort(array, i 1, right);}return array;} else {return array is not an Array or left or right is not a number!;}
}//方法二
var quickSort2 function(arr) {if (arr.length 1) {return arr;}const pivotIndex Math.floor(arr.length / 2);const pivot arr[pivotIndex];const less [];const greater [];for (let i 0; i arr.length; i) {if (i pivotIndex) {continue;}if (arr[i] pivot) {less.push(arr[i]);} else {greater.push(arr[i]);}}return [...quickSort2(less), pivot, ...quickSort2(greater)];
};var arr[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(quickSort(arr,0,arr.length-1));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
console.log(quickSort2(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]算法分析 最佳情况T(n) O(nlogn) 最差情况T(n) O(n2) 平均情况T(n) O(nlogn)
三、选择排序
选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理首先在未排序序列中找到最小大元素存放到排序序列的起始位置然后再从剩余未排序元素中继续寻找最小大元素然后放到已排序序列的末尾。以此类推直到所有元素均排序完毕。
步骤
首先在未排序序列中找到最小大元素存放到排序序列的起始位置再从剩余未排序元素中继续寻找最小大元素然后放到已排序序列的末尾。重复第二步直到所有元素均排序完毕。
function selectionSort(arr) {var len arr.length;var minIndex, temp;console.time(选择排序耗时);for (var i 0; i len - 1; i) {minIndex i;for (var j i 1; j len; j) {if (arr[j] arr[minIndex]) { //寻找最小的数minIndex j; //将最小数的索引保存}}temp arr[i];arr[i] arr[minIndex];arr[minIndex] temp;}console.timeEnd(选择排序耗时);return arr;
}
var arr[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(selectionSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]算法分析 最佳情况T(n) O(n2) 最差情况T(n) O(n2) 平均情况T(n) O(n2)
四、插入排序
插入排序Insertion-Sort是一种简单直观的排序算法。它的工作原理是通过构建有序序列对于未排序数据在已排序序列中从后向前扫描找到相应位置并插入。插入排序在实现上通常采用in-place排序即只需用到O(1)的额外空间的排序因而在从后向前扫描过程中需要反复把已排序元素逐步向后挪位为最新元素提供插入空间。
步骤
从第一个元素开始该元素可以认为已经被排序取出下一个元素在已经排序的元素序列中从后向前扫描如果该元素已排序大于新元素将该元素移到下一位置重复步骤3直到找到已排序的元素小于或者等于新元素的位置将新元素插入到该位置后重复步骤2~5。
function insertionSort(array) {if (Object.prototype.toString.call(array).slice(8, -1) Array) {console.time(插入排序耗时);for (var i 1; i array.length; i) {var key array[i];var j i - 1;while (j 0 array[j] key) {array[j 1] array[j];j--;}array[j 1] key;}console.timeEnd(插入排序耗时);return array;} else {return array is not an Array!;}
}算法分析 最佳情况输入数组按升序排列。T(n) O(n) 最坏情况输入数组按降序排列。T(n) O(n2) 平均情况T(n) O(n2)
五、计算排序
计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。 步骤
找出待排序的数组中最大和最小的元素统计数组中每个值为i的元素出现的次数存入数组C的第i项对所有的计数累加从C中的第一个元素开始每一项和前一项相加反向填充目标数组将每个元素i放在新数组的第C(i)项每放一个元素就将C(i)减去1。
function countingSort(array) {var len array.length,B [],C [],min max array[0];console.time(计数排序耗时);for (var i 0; i len; i) {min min array[i] ? min : array[i];max max array[i] ? max : array[i];C[array[i]] C[array[i]] ? C[array[i]] 1 : 1;}for (var j min; j max; j) {C[j 1] (C[j 1] || 0) (C[j] || 0);}for (var k len - 1; k 0; k--) {B[C[array[k]] - 1] array[k];C[array[k]]--;}console.timeEnd(计数排序耗时);return B;算法分析 当输入的元素是n 个0到k之间的整数时它的运行时间是 O(n k)。计数排序不是比较排序排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围等于待排序数组的最大值与最小值的差加上1这使得计数排序对于数据范围很大的数组需要大量时间和内存。
最佳情况T(n) O(nk) 最差情况T(n) O(nk) 平均情况T(n) O(nk)
六、归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法Divide and Conquer的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为2-路归并。
步骤
把长度为n的输入序列分成两个长度为n/2的子序列对这两个子序列分别采用归并排序将两个排序好的子序列合并成一个最终的排序序列。 function mergeSort(arr) { //采用自上而下的递归方法var len arr.length;if(len 2) {return arr;}var middle Math.floor(len / 2),left arr.slice(0, middle),right arr.slice(middle);return merge(mergeSort(left), mergeSort(right));
}function merge(left, right)
{var result [];console.time(归并排序耗时);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());console.timeEnd(归并排序耗时);return result;
}
var arr[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(mergeSort(arr));算法分析 最佳情况T(n) O(n) 最差情况T(n) O(nlogn) 平均情况T(n) O(nlogn)
七、希尔排序
希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法第4版》的合著者Robert Sedgewick提出的。 步骤 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序具体算法描述
选择一个增量序列t1t2…tk其中titjtk1按增量序列个数k对序列进行k 趟排序每趟排序根据对应的增量ti将待排序列分割成若干长度为m 的子序列分别对各子表进行直接插入排序。仅增量因子为1 时整个序列作为一个表来处理表长度即为整个序列的长度。
function shellSort(arr) {var len arr.length,temp,gap 1;console.time(希尔排序耗时:);while(gap len/5) { //动态定义间隔序列gap gap*51;}for (gap; gap 0; gap Math.floor(gap/5)) {for (var i gap; i len; i) {temp arr[i];for (var j i-gap; j 0 arr[j] temp; j-gap) {arr[jgap] arr[j];}arr[jgap] temp;}}console.timeEnd(希尔排序耗时:);return arr;
}
var arr[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(shellSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
算法分析 最佳情况T(n) O(nlog2 n) 最坏情况T(n) O(nlog2 n) 平均情况T(n) O(nlog n)
八、堆排序
堆排序Heapsort是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构并同时满足堆积的性质即子结点的键值或索引总是小于或者大于它的父节点。
步骤
将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆此堆为初始的无序区将堆顶元素R[1]与最后一个元素R[n]交换此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]R[n]由于交换后新的堆顶R[1]可能违反堆的性质因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆然后再次将R[1]与无序区最后一个元素交换得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1则整个排序过程完成。
/*方法说明堆排序
param array 待排序数组*/
function heapSort(array) {console.time(堆排序耗时);if (Object.prototype.toString.call(array).slice(8, -1) Array) {//建堆var heapSize array.length, temp;for (var i Math.floor(heapSize / 2) - 1; i 0; i--) {heapify(array, i, heapSize);}//堆排序for (var j heapSize - 1; j 1; j--) {temp array[0];array[0] array[j];array[j] temp;heapify(array, 0, --heapSize);}console.timeEnd(堆排序耗时);return array;} else {return array is not an Array!;}
}
/*方法说明维护堆的性质
param arr 数组
param x 数组下标
param len 堆大小*/
function heapify(arr, x, len) {if (Object.prototype.toString.call(arr).slice(8, -1) Array typeof x number) {var l 2 * x 1, r 2 * x 2, largest x, temp;if (l len arr[l] arr[largest]) {largest l;}if (r len arr[r] arr[largest]) {largest r;}if (largest ! x) {temp arr[x];arr[x] arr[largest];arr[largest] temp;heapify(arr, largest, len);}} else {return arr is not an Array or x is not a number!;}
}
var arr[91,60,96,13,35,65,46,65,10,30,20,31,77,81,22];
console.log(heapSort(arr));//[10, 13, 20, 22, 30, 31, 35, 46, 60, 65, 65, 77, 81, 91, 96]算法分析 最佳情况T(n) O(nlogn) 最差情况T(n) O(nlogn) 平均情况T(n) O(nlogn)
九、桶排序
桶排序 (Bucket sort)的工作的原理假设输入数据服从均匀分布将数据分到有限数量的桶里每个桶再分别排序有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排
步骤
设置一个定量的数组当作空桶遍历输入数据并且把数据一个一个放到对应的桶里去对每个不是空的桶进行排序从不是空的桶里把排好序的数据拼接起来。
/*方法说明桶排序
param array 数组
param num 桶的数量*/
function bucketSort(array, num) {if (array.length 1) {return array;}var len array.length, buckets [], result [], min max array[0], regex /^[1-9][0-9]*$/, space, n 0;num num || ((num 1 regex.test(num)) ? num : 10);console.time(桶排序耗时);for (var i 1; i len; i) {min min array[i] ? min : array[i];max max array[i] ? max : array[i];}space (max - min 1) / num;for (var j 0; j len; j) {var index Math.floor((array[j] - min) / space);if (buckets[index]) { // 非空桶插入排序var k buckets[index].length - 1;while (k 0 buckets[index][k] array[j]) {buckets[index][k 1] buckets[index][k];k--;}buckets[index][k 1] array[j];} else { //空桶初始化buckets[index] [];buckets[index].push(array[j]);}}while (n num) {result result.concat(buckets[n]);n;}console.timeEnd(桶排序耗时);return result;
}
var arr[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(bucketSort(arr,4));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]算法分析 桶排序最好情况下使用线性时间O(n)桶排序的时间复杂度取决与对各个桶之间数据进行排序的时间复杂度因为其它部分的时间复杂度都为O(n)。很显然桶划分的越小各个桶之间的数据越少排序所用的时间也会越少。但相应的空间消耗就会增大。
最佳情况T(n) O(nk) 最差情况T(n) O(nk) 平均情况T(n) O(n2)
十、基数排序
基数排序是按照低位先排序然后收集再按照高位排序然后再收集依次类推直到最高位。有时候有些属性是有优先级顺序的先按低优先级排序再按高优先级排序。最后的次序就是高优先级高的在前高优先级相同的低优先级高的在前。基数排序基于分别排序分别收集所以是稳定的。 步骤
取得数组中的最大数并取得位数arr为原始数组从最低位开始取每个位组成radix数组对radix进行计数排序利用计数排序适用于小范围数的特点
/*** 基数排序适用于* (1)数据范围较小建议在小于1000* (2)每个数值都要大于等于0* author damonare* param arr 待排序数组* param maxDigit 最大位数*/
//LSD Radix Sortfunction radixSort(arr, maxDigit) {var mod 10;var dev 1;var counter [];console.time(基数排序耗时);for (var i 0; i maxDigit; i, dev * 10, mod * 10) {for(var j 0; j arr.length; j) {var bucket parseInt((arr[j] % mod) / dev);if(counter[bucket] null) {counter[bucket] [];}counter[bucket].push(arr[j]);}var pos 0;for(var j 0; j counter.length; j) {var value null;if(counter[j]!null) {while ((value counter[j].shift()) ! null) {arr[pos] value;}}}}console.timeEnd(基数排序耗时);return arr;
}
var arr [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(radixSort(arr,2)); //[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
算法分析 最佳情况T(n) O(n * k) 最差情况T(n) O(n * k) 平均情况T(n) O(n * k)
