dtcms模板 echarts golang爬虫 less centos7 Android开发 javascript ssl datepicker db2 支付网站建设 cmd查看mysql版本 拼接json字符串 java时间戳 如何升级python linux查看防火墙 phpstorm插件 python获取日期 python的random模块 java连接mysql java语言 java循环语句 java基础课程 javafloat java基本数据结构 java中new java入门基础 java配置jdk linux硬盘 linux安装系统 hadoop权威指南 microkms 骁龙660和625 修改tomcat端口 linux解压tar 苹果手机老是自动重启 flash制作工具 subscribe 视频加字幕软件 js刷新页面
当前位置: 首页 > 学习教程  > 编程语言

JS 算法——排序

2020/9/19 14:48:30 文章标签:

前言:

常见排序算法:冒泡排序,选择排序,插入排序,快速排序,归并排序,谢尔排序,堆积排序 ,已经 JS 中的 sort  排序方法的一个总结。(算法核心思想,代码,时间 / 空间复杂度 等)


  • 冒泡排序 ?

核心思想:从未排序元素的第一个开始,依次与相邻元素比较,大的往后沉,小的往前浮,比较趟数不一定。(冒泡排序比较任何两个相邻的项,如果第一个比第二个大,则交换它们)。

  • 时间复杂度为 O(n^2);
  • 排序趟数与原始序列中数据元素的排列有关(1 ~ (n-1次));
  • 是一种 稳定性 排序方法。
  • 它在所有排序算法中最简单,从运行的时间来看,冒泡排序是最差的一个。
function modifiedBubbleSort(arr){
    for(var i=0; i<arr.length; i++){
        for(var j=0; j<arr.length-i-1; j++){
            if(arr[j] > arr[j+1){
                swap(arr, j, j+1);
            }
        }
    }
}
function swap(arr, index1, index2){
    var temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
}
  • 选择排序 ?

核心思想:一共 n-1 趟,每趟从未排序的元素中选出一个值最小的元素放在这些未排序元素的最前面,直到最后一个。

算法步骤:1,在未排序元素中找到最小的那个元素;2,插入到未排序元素的第一个。

  • 时间复杂度为 O(n^2);
  • 元素之间的比较次数与原始序列中元素的分布状态无关;
  • 是一种 非稳定性 排序方法。(非稳定是指,有相同元素时,进行排序,会改变其位置)。
function selectionSort(arr){
    // 获取数组的长度
    var len = arr.length;
    // 标记第i个最小值下标
    var indexMin;
    // 外层循环,n-1趟
    for(var i=0; i< len-1; i++){
        // 最小下标初始化,从i开始找
        indexMin = i;
        // 内层循环,从 i 到 len 之间查找这一趟的最小值
        for(var j=i; j<len; j++){
            if(arr[indexMin]) > arr[j]){
                indexMin = j;
            }
        }
        // 交换元素,这一趟最小值和第 i 个元素
        if(i !== indexMin){
            swap(arr, i, indexMin);
        }
    }
    return arr;
}
function swap(arr, index1, index2){
    var temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
}
  • 插入排序 ?

核心思想:从第 2 个元素开始,一共 n-1 趟,每趟将未排序的第一个元素插入到已排序的元素的合适位置,直到最后一个元素。

算法步骤:1,对比确定插入位置;2,插入元素。

  • 插入排序算法的改进:如果初始序列比较有序,从大到小,从左边开始查找定位;从小到大,从右边开始查找定位。
  • 如果初始序列是无序的,采用 二分查找 的方式去定位。
  • 时间复杂度为 O(n^2) ,是一种 稳定性 排序方法。(稳定排序算法是指,相同的两个值,排序下来位置不变的。
function insertionSort(arr){
    // 记录数组的长度
    var len = arr.length;
    // 声明全局变量
    var j,temp;
    // 外层循环,控制趟数,从第二个元素开始,总共n-1趟
    for(var i=1; i<len; i++){
        // 标记第几趟就是第几个元素进行插入定位排序
        j = i;
        // 存储当前要定位插入排序的元素
        temp = arr[i];
        // 内层循环,查找定位,进行元素插入
        while(j>0; && arr[j-1]>temp){
            arr[j] = arr[j-1];
            j--;
        }
        arr[j] = temp;
    }
}
  • 归并排序 ?

核心思想 :归并排序是一种 分治算法 。其思想是将原始数组切分成较小的数组。直到每个小数组只有一个位置,接着将小数组归并成较大的数组,直到最后只有一个排序完毕的大数组。由于是分治法,归并排序也是递归的。

function mergeSort(arr){
	var length = arr.length;
	if(length === 1){
		return arr;
	}
	var mid = Math.floor(length / 2);
	var left = arr.slice(0, mid);
	var right = arr.slice(mid, length);
	return merge(mergeSort(left), mergeSort(right));
}
			
function merge(left, right){
	var result = [];
	var iL = iR = 0;
	while(iL < left.length && iR < right.length){
		if(left[iL] < right[iR]){
			result.push(left[iL++]);
		}else{
			result.push(right[iR++]);
		}
	}
	while(iL < left.length){
		result.push(left[iL++]);
	}
	while(iR < right.length){
		result.push(right[iR++]);
	}
	return result;
}
  • 快速排序 ?

核心思想:从当前参加排序的元素中任选一个元素与当前参加排序的那些元素进行比较,凡是小于该元素的元素都移到该元素的前面,凡是大于该元素都移到该元素的后面。分别对两部分重复上述过程,直到排序结束。该过程是一个递归的过程。每一趟至少可以确定一个元素的最终位置。

算法实现步骤:

  • 首先,从数组中选择中间一项作为主元。
  • 创建两个指针,左边一个指向数组的第一项,右边一个指向数组的最后一项。移动左指针直到找到一个比主元大的数,接着移动右指针直到找到一个比主元小的元素,然后交换它们,重复这个操作,直到左指针超过了右指针。这个过程将使得比主元小的值都排在主元之前,而比主元大的值都排在主元之后,这一步叫划分操作。
  • 接着,算法对划分后的小数组重复之前的两个操作,直至数组已完全排序。

时间复杂度为 O(nlog2^n),如果初始序列是顺序或者逆序,快速排序沦落为慢速排序。

function quickSort(arr,left,right){
	var index;
	if(arr.length > 1){
		index = partition(arr,left,right);
		if(left < index - 1){
			quickSort(arr,left,index-1);
		}
		if(index < right){
			quickSort(arr,index,right);
		}
	}
}
			
function partition(arr,left,right){
	var pivot = arr[Math.floor((right+left) / 2)];
	var i = left;
	var j = right;
	while(i<=j){
		while(arr[i]<pivot){
			i++;
		}
		while(arr[j]>pivot){
			j--;
		}
		if(i<=j){
			swapQuickStort(arr,i,j);
			i++;
			j--;
		}
	}
	return i;
}
			
function swapQuickStort(arr,index1,index2){
	var temp = arr[index1];
	arr[index1] = arr[index2];
	arr[index2] = temp;
}
			
  • 谢尔排序 ?

核心思想:也叫缩小增量排序法。首先确定一个元素的间隔数gap。将参加排序的元素按照 gap 分隔成若干子序列,然后对各个子序列采用某一种排序方法进行排序;此后减少 gap 值,重复上述过程,直到 gap 小于 1。

  • 时间复杂度在 O(nlog2^n)O(n^2) 之间,小于 O(n^3/2);
  • 时间复杂度和 gap 分割方法有关;
  • 是一种 非稳定性 排序方法。
function shellSort(arr,len){
	var gap = len % 2 === 0 ? len : len+1 ;
	var flag;
	while(gap > 1){
		gap = gap / 2;
		do{
			flag = 0;
			for(var i=0; i<len - gap; i++){
				var j = i + gap ;
				if(arr[i] > arr[j]){
					var temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
					flag = 1;
				}
			}
		}while(flag != 0);
	}
	return arr;
}
  • 堆积排序 ?

核心思想:每一趟将所有未排序的元素组成一个大顶堆积(父节点大于左右子节点),将堆积的第一个元素和堆积的最后一个元素交换位置,直到最后一个元素。核心是将序列构建成堆积。堆积是一颗完全二叉树。

时间复杂度 O(nlog2^n)

var len; // 因为声明的多个函数都需要数据长度,所以把len设置成为全局变量
function buildMaxHeap(arr) { // 建立大顶堆
	len = arr.length;
	for (var i = Math.floor(len / 2); i >= 0; i--) {
		heapify(arr, i);
	}
}
function heapify(arr, i) { // 堆调整
	var left = 2 * i + 1,
		right = 2 * i + 2,
		largest = i;
	if (left < len && arr[left] > arr[largest]) {
		largest = left;
	}
	if (right < len && arr[right] > arr[largest]) {
	    largest = right;
	}
	if (largest != i) {
		swap(arr, i, largest);
		heapify(arr, largest);
	}
}

function swap(arr, i, j) {
	var temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

function heapSort(arr) {
	buildMaxHeap(arr);
	for (var i = arr.length - 1; i > 0; i--) {
		swap(arr, 0, i);
		len--;
		heapify(arr, 0);
	}
	return arr;
}
  • JS 中 sort 排序 ?

内部原理:冒泡排序。

JavaScript中数组的 sort() 方法主要用于对数组的元素进行排序。其中,sort()方法有一个可选参数。但是,此参数必须是函数。 数组在调用 sort()方法时,如果没有传参将按字母顺序(字符编码顺序)对数组中的元素进行排序,如果想按照其他标准进行排序,就需要进行传一个参数且为函数,该函数要比较两个值,并且会返回一个用于说明这两个值的相对顺序的数字。

var arr = [3,1,5,8,28];
// 正向
var arr1 = arr.sort(function(a ,b){
    return a-b;
})
// 反向
var arr2 = arr.sort(function(a, b){
    return b-a;
});

  • 总结 : 

稳定性:

  • 稳定归并排序、冒泡排序、插入排序,基数排序。
  • 不稳定选择排序、快速排序、希尔排序、堆排序。

时间复杂度:

  • 最基础的四个算法:冒泡、选择、插入、快排 中,快排的 时间复杂度 最小 O(n*log2n),其他都是O(n2)。

本文链接: http://www.dtmao.cc/news_show_200185.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?