从头开始复习算法之基础排序

栏目: 编程工具 · 发布时间: 4年前

内容简介:首先我们来说一说冒泡排序,首先我们来说一说冒泡排序的思想: 首先我们用图表的形式来模拟第一轮变换:我们发现冒泡的思想就是从数组的开始第一个数据开始不断的后一个数据做比较,如果前一个数据比后一个数据要大,就将数组的两个位置的数据进行调换。就这样不断的调换,我们就将n个数据里面的最大值调换到了数组的最后一位。当我冒泡完一轮之后,最后一个数字肯定是数组内的最大值,此时我们就只需要再去管数组内的n-1个数据了,我们再用同样的冒泡方式去处理这个n-1个数据。就在这样依次类推,直到将所有的数据都排列清除为止。

首先我们来说一说冒泡排序,首先我们来说一说冒泡 排序 的思想: 首先我们用图表的形式来模拟第一轮变换:

操作 0 1 2 3 4 5 6 7
原始数据 4 8 2 3 1 6 7 0
第一次排序 [4 8] 2 3 1 6 7 0
第二次排序 4 [2 8] 3 1 6 7 0
第三次排序 4 2 [3 8] 1 6 7 0
第四次排序 4 2 3 [1 8] 6 7 0
第五次排序 4 2 3 1 [6 8] 7 0
第六次排序 4 2 3 1 6 [7 8] 0
第七次排序 4 2 3 1 6 7 [0 8]

我们发现冒泡的思想就是从数组的开始第一个数据开始不断的后一个数据做比较,如果前一个数据比后一个数据要大,就将数组的两个位置的数据进行调换。就这样不断的调换,我们就将n个数据里面的最大值调换到了数组的最后一位。

当我冒泡完一轮之后,最后一个数字肯定是数组内的最大值,此时我们就只需要再去管数组内的n-1个数据了,我们再用同样的冒泡方式去处理这个n-1个数据。就在这样依次类推,直到将所有的数据都排列清除为止。

具体的代码实现如下:

function swap(arr,index1,index2){
	let temp = arr[index1];
	arr[index1] = arr[index2];
	arr[index2] = temp
}

function bubbleIndex(arr,n){
	for(let i =0;i<n;i++){
		if(arr[i]>arr[i+1]){
			swap(arr,i,i+1);
		}
	}
}

function bubbleSort(arr){
	let n = arr.length;
	while(n>=0){
		bubbleIndex(arr,n);
		n--;
	}
	return arr;
}
复制代码

二、 选择排序

然后我们再来看一下选择排序,选择排序可能理解上面比前一个要简单一点。它的思想是:每一次从待排序的数组n中选出最大的一个元素放在数组的第一个位置,此时我们第一个元素肯定是最大的元素,就不用管了。然后再从剩余n-1个元素中再去选择排序。以此类推,直到全部待排序的数组的元素全部排列完成。

具体的代码如下:

function swap(arr,index1,index2){
	let temp = arr[index1];
	arr[index1] = arr[index2];
	arr[index2] = temp
}

function findMaxPos(arr,n,length){
	let pos = 0;
	let max =Number.MIN_SAFE_INTEGER;
	for(let i=n;i<length;i++){
		if(max <= arr[i]){
			max = arr[i];
			pos = i;
		}
	}
	swap(arr,n,pos)
}

function selectSort(arr){
	let length = arr.length;
	let n=0;
	while(n<length){
		findMaxPos(arr,n,length)
		n++;
	}
	return arr
}
复制代码

三、 插入排序

最后我们再来讲一讲插入排序: 我们还是用图表的形式来进行第一轮操作讲解吧:

操作 0 1 2 3 4
原始数据 1 3 4 5 2
第一次操作 1 3 4 [2 5]
第一次操作 1 3 [2 4] 5
第三次操作 1 [2 3] 4 5
停止 1 2 3 4 5

首先我们取一个部分有序数组,从第一个无序元素开始取待插入的元素逐个与前一个元素相比较,如果前一个元素比待插入元素要大,就交换两者的位置,直到前一个元素比待插入元素要小时候停止。进入下一轮循环,直到排完数组的所有元素为止。 这里很多人可能会问了,数组要是全部都是乱的怎么办? 那就从数组的第二个元素开始插入,一个元素的数组可能是有序的吧!

function swap(arr,index1,index2){
	let temp = arr[index1];
	arr[index1] = arr[index2];
	arr[index2] = temp
}

function insertIndex(arr,n){
	for(let i=n-1;i>0;i--){
		if(arr[i]<arr[i-1]){
			swap(arr,i,i-1);
		}
	}
}

function insertSort(arr){
	let length = arr.length;
	if(length<=0) return arr;
	let n=0
	while(n<length){
		insertIndex(arr,n)
		n++;
	}
	return arr;
}
复制代码

说在最后

首先关于这三个算法呢?我大概花了不到20分钟的时间就写出来了,可能代码有点繁琐,也可能有些漏洞 如果存在错误请大家指正。

然后关于排序这一块呢!其实是面试经常会考的问题,昨天没事儿就简单的复习了一下冒泡排序、选择排序、插入排序、归并排序、堆排序和快速排序。其实排序这一块,代码敲起来还是比较简单的,关键是要理解排序的思想,如果思想理解透彻了 其实写代码 应该是手到擒来的。接下来看怎么能把快排和归并排序用最简单的办法给讲出来。今天就到这里了,中午不睡,下午崩溃 拜了个拜!


以上所述就是小编给大家介绍的《从头开始复习算法之基础排序》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

计算机程序设计艺术(第3卷)-排序和查找(英文影印版)

计算机程序设计艺术(第3卷)-排序和查找(英文影印版)

(美)Donald E.Knuth / 清华大学出版社 / 2002-9 / 85.00元

《计算机程序设计艺术排序和查找(第3卷)(第2版)》内容简介:这是对第3卷的头一次修订,不仅是对经典计算机排序和查找技术的最全面介绍,而且还对第1卷中的数据结构处理技术作了进一步的扩充,通盘考虑了将大小型数据库和内外存储器。它遴选了一些经过反复检验的计算机方法,并对其效率做了定量分析。第3卷的突出特点是对“最优排序”一节作了修订,对排列论原理与通用散列法作了全新讨论。一起来看看 《计算机程序设计艺术(第3卷)-排序和查找(英文影印版)》 这本书的介绍吧!

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

URL 编码/解码
URL 编码/解码

URL 编码/解码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具