冒泡排序
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;}复制代码
j < len-1-i
的意思是:比较次数不包含当前元素和自身比较,且已经排好顺序的元素不需要再次参与排序,有助于性能提升。
选择排序(事件复杂度稳定)
function selectionSort(arr){ var len = arr.length; var minIndex, temp; 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; }}复制代码
插入排序
function insertionSort(arr) { var len = arr.length; var preIndex, current; for (var i = 1; i < len; i++) { preIndex = i - 1; current = arr[i]; while(preIndex >= 0 && arr[preIndex] > current) { arr[preIndex+1] = arr[preIndex]; preIndex--; } arr[preIndex+1] = current; } return arr;}复制代码
快速排序(效率高)
步骤:
- 在数据集之中,选择一个元素作为"基准"(pivot)。
- 所有小于"基准"的元素,都移到"基准"的左边;所有大于"基准"的元素,都移到"基准"的右边。
- 对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。
function quickSort(arr){ if(arr.length <= 1){ return arr}; var pivotIndex = Math.floor(arr.length / 2); var pivot = arr.splice(pivotIndex, 1)[0]; var left = []; var right = []; for(var i = 0; i < arr.length; i++){ if(arr[i] < pivot){ left.push(arr[i]); }else if(arr[i] > pivot){ right.push(arr[i]); } } return quickSort(left).concat([pivot], quickSort(right));}复制代码
未完待续。。。