冒泡排序O(n^2) =选择排序O(n^2)> 插入排序O(n^2)>希尔排序O(n^(3/2))>快速排序O(nlogn)
详解参考
https://www.jianshu.com/p/f1f2dc978762https://www.jianshu.com/p/8940e7030ff4
冒泡排序：从左往右比较并交换最大值得位置，将最大值放在最右侧；循环这一操作 选择排序：从左往右找到最小值并记录最小值的位置，然后将该最小值放在最左侧；循环这一操作
插入排序：左侧是排好序的部分，标记已经排序的位置，依次将标记位置右侧的值插入左侧已经排好序的部分
<!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title></title> </head> <body> <script> //创建列表类 function ArrayList(){ this.array = [] ArrayList.prototype.insert = function(item){ return this.array.push(item) } ArrayList.prototype.toString = function(){ return this.array.join('-') } //交换a1和a2的值 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(){ var length = this.array.length; //只比较还没有被排序的部分,每比较一次需要排序的元素就减少一个 for(let j =length-1;j>=0;j--){ for(let i=0;i<j;i++){ //将最大的数字放在数组的末尾 if(this.array[i]>this.array[i+1]){ this.swap(i,i+1) } } } } //选择排序 ArrayList.prototype.selectionSort = function(){ var length = this.array.length for(var j=0;j< length-1;j++){ var min = j for(var i=min+1; i<length;i++){ if(this.array[min]> this.array[i]){ min = i } } this.swap(min,j) } } //插入排序 ArrayList.prototype.insertSort = function(){ var length = this.array.length; var temp = null; var j = null //第一轮比较：this.array[0]当做已经排好序的部分 for(var i = 1;i<length;i++){ temp = this.array[i]; j = i; //在左侧已经排好序的部分中,从右往左依次比较, //若this.array[j-1]大于temp就往右移动一个位置,this.array[j] = this.array[j-1] //若this.array[j-1]小于temp就不移动,跳出while循环,将temp插入到当前位置(this.array[j]) while(this.array[j-1] > temp && j >0){ this.array[j] = this.array[j-1] j-- } this.array[j] = temp; } } //希尔排序 ArrayList.prototype.shellSort = function(){ var length = this.array.length; var gap = Math.floor(length/2) while(gap >=1){ for(var i = gap; i < length; i++){ var j= i; var temp = this.array[i] while(this.array[j-gap] > temp && j > gap-1){ this.array[j] = this.array[j-gap] j-=gap } this.array[j] = temp } gap = Math.floor(gap/2) } } //快速排序 //1.选择枢纽 ArrayList.prototype.median = function(left,right){ // 取出数组的中间位置 var center = Math.floor((left+right)/2) //判断大小并交换位置,保证left>center>right if(this.array[left] > this.array[center]){ this.swap(left,center) } if(this.array[center] > this.array[right]){ this.swap(center, right) } if(this.array[left] > this.array[right]){ this.swap(left,right) } //将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) } ArraryList.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.将 left大于枢纽的值 与 right小于枢纽的值 进行交换 while(true){ //++i 返回计算后的值 //从左向右找出大于枢纽的值 while(this.array[++i] > pivot){} //从右向左找出小于枢纽的值 while(this.array[--j] < pivot){} if(i <j){ this.swap(i,j) }else{ break; } } //5.将枢纽放置到当前i的位置 this.swap(i,right-1) //6.分别排序当前枢纽位置的左右两边的数字 this.quick(left,i-1) this.quick(i+1,right) } } var list = new ArrayList() list.insert(15) list.insert(10) list.insert(29) list.insert(600) list.insert(100) list.insert(29) list.insert(2) alert(list) // // list.bubbleSort() // alert(list) // alert('selection') // list.selectionSort() // list.insertSort() list.shellSort() alert(list) </script> </body> </html>
