- 时间复杂的度
- 冒泡排序
- 选择排序
- 插入排序
- 归并排序
- 快速排序
- 计数排序
- 桶排序
- 基数排序
时间复杂的度 冒泡排序所有排序从小到大,本文排序算法全部都是以javascript为基础实现的
const bubbleSort = ( arr ) => { const { length } = arr; for(let i = 0; i < length; i++){ for (let j = 0; j < length - 1 - i; j++) { if( arr[j] > arr[j+1] ) [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; } } return arr; }选择排序
const selectionSort = ( arr ) => { const { length } = arr; let indexMin; for(let i = 0; i < length; i++){ indexMin = i; for (let j = 0; j < length - 1 - i; j++){ arr[indexMin] > arr[j] && (indexMin = j); } i !== indexMin && ([arr[i], arr[indexMin]] = [arr[indexMin], arr[i]]); } return arr; }插入排序
const insertionSort = ( arr ) => { const { length } = arr; let temp; for(let i = 1; i < length; i++){ let j = i; temp = arr[i]; while(j > 0 && arr[j - 1] > temp){ arr[j] = arr[j - 1]; j--; } arr[j] = temp; } return arr; }归并排序
const mergeSort = ( arr ) => { if(arr.length > 1){ const { length } = arr; const middle = Math.floor(length / 2); const left = mergeSort(arr.slice(0, middle)); const right = mergeSort(arr.slice(middle, length)); arr = merge(left, right); } return arr; } const merge = ( left, right ) => { let i = 0, j = 0; const result = []; while(i < left.length && j < right.length){ result.push(left[i] < right[j]? left[i++]: right[j++]); } return [...result, ...(i < left.length? left.slice(i): right.slice(j))]; }快速排序
const quickSort = ( arr ) => { quick(arr, 0, arr.length - 1); return arr; }; const quick = ( arr, left, right ) => { let index; if(arr.length > 1){ index = partition(arr, left, right); if(left < index - 1){ quick(arr, left, index - 1); } if(right > index){ quick(arr, index, right); } } } const partition = ( arr, left, right ) => { const pivot = arr[Math.floor((right + left) / 2)]; let i = left, j = right; while(i <= j){ while(arr[i] < pivot) i++; while(arr[j] > pivot) j--; if(i <= j){ [arr[i], arr[j]] = [arr[j], arr[i]]; i++; j--; } } return i; }计数排序
const countingSort = ( arr ) => { if (arr.length < 2) { return arr; } const maxValue = findMaxValue(arr); const counts = new Array(maxValue + 1); arr.forEach(element => { if (!counts[element]) { counts[element] = 0; } counts[element]++; }); let sortedIndex = 0; counts.forEach((count, i) => { while (count > 0) { arr[sortedIndex++] = i; count--; } }); return arr; } const findMaxValue = ( arr ) => { let max = arr[0]; for (let i = 1; i < arr.length; i++) { if (arr[i] > max) { max = arr[i]; } } return max; } const findMinValue = ( arr ) => { let min = arr[0]; for (let i = 1; i < arr.length; i++) { if (arr[i] < min) { min = arr[i]; } } return min; }桶排序
const bucketSort = ( arr, bucketSize = 5 ) => { if (arr.length < 2) { return arr; } const buckets = createBuckets(arr, bucketSize); return sortBuckets(buckets); } const createBuckets = ( arr, bucketSize ) => { let minValue = arr[0]; let maxValue = arr[0]; for (let i = 1; i < arr.length; i++) { if (arr[i] < minValue) { minValue = arr[i]; } else if (arr[i] > maxValue) { maxValue = arr[i]; } } const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1; const buckets = []; for (let i = 0; i < bucketCount; i++) { buckets[i] = []; } for (let i = 0; i < arr.length; i++) { const bucketIndex = Math.floor((arr[i] - minValue) / bucketSize); buckets[bucketIndex].push(arr[i]); } return buckets; } const sortBuckets = ( buckets ) => { const sortedArray = []; for (let i = 0; i < buckets.length; i++) { if (buckets[i] != null) { insertionSort(buckets[i]); sortedArray.push(...buckets[i]); } } return sortedArray; }基数排序
const radixSort = ( arr, radixBase = 10 ) => { if (arr.length < 2) { return arr; } const minValue = findMinValue(arr); const maxValue = findMaxValue(arr); let significantDigit = 1; while ((maxValue - minValue) / significantDigit >= 1) { arr = countingSortForRadix(arr, radixBase, significantDigit, minValue); significantDigit *= radixBase; } return arr; } const countingSortForRadix = ( arr, radixBase, significantDigit, minValue) => { let bucketsIndex; const buckets = []; const aux = []; for (let i = 0; i < radixBase; i++) { buckets[i] = 0; } for (let i = 0; i < arr.length; i++) { bucketsIndex = Math.floor(((arr[i] - minValue) / significantDigit) % radixBase); buckets[bucketsIndex]++; } for (let i = 1; i < radixBase; i++) { buckets[i] += buckets[i - 1]; } for (let i = arr.length - 1; i >= 0; i--) { bucketsIndex = Math.floor(((arr[i] - minValue) / significantDigit) % radixBase); aux[--buckets[bucketsIndex]] = arr[i]; } for (let i = 0; i < arr.length; i++) { arr[i] = aux[i]; } return arr; }