摘要：快速排序，参考排序算法的完整实现各种排序算法的完整实现如下冒泡排序选择排序插入排序归并排序快速排序，参考排序方法验证冒泡排序选择排序插入排序归并排序快速排序源码地址的数据结构与算法三源码
1 排序和搜索算法 1.1 排序算法 1.1.1 冒泡排序
冒泡排序比较任何两个相邻的项,如果第一个比第二个大,则交换它们。元素项向上移动至正确的顺序,就好像气泡升至表面一样,冒泡排序因此得名。冒泡排序的时间复杂度为O(n2)。
//冒泡排序
bubbleSort: function() {
var self = this;
function swap(index1, index2) {
var aux = self.array[index2];
self.array[index2] = self.array[index1];
self.array[index1] = aux;
}
var length = this.array.length;
for (var i = 0; i < length; i++) {
for (var j = 0; j < length - 1 - i; j++) {
if (this.array[j] > this.array[j + 1]) {
swap(j, j + 1);
}
}
}
}
1.1.2 选择排序
选择排序算法是一种原址比较排序算法。选择排序大致的思路是找到数据结构中的最小值并将其放置在第一位,接着找到第二小的值并将其放在第二位,以此类推。选择排序的时间复杂度为O(n2)。
//选择排序
selectionSort:function(){
var length = this.array.length;
var indexMin;
for(var i = 0; i < length - 1; i++){
indexMin = i;
for(var j = i; j < length; j++){
if (this.array[indexMin] > this.array[j]) {
indexMin = j;
}
}
if (indexMin !== i) {
this.swap(indexMin,i);
}
}
}
1.1.3 插入排序
有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
insertionSort:function(){
var length = this.array.length;
var j;
var temp;
for(var i = 1; i < length; i++){
temp = this.array[i];
j = i;
while(j > 0 && this.array[j - 1] > temp){
this.array[j] = this.array[j - 1];
j--;
}
this.array[j] = temp;
}
}
1.1.4 归并排序
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。时间复杂度为O(nlogn)，空间复杂度为O(n)。
//归并排序
mergeSort:function(){
function mergeSortRec(array){
var length = array.length;
if (length === 1) {
return array;
}
var mid = Math.floor(length/2);
var left = array.slice(0,mid);
var right = array.slice(mid,length);
return merge(mergeSortRec(left),mergeSortRec(right));
}
function merge(left,right){
var result = [];
var il = 0;
var 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;
}
this.array = mergeSortRec(this.array);
}
1.1.5 快速排序
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。时间负责度为O(n^2)，并且比其他负责度为O(n^2)的排序算法要好。
//快速排序，参考http://www.ruanyifeng.com/blog/2011/04/quicksort_in_javascript.html
quickSort:function(){
function sort(array){
if (array.length <= 1) {
return array;
}
var pivotIndex = Math.floor(array.length/2);
var pivot = array.splice(pivotIndex,1)[0];
var left = [];
var right = [];
for(var i = 0; i < array.length; i++){
if (array[i] < pivot) {
left.push(array[i]);
}else{
right.push(array[i]);
}
}
return sort(left).concat([pivot],sort(right));
}
this.array = sort(this.array);
}
1.2 排序算法的完整实现
各种排序算法的完整实现如下：
function ArrayList() {
this.array = [];
}
ArrayList.prototype = {
constructor: ArrayList,
insert: function(item) {
this.array.push(item);
},
toString: function() {
return this.array.join();
},
swap: function(index1, index2) {
var aux = this.array[index2];
this.array[index2] = this.array[index1];
this.array[index1] = aux;
},
//冒泡排序
bubbleSort: function() {
var length = this.array.length;
for (var i = 0; i < length; i++) {
for (var j = 0; j < length - 1 - i; j++) {
if (this.array[j] > this.array[j + 1]) {
this.swap(j, j + 1);
}
}
}
},
//选择排序
selectionSort: function() {
var length = this.array.length;
var indexMin;
for (var i = 0; i < length - 1; i++) {
indexMin = i;
for (var j = i; j < length; j++) {
if (this.array[indexMin] > this.array[j]) {
indexMin = j;
}
}
if (indexMin !== i) {
this.swap(indexMin, i);
}
}
},
//插入排序
insertionSort: function() {
var length = this.array.length;
var j;
var temp;
for (var i = 1; i < length; i++) {
temp = this.array[i];
j = i;
while (j > 0 && this.array[j - 1] > temp) {
this.array[j] = this.array[j - 1];
j--;
}
this.array[j] = temp;
}
},
//归并排序
mergeSort: function() {
function mergeSortRec(array) {
var length = array.length;
if (length === 1) {
return array;
}
var mid = Math.floor(length / 2);
var left = array.slice(0, mid);
var right = array.slice(mid, length);
return merge(mergeSortRec(left), mergeSortRec(right));
}
function merge(left, right) {
var result = [];
var il = 0;
var 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;
}
this.array = mergeSortRec(this.array);
},
//快速排序，参考http://www.ruanyifeng.com/blog/2011/04/quicksort_in_javascript.html
quickSort:function(){
function sort(array){
if (array.length <= 1) {
return array;
}
var pivotIndex = Math.floor(array.length/2);
var pivot = array.splice(pivotIndex,1)[0];
var left = [];
var right = [];
for(var i = 0; i < array.length; i++){
if (array[i] < pivot) {
left.push(array[i]);
}else{
right.push(array[i]);
}
}
return sort(left).concat([pivot],sort(right));
}
this.array = sort(this.array);
}
};
排序方法验证：
function createNonSortedArray(size) {
var array = new ArrayList();
for (var i = size; i > 0; i--) {
//(function(i) {
array.insert(i);
//})(i);
}
return array;
}
//冒泡排序
var array = createNonSortedArray(5);
console.log(array.toString());
array.bubbleSort();
console.log(array.toString());
//选择排序
console.log(array.toString());
array.selectionSort();
console.log(array.toString());
//插入排序
console.log(array.toString());
array.insertionSort();
console.log(array.toString());
//归并排序
console.log(array.toString());
array.mergeSort();
console.log(array.toString());
//快速排序
console.log(array.toString());
array.quickSort();
console.log(array.toString());
源码地址
Javascript的数据结构与算法(三)源码
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/86659.html
摘要：像刚才的这幅图，就是二叉搜索树。而我们本文要学习的内容，就是如何写一个二叉搜索树。但在二叉搜索树中，我们把节点成为键，这是术语。前端路漫漫，且行且歌的前端乐园原文链接寒假前端学习学习数据结构与算法四二叉搜索树 本系列的第一篇文章: 学习JavaScript数据结构与算法（一），栈与队列第二篇文章：学习JavaScript数据结构与算法（二）：链表第三篇文章：学习JavaScript数据...
摘要：最近想要研究研究地形的渲染，然后就想起了四叉树，在网上看了一篇相关的文章，准备拿实现一下备用。四叉树的定义是它的每个节点下至多可以有四个子节点，通常把一部分二维空间细分为四个象限或区域并把该区域里的相关信息存入到四叉树节点中。 最近想要研究研究webgl地形的渲染，然后就想起了四叉树，在网上看了一篇相关的文章，准备拿javascript实现一下备用。 四叉树原理 （这部分就直...
摘要：算法性能提升图片算法处理实质原理其实是遍历像素点，对像素点的值进行改造。而像素点的数量与图片的大小尺寸成正向指数级增长，因此适当的缩放图片源后再去处理，对性能的提升十分巨大。 引言： 本系列现在构思成以下4个部分: 基础类型图片处理技术之缩放、裁剪与旋转(传送门)； 基础类型图片处理技术之图片合成(传送门)； 基础类型图片处理技术之文字合成(传送门)； 算法类型图片处理技术(传送门)...
阅读 2989·2021-11-25 09:43
阅读 3607·2021-11-24 11:13
阅读 3381·2021-10-14 09:42
阅读 2584·2021-09-23 11:53
阅读 3626·2021-09-22 15:57
阅读 3245·2021-09-02 09:54
阅读 3515·2019-08-30 13:47
阅读 1655·2019-08-29 16:55
