代码封装:
//创建列表类 function ArrayList() { //属性 this.array = []; //方法 //将我们数据可以插入到数组中的方法 ArrayList.prototype.insert = function (item) { this.array.push(item); } //toString ArrayList.prototype.toString = function () { return this.array.join(' '); } //实现排序算法 //交换两个位置的数据 ArrayList.prototype.swap = function (m, n) { var temp = this.array[m]; this.array[m] = this.array[n]; this.array[n] = temp; } //冒泡排序 ArrayList.prototype.bubbleSort = function () { //1.获取数组的长度 var length = this.array.length; for (var i = length - 1; i >= 0; i--) { //比较i和i+1两个数据,如果i位置的数据大于i+1位置的数据,交换数据 for (var j = 0; j < i; j++) { if (this.array[j] > this.array[j + 1]) { //交换数据 this.swap(j, j + 1); } } } } //选择排序 ArrayList.prototype.selectSort = function () { //1.获取数组的长度 var length = this.array.length; //2.外层循环,从0位置开始取数据 for (var j = 0; j < length - 1; j++) { var min = j; for (var i = min; i < length; i++) { if (this.array[min] > this.array[i]) { min = i; } } this.swap(min, j); } } //插入排序 ArrayList.prototype.insertSort = function () { //1.获取数组长度 var length = this.array.length; //2.外层循环:从第一个位置开始获取数据,像向前面局部有序进行插入 for (var i = 0; i < length; i++) { //3.内层循环:获取i位置的元素,和前面的数据依次进行比较 var temp = this.array[i]; var j = i; while (this.array[j - 1] > temp && j > 0) { this.array[j] = this.array[j - 1]; j--; } //4.将j位置的数据放置temp this.array[j] = temp; } } //希尔排序 ArrayList.prototype.shellSort = function(){ //1.获取数组的长度 var length = this.array.length; //2.初始化增量 var gap = Math.floor(length / 2); //3.while循环,gap不断减小 while(gap >= 1){ //4.以gap作为间隔,进行分组,对分组进行插入排序 for(var i = gap;i < length; i++){ var temp = this.array[i]; var j = i; while(this.array[j - gap] > temp && j > gap-1){ this.array[j] = this.array[j-gap]; j -= gap; } //5.将j位置的元素赋值temp this.array[j] = temp; } gap = Math.floor(gap / 2) } } //快速排序 //1.选中枢纽 ArrayList.prototype.median = function(left,right){ //1.取出中间的位置 var center = Math.floor((right + left)/2); //2.判断大小,进行交换 if(this.array[left] > this.array[center]){ this.swap(left,center); } if(this.array[left] > this.array[right]){ this.swap(left,right); } if(this.array[center] > this.array[right]){ this.swap(center,right); } //3.将center换到right-1的位置 this.swap(center,right-1); return this.array[right-1]; } //2.快速排序的实现 ArrayList.prototype.quickSort = function(){ this.quick(0,this.array.length-1) } ArrayList.prototype.quick = function(left,right){ //1.结束条件 if(left >= right) { return } //2.获取枢纽 var pivot = this.median(left,right); //3.定义变量用于记录当前找到的位置 var i = left; var j = right - 1; //4.进行交换 while(i<j){ while(this.array[++i] < pivot){} while(this.array[--j] > pivot){} if(i<j){ this.swap(i,j); }else{ break; } } //6.将枢纽放置在正确的位置 this.swap(i,right-1); //7.分而治之 this.quick(left,i-1); this.quick(i+1,right); } }
作者:cake_eat
链接:https://blog.csdn.net/cake_eat/article/details/111145612
来源:CSDN
著作权归作者所有,转载请联系作者获得授权,切勿私自转载。