1.冒泡排序
(1)依次比较相邻的两个元素,如果后一个小于前一个,则交换。
(2)重复以上的操作
注:每进行一轮,最后都已经是最大的了,因此后一轮需要比较次数可以比上一次少一个
function bubbleSort(arr){ var length = arr.length; for(var i = 0;i<length-1;i++){ for(var j=0;j<length-1-i;j++){ if(arr[j]>arr[j+1]){ var temp = arr[j+1]; arr[j+1] = arr[j]; arr[j] = temp; } } } return arr; }
2.选择排序
(1)在未排序序列中找到最小(大)元素,存放到排序序列的起始位置
(2)再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾
(3)重复(2)直至排完
function selectionSort(arr) { var length = arr.length; var minIndex, temp; for (var i = 0; i < length - 1; i++) { minIndex = i; for (var j = i + 1; j < length; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } return arr; }
3.插入排序
(1)将第一个元素看作已经被排序
(2)取出下一个元素,在已排序的序列中比较已排序序列中的元素和新元素,如果已排序的元素大于新元素,将已排序元素移到下一个位置
(3)重复(2)直到已排序的元素小于或等于新元素的位置,将新元素插入到该位置后
(4)重复(2)(3)
function insertSort(arr){ var length = arr.length; for(var i=1;i<length;i++){ var key = arr[i]; var j= i-1; while(j>=0 && arr[j]>key){ arr[j+1]=arr[j]; j--; } arr[j+1]=key; } return arr; }
4.快速排序
(1)在数据中,选择一个元素作为“基准”(pivot)
(2)所有小于“基准”的元素,都移到“基准”的左边;所有大于“基准”的元素,都移到“基准”的右边
(3)对“基准”左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止
function quickSort(arr){ if(arr.length <=1){ return arr; } var keyIndex = Math.floor(arr.length/2); var key=arr.splice(keyIndex,1)[0]; var left=[]; var right =[]; for(var i=0;i<arr.length;i++){ if(arr[i]<key){ left.push(arr[i]); }else{ right.push(arr[i]); } } return quickSort(left).concat([key],quickSort(right)); }