注册
登录
前言读者自行尝试可以想看源码戳这(https://github.com/damonare/Sorts)，博主在github建了个库，读者可以Clone下来本地尝试。此博文配合源码体验更棒哦
JavaScript可谓风头无两，已经坐上了头把交椅。
十大排序算法或是和十大排序算法同等难度的 )，但就是之前没用javascript实现过或是没仔细看过相关算法的原理，导致写起来浪费很多时间。所以撸一撸袖子决定自己查资料自己总结一篇博客等用到了直接看自己的博客就OK了，正所谓靠天靠地靠大牛不如靠自己(ˉ(∞)ˉ)。
正文排序算法说明(1)排序的定义：对一序列对象根据某个关键字进行排序;输入：n个数：a1,a2,a3,…,an 输出：n个数的排列:a1’,a2’,a3’,…,an’，使得a1’ 再讲的形象点就是排排坐，调座位，高的站在后面，矮的站在前面咯。 (2)对于评述算法优劣术语的说明稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面; 不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面; 内排序：所有排序操作都在内存中完成; 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行; 时间复杂度: 一个算法执行所耗费的时间。 空间复杂度: 运行完一个程序所需内存的大小。 关于时间空间复杂度的更多了解请戳这里(http://blog.csdn.net/booirror/article/details/7707551/)，或是看书程杰大大编写的《大话数据结构》还是很赞的，通俗易懂。 (3)排序算法图片总结(图片来源于网络):排序对比：
图片名词解释：n: 数据规模 k:“桶”的个数 In-place: 占用常数内存，不占用额外内存 Out-place: 占用额外内存 排序分类：
1.冒泡排序(Bubble Sort)好的，开始总结第一个排序算法，冒泡排序。我想对于它每个学过C语言的都会了解的吧，这可能是很多人接触的第一个排序算法。 (1)算法描述冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 (2)算法描述和实现具体算法描述如下：
JavaScript代码实现：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[j+1]) { //相邻元素两两对比
var temp = arr[j+1]; //元素交换
arr[j+1] = 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]
改进冒泡排序：设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。 改进后算法如下: function bubbleSort2(arr) {
console.time('改进后冒泡排序耗时');
var i = arr.length-1; //初始时,最后位置保持不变
while ( i> 0) {
var pos= 0; //每趟开始时,无记录交换
for (var j= 0; j< i; j++)
if (arr[j]> arr[j+1]) {
pos= j; //记录交换的位置
var tmp = arr[j]; arr[j]=arr[j+1];arr[j+1]=tmp;
}
i= pos; //为下一趟排序作准备
}
console.timeEnd('改进后冒泡排序耗时');
return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(bubbleSort2(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。 改进后的算法实现为: function bubbleSort3(arr3) {
var low = 0;
var high= arr.length-1; //设置变量的初始值
var tmp,j;
console.time('2.改进后冒泡排序耗时');
while (low < high) {
for (j= low; j< high; ++j) //正向冒泡,找到最大者
if (arr[j]> arr[j+1]) {
tmp = arr[j]; arr[j]=arr[j+1];arr[j+1]=tmp;
}
--high; //修改high值, 前移一位
for (j=high; j>low; --j) //反向冒泡,找到最小者
if (arr[j]<arr[j-1]) {
tmp = arr[j]; arr[j]=arr[j-1];arr[j-1]=tmp;
}
++low; //修改low值,后移一位
}
console.timeEnd('2.改进后冒泡排序耗时');
return arr3;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(bubbleSort3(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
三种方法耗时对比：
由图可以看出改进后的冒泡排序明显的时间复杂度更低，耗时更短了。读者自行尝试可以戳这，博主在github建了个库，读者可以Clone下来本地尝试。此博文配合源码体验更棒哦~~~ 冒泡排序动图演示:
(3)算法分析
当输入的数据已经是正序时(都已经是正序了，为毛何必还排序呢….)
当输入的数据是反序时(卧槽，我直接反序不就完了….)
2.选择排序(Selection Sort)表现最稳定的排序算法之一(这个稳定不是指算法层面上的稳定哈，相信聪明的你能明白我说的意思2333)，因为无论什么数据进去都是O(n2)的时间复杂度…..所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。 (1)算法简介选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小(大)元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小(大)元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 (2)算法描述和实现n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：
Javascript代码实现: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]
选择排序动图演示：
(3)算法分析
3.插入排序(Insertion Sort)插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。当然，如果你说你打扑克牌摸牌的时候从来不按牌的大小整理牌，那估计这辈子你对插入排序的算法都不会产生任何兴趣了….. (1)算法简介插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序(即只需用到O(1)的额外空间的排序)，因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。 (2)算法描述和实现一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
Javascript代码实现: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!';
}
}
改进插入排序：查找插入位置时使用二分查找的方式 function binaryInsertionSort(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], left = 0, right = i - 1;
while (left <= right) {
var middle = parseInt((left + right) / 2);
if (key < array[middle]) {
right = middle - 1;
} else {
left = middle + 1;
}
}
for (var j = i - 1; j >= left; j--) {
array[j + 1] = array[j];
}
array[left] = key;
}
console.timeEnd('二分插入排序耗时：');
return array;
} else {
return 'array is not an Array!';
}
}
var arr=[3,44,38,5,47,15,36,26,27,2,46, |
|
声明：文章版权归原作者所有 部分文章转自互联网 如有侵权请联系
[邮箱地址] 删除
|
