JS排序算法:冒泡法、快速排序法、选择排序法、插入排序法、哈希排序
//生成数组
var arr = new Array(1000);
for (var i = 0; i < 1000; i++) {
arr[i] = (Math.round(Math.random() * 1000));
}
1.冒泡法
排序思想:数组相邻两项进行比较,如果前一项比后一项大则交换位置,比较arr.length-1轮,每一轮把最大的一位数放最后
//冒泡法排序
function sortArr(arr) {
for (var i = 0; i < arr.length - 1; i++) {//比较arr.length-1轮
for (var j = i + 1; j < arr.length; j++) {
if (arr[i] > arr[j]) {//交换
var temp = arr[i];//临时变量
arr[i] = arr[j];
arr[j] = temp;
}
}
}
2.快速排序法
原理:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,
整个排序过程可以递归进
(1)在数据集之中,选择一个元素作为”基准”(pivot)。
(2)所有小于”基准”的元素,都移到”基准”的左边;所有大于”基准”的元素,都移到”基准”的右边。
(3)对”基准”左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。
快速排序的最坏运行情况是O(n²),比如说顺序数列的快排。但它的平摊期望时间是O(n log n) ,且O(n log n)记号中隐含的常数因子很小,比复杂度稳定等于O(n log n)的归并排序要小很多。所以,对绝大多数顺序性较弱的随机数列而言,快速排序总是优于归并排序。
//快速排序法
function sortQuick(arr) {
if (arr.length <= 1) {//递归结束判断条件
return arr;
} else {
var index = Math.floor(arr.length / 2);//取最中间的那个元素
var len = arr.splice(index, 1);
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++) {
if (arr[i] < len) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return sortQuick(left).concat(len, sortQuick(right));
}
}
3.选择排序法
原理:每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法
假定数组每次比较范围内第一个元素最小min,和剩下的比较,如果比假定的这个元素小,则令min为这个元素,直到找到最小的,然后交换位置,每比较一次,
就把最小的一位数找出来放数组最前面。
//选择排序
function sortSelect(arr) {
for (var i = 0; i < arr.length; i++) {
var min = arr[i];
var index = i;
for (var j = i + 1; j < arr.length; j++) {
if (arr[j] < min) {
min = arr[j];
index = j;
}
}
if (index != i) {
var temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
}
}
}
4.插入排序法
插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外(让数组多一个空间才有插入的位置),
而第二部分就只包含这一个元素(即待插入元素)。在第一部分排序完成后,再将这个最后元素插入到已排好序的第一部分中。
//插入排序
function sortInsert(arr) {
for (var i = 0; i < arr.length - 1; i++) {
var insert = arr[i + 1];
var index = i+1;
for(var j=i;j>=0;j--){
if(insert > arr[j]){
arr[j+1] = arr[j];
index = j;
}
}
arr[index] = insert;
}
}
5.哈希排序
原理:先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序
(增量足够小)时,再对全体元素进行一次直接插入排序。
//哈希排序
function sortShell(arr){
var len = arr.length,
temp,
gap = 1;
while(gap < len/3){
gap = gap*3+1;
}
for(gap;gap>0;gap = Math.floor(gap/3)){
for(var i=gap;i<len;i++){
temp = arr[i];
for(var j=i-gap;j>0&&arr[j]>temp;j-=gap){
arr[j+gap] = arr[j];
}
arr[j+gap] = temp;
}
}
return arr;
}
//哈希排序 function sortShell(arr){ var len = arr.length, temp, gap = 1; while(gap < len/3){ gap = gap*3+1; } for(gap;gap>0;gap = Math.floor(gap/3)){ for(var i=gap;i<len;i++){ temp = arr[i]; for(var j=i-gap;j>0&&arr[j]>temp;j-=gap){ arr[j+gap] = arr[j]; } arr[j+gap] = temp; } } return arr; }
本站提供的教程和内容信息仅限用于学习和研究目的;不得将上述内容用于商业或者非法用途,否则,一切后果自负。本站信息多数来自网络收集整理,版权争议与本站无关。您必须在下载后的24个小时之内,从您的电脑或手机中彻底删除,如果喜欢该内容,请购买正版,得到更好的服务。如有侵权请邮件联系我们处理,敬请谅解。
{{item.user_name}}
{{item.createAt }}