提问式算法速通--排序

ask：JS 实现快速排序

answer：这是一个简单的快速排序实现，可以根据需要进行优化。

const quickSort = (arr)=>{
  if(arr.length<=1) return arr
  const left = [],right = [],center = arr[0]
  for(let i = 1; i < arr.length; i++){
	if(arr[i] < center){
	  left.push(arr[i])
	}else{
	  right.push(arr[i])
	}
  }
  return [...quickSort(left), center, ...auickSort(right)]
}

ask：如果要优化，有哪些优化方向

answer：针对小数组的优化： 对于小规模的数组，使用插入排序可能比快速排序更有效。可以在递归的过程中切换到插入排序，从而减少递归的深度。尾递归优化： 尾递归是一种优化技术，可以减少递归调用的堆栈空间使用。在一些 JavaScript 引擎中，尾递归优化可能会生效，但并非所有都支持。三路快速排序： 为了处理重复元素，可以采用三路快速排序，将数组划分为小于、等于和大于基准点的三个部分，以减少相同元素的多次比较。

ask：JS 实现插入排序

answer：

const insertSort = (arr) => {
	const n = arr.length
	for (let i = 1; i < n; i++) {
		let one = arr[i]
		let j = i - 1
		while (j > -1 && arr[j] > one) {
			arr[j + 1] = arr[j]
			j--
		}
		arr[j + 1] = one
	}
	return arr
}

ask：JS 实现选择排序

answer：

const selectSort = (arr) => {
	const n = arr.length
	for (let i = 0; i < n - 1; i++) {
		let min = i
		for (let j = i + 1; j < n; j++) {
			if (arr[j] < arr[min]) {
				min = j
			}
		}
		if (min != i) {
			[arr[i], arr[min]] = [arr[min], arr[i]]
		}
	}
	return arr
}

ask：还有那些排序算法

answer：

除了快速排序、选择排序，还有许多其他排序算法，其中一些常见的包括：

冒泡排序（Bubble Sort）：通过多次遍历数组，比较相邻元素并交换，将最大（或最小）元素冒泡到数组末尾（或开头）。
插入排序（Insertion Sort）：通过构建有序序列，逐个将未排序的元素插入到已排序部分的合适位置。
归并排序（Merge Sort）：采用分治法，将数组分为两个子数组，分别排序，然后合并这两个子数组以得到最终有序数组。
堆排序（Heap Sort）：利用堆的数据结构进行排序，通过构建最大堆或最小堆来实现。
计数排序（Counting Sort）：针对具有一定范围的整数进行排序，通过统计每个元素出现的次数并计算累积次数，然后将元素放置到正确的位置。
桶排序（Bucket Sort）：将元素分配到不同的桶中，每个桶内再进行排序，最后按顺序合并各个桶的元素。
基数排序（Radix Sort）：按照数字的个位、十位、百位等顺序进行排序，是一种多关键字的排序算法。

ask：JS 实现归并排序

answer：

const mergeSort = (arr = []) => {
	if (arr.length <= 1) return arr
	const mIndex = Math.floor(arr.length / 2)
	const left = arr.slice(0, mIndex)
	const right = arr.slice(mIndex)
	return merge(mergeSort(left), mergeSort(right))
}
const merge = (left = [], right = []) => {
	let arr = [], rIndex = 0, lIndex = 0
	while (lIndex < left.length && rIndex < right.length) {
		if (left[lIndex] < right[rIndex]) {
			arr.push(left[lIndex])
			lIndex++
		} else {
			arr.push(right[rIndex])
			rIndex++
		}
	}
	return arr.concat(left.slice(lIndex).concat(right.slice(rIndex)))
}

JS实现冒泡排序

const bubbleSort = (arr=[])=>{
	const n = arr.length
	for(let i = 0;i<n-1;i++){
		for(let j = 0;j<n-1-i;j++){
			if(arr[j]>arr[j+1]){
				[arr[j],arr[j+1]] = [arr[j+1],arr[j]]
			}
		}
	}
	return arr
}

JS实现桶排序

桶排序的思路是，当元素均匀分布在一个范围内的情况，然后对每个桶内的元素进行排序，最后合并，实现
最终还是需要一个排序方法

分别说明上面排序的时间复杂度

快速排序（Quick Sort）:平均时间复杂度：O(n log n)最坏情况时间复杂度：O(n^2)（当选择的基准点极端不平衡时）最好情况时间复杂度：O(n log n)
插入排序（Insertion Sort）:平均时间复杂度：O(n^2)最坏情况时间复杂度：O(n^2)最好情况时间复杂度：O(n)（在数组已经基本有序的情况下）
选择排序（Selection Sort）:平均时间复杂度：O(n^2)最坏情况时间复杂度：O(n^2)最好情况时间复杂度：O(n^2)（因为无论如何都需要进行相同数量的比较和交换）
归并排序（Merge Sort）:平均时间复杂度：O(n log n)最坏情况时间复杂度：O(n log n)最好情况时间复杂度：O(n log n)
冒泡排序（Bubble Sort）:平均时间复杂度：O(n^2)最坏情况时间复杂度：O(n^2)最好情况时间复杂度：O(n)（在数组已经有序的情况下）

这些复杂度分析是基于比较排序的一般情况。特定情境下，不同的算法可能表现更好或更差。例如，对于小规模数据或近乎有序的数据，插入排序可能更优。

时间复杂度排序

以下是上述时间复杂度按照增长趋势从低到高的排序：