js十大经典算法排序

js十大经典算法排序

一、冒泡排序。二、选择排序。三、插入排序。四、希尔排序。五、归并排序六、快速排序七、堆排序八、计数排序九、桶排序十、基数排序

visualgo算法排序可视化：https://visualgo.net/zh/

一、冒泡排序。

/** * 冒泡排序 * @param {Array} arr - 数组 * @returns {Array} - 排序好的数组 */ console.time('冒泡排序') function bubbleSort(arr) { let len = arr.length; let temp; for (let i = 0; i < len; i++) { for (let j = 0; j < len - 1 - i; j++) { // 如果后边的比较小，和前面的换下位置。 if (arr[j] > arr[j + 1]) { temp = arr[j + 1]; arr[j + 1] = arr[j]; arr[j] = temp } } } return arr } let arr = [1, 2, 234, 235, 23452, 234525, 4, 2, 5] console.log(bubbleSort(arr)) console.timeEnd('冒泡排序')

二、选择排序。

/** * 选择排序 * @param {Array} arr - 数组 * @returns {Array} - 排序好的数组 */ console.time('选择排序') function selectionSort(arr) { let len = arr.length; let temp, minIndex; for (let i = 0; i < len - 1; i++) { minIndex = i for (let j = i + 1; j < len; j++) { if (arr[j] < arr[minIndex]) { minIndex = j } } temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp } return arr } let arr = [1, 2, 234, 235, 23452, 234525, 4, 2, 5] console.log(selectionSort(arr)) console.timeEnd('选择排序')

三、插入排序。

/** * 插入排序 * @param {Array} arr * @returns {Array} */ console.time('插入排序') function insertionSort(arr) { let len = arr.length; let preIndex, current; for (let 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 } let arr = [1, 2, 234, 235, 23452, 234525, 4, 2, 5] console.log(insertionSort(arr)) console.timeEnd('插入排序')

四、希尔排序。

/** * 希尔排序,优化版的插入排序 * @param {Array} arr * @returns {Array} */ console.time('希尔排序') function shellSort(arr) { let len = arr.length; let temp, gap = 1; while (gap < len / 3) { gap = gap * 3 + 1; } for (gap; gap > 0; gap = Math.floor(gap / 3)) { for (let i = gap; i < len; i++) { temp = arr[i]; for (var j = i - gap; j >= 0 && arr[j] > temp; j -= gap) { arr[j + gap] = arr[j] } arr[j + gap] = temp } } return arr } let arr = [1, 2, 234, 235, 23452, 234525, 4, 2, 5] console.log(shellSort(arr)) console.timeEnd('希尔排序')

五、归并排序

/** * 归并排序 * @param {Array} arr * @returns {Array} */ console.time('归并排序') function mergeSort(arr) { let len = arr.length; if (len << 2) { return arr; } let middle = Math.floor(len / 2), left = arr.slice(0, middle), right = arr.slice(middle); return merge(mergeSort(left), mergeSort(right)) } function merge(left, right) { let result = []; while (left.length && right.length) { if (left[0] <= right[0]) { result.push(left.shift()) } else { result.push(right.shift()) } } while (left.length) { result.push(left.shift()) } while (right.length) { result.push(right.shift()) } return result } let arr = [1, 2, 234, 235, 23452, 234525, 4, 2, 5] console.log(mergeSort(arr)) console.timeEnd('归并排序')

六、快速排序

/** * 快速排序 * @param {Array} arr * @returns {Array} */ console.time('快速排序') function quickSort(arr, left, right) { let len = arr.length, partitionIndex; left = typeof left != 'number' ? 0 : left; right = typeof right != 'number' ? len - 1 : right; if (left < right) { partitionIndex = partition(arr, left, right); quickSort(arr, left, partitionIndex - 1); quickSort(arr, partitionIndex + 1, right); } return arr; } function partition(arr, left, right) { let pivot = left, index = pivot + 1; for (let i = index; i <= right; i++) { if (arr[i] < arr[pivot]) { swap(arr, i, index); index++; } } swap(arr, pivot, index - 1); return index - 1 } function swap(arr, i, j) { let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } let arr = [1, 2, 234, 235, 23452, 234525, 4, 2, 5] console.log(quickSort(arr)) console.timeEnd('快速排序')

七、堆排序

/** * 堆排序 * @param {Array} arr * @returns {Array} */ console.time('堆排序') var len; //因为声明的多个函数都需要数据长度，所以把len设置成为全局变量 function buildMaxHeap(arr) { //建立大顶堆 len = arr.length; for (var i = Math.floor(len / 2); i >= 0; i--) { heapify(arr, i); } return arr } function heapify(arr, i) { //堆调整 var left = 2 * i + 1, right = 2 * i + 2, largest = i; if (left < len && arr[left] > arr[largest]) { largest = left; } if (right < len && arr[right] > arr[largest]) { largest = right; } if (largest != i) { swap(arr, i, largest); heapify(arr, largest); } } function swap(arr, i, j) { var temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } function heapSort(arr) { buildMaxHeap(arr); for (var i = arr.length - 1; i > 0; i--) { swap(arr, 0, i); len--; heapify(arr, 0); } return arr; } let arr = [1, 2, 234, 235, 23452, 234525, 4, 2, 5] console.log(buildMaxHeap(arr)) console.timeEnd('堆排序')

八、计数排序

/** * 计数排序 * @param {Array} arr * @returns {Array} */ console.time('计数排序') function countingSort(arr, maxValue) { var bucket = new Array(maxValue + 1), sortedIndex = 0; arrLen = arr.length, bucketLen = maxValue + 1; for (var i = 0; i < arrLen; i++) { if (!bucket[arr[i]]) { bucket[arr[i]] = 0; } bucket[arr[i]]++; } for (var j = 0; j < bucketLen; j++) { while (bucket[j] > 0) { arr[sortedIndex++] = j; bucket[j]--; } } return arr; } let arr = [1, 2, 234, 235, 23452, 234525, 4, 2, 5] console.log(countingSort(arr)) console.timeEnd('计数排序')

九、桶排序

/** * 桶排序 * @param {Array} arr * @returns {Array} */ console.time('桶排序') function bucketSort(arr, bucketSize) { if (arr.length === 0) { return arr; } var i; var minValue = arr[0]; var maxValue = arr[0]; for (i = 1; i < arr.length; i++) { if (arr[i] < minValue) { minValue = arr[i]; //输入数据的最小值 } else if (arr[i] > maxValue) { maxValue = arr[i]; //输入数据的最大值 } } //桶的初始化 var DEFAULT_BUCKET_SIZE = 5; //设置桶的默认数量为5 bucketSize = bucketSize || DEFAULT_BUCKET_SIZE; var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1; var buckets = new Array(bucketCount); for (i = 0; i < buckets.length; i++) { buckets[i] = []; } //利用映射函数将数据分配到各个桶中 for (i = 0; i < arr.length; i++) { buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]); } arr.length = 0; for (i = 0; i < buckets.length; i++) { insertionSort(buckets[i]); //对每个桶进行排序，这里使用了插入排序 for (var j = 0; j < buckets[i].length; j++) { arr.push(buckets[i][j]); } } return arr; } let arr = [1, 2, 234, 235, 23452, 234525, 4, 2, 5] console.log(bucketSort(arr)) console.timeEnd('桶排序')

十、基数排序

/** * 基数排序 * @param {Array} arr * @returns {Array} */ console.time('基数排序') //LSD Radix Sort var counter = []; function radixSort(arr, maxDigit) { var mod = 10; var dev = 1; for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) { for (var j = 0; j < arr.length; j++) { var bucket = parseInt((arr[j] % mod) / dev); if (counter[bucket] == null) { counter[bucket] = []; } counter[bucket].push(arr[j]); } var pos = 0; for (var j = 0; j < counter.length; j++) { var value = null; if (counter[j] != null) { while ((value = counter[j].shift()) != null) { arr[pos++] = value; } } } } return arr; } let arr = [1, 2, 234, 235, 23452, 234525, 4, 2, 5] console.log(radixSort(arr)) console.timeEnd('基数排序')