一个苹果

一，冒泡排序 1, 相邻之间相比较，左边比右边大的话，交换位置。 2，第一轮下来,已经把最大的值选出来，并排在最后位，这样剩下需排序的的数组减1，依次类推。 function sort(arr) { for(let i = 0, l = arr.length - 1; i < l; i++) { for(let j = 0; j < arr.length - i - 1; j++) { if (arr[j] > arr[j+1]) { [arr[j], arr[j+1]] = [arr[j+1], arr[j]] } } } } let list = [5,4,8,2,1,9,7,3,6] sort(list) console.log(list) 二，快速排序 1，找一个基准点(一般是中间数) 2，和基准值比较，比基准值小放leftList，比基准值大放rightList 3，递归执行上述操作，直到arr.length <= 1 function sort(arr) { if (arr.length <= 1) return arr let midIndex = Math.floor(arr.length/2) let midVal = arr[midIndex] // 基准值，一般取中间数 arr.splice(midIndex, 1) let leftList = [] let rightList = [] for(let i = 0, l = arr.length; i < l; i++) { if (arr[i] < midVal) { leftList.push(arr[i]) } else { rightList.push(arr[i]) } } return sort(leftList).concat(midVal, sort(rightList)) } let list = [5,4,8,2,1,9,7,3,6] let newList = sort(list) console.log(newList) 三，选择排序 1，找到数组中最小值的索引 2，把最小值排到第一位来。以此类推 function sort(arr) { if (arr.length <= 1) return arr let minIndex for(let i = 0, l = arr.length - 1; i < l; i++) { minIndex = i for(let j = i + 1; j < arr.length; j++) { if (arr[j] < arr[minIndex]) { minIndex = j } } if (i !== minIndex) [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]] } } let list = [5,4,8,2,1,9,7,3,6] sort(list) console.log(list) 四，插入排序 类似我们打扑克牌，牌从左向右的排序，抽出一张牌插到合适的位置放。 1，抽出位置1的牌，与位置0比较，当位置0的牌比1大时, 先把0的值填入位置1。剩下0位置插入。 2，抽出位置2的牌，与前面位置1比较，当位置1比2大时，先把1的值填入2位置，位置1空出。往下一层比较，找到合适的位置。依次类推。 function sort(arr) { let perIndex, current for(let i = 1, l = arr.length; i < l; i++) { perIndex = i - 1 current = arr[i] // 抽出的位置值，当前位置为i === perIndex+1 while(perIndex >= 0 && arr[perIndex] > current){ arr[perIndex + 1] = arr[perIndex] // 先把位置1的值填入2位置，空出位置1 perIndex-- // 往下一层，此时perIndex位置为0，假设arr[0] < current时，循环结束，所以位置1(perIndex+1)的值为current } arr[perIndex+1] = current } } let list = [5, 4, 8, 2, 1, 9, 7, 3, 6] sort(list) console.log(list) 五，希尔排序 1，按一定的间隔对数组进行分组，一般以数组长度一半 gap = length / 2 (ps:也可以是3,4,无强性要求) (假如：数组长度为10的话gap = 10 / 2 = 5，也就是，位置0和5为一组，位置1和6位一组...,组里的值进行插入排序) 2，以gap的一半进行缩小 gap = gap / 2 （此时：gap = Math.floor(5 / 2) = 2 向下取整，也就是，位置0和位置2为一组，位置1和3为一组..,组里的值进行插入排序） 3，当gap === 1时，此时所有元素为一组，此时运行的就是我们一般的插入排序了。 这样处理的好处是：希尔排序的优化使得原本 O(n^2) 的时间复杂度一下降为 O(nlogn) function sort(arr) { for(let gap = Math.floor(arr.length / 2); gap > 0; gap = Math.floor(gap / 2)) { // 循环组递减 // 内循环与插入排序写法一致,只是每次移动的步长为gap for(let i = gap; i < arr.length; i++) { let temp = arr[i] let j = i - gap; // 例如 gap = 4, 则j = 0, 0 和4位置之间的比较 for(j; j >= 0 && temp < arr[j]; j -= gap) { arr[j + gap] = arr[j] } arr[j + gap] = temp } } } let list = [5, 4, 8, 2, 1, 9, 7, 3, 6] sort(list) console.log(list) 六，归并排序 采用分治思想 1，先把数组从中间分开， [5, 4, 8, 2, 1, 9, 7, 3, 6, 0] [5, 4, 8, 2, 1] [9, 7, 3, 6, 0] [5, 4, 8] [2, 1] [9, 7, 3] [6, 0] [5, 4] [8] [2] [1] [9, 7] [3] [6] [0] [5] [4] [9] [7] 2，分别比较合并 [4, 5] [4, 5, 8] [1, 2] [1, 2, 4, 5, 8] ... function sort(arr) { if(arr.length < 2) return arr let mid = Math.floor(arr.length / 2), left = arr.slice(0, mid), right = arr.slice(mid) return merge(sort(left), sort(right)) } function merge(left, right) { const result = [] while(left.length && right.length) { if(left[0] <= right[0]){ result.push(left.shift()) // 相当于result.push(left[0]);left.shift() } else { result.push(right.shift()) } } while(left.length) result.push(left.shift()) while(right.length) result.push(right.shift()) return result } let list = [5, 4, 8, 2, 1, 9, 7, 3, 6, 0] console.log(sort(list)) 七，堆排序 堆排序.gif 1，构建堆，堆顶是最大的元素（子结点的键值或索引总是小于（或者大于）它的父节点） 2，把最大的元素交换到堆顶，然后把堆顶跟交换到数组后面，数组减1，依次重复。 // 构建最大堆 function buildHeap(arr) { for(let i = Math.floor(arr.length / 2); i >= 0; i--) { adjustHeap(arr, i, arr.length) } } function adjustHeap(arr, i, len) { let left = 2 * i + 1, right = 2 * i + 2, largest = i // 最大值位置 // 3个节点的交换，找出最大做顶节点 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) adjustHeap(arr, largest, len) } } // 交换位置 function swap(arr, i, j) { [arr[i], arr[j]] = [arr[j], arr[i]] } // 取值排序 function sort(arr) { buildHeap(arr) // 构建堆 for(let i = arr.length - 1; i > 0; i--) { swap(arr, 0, i) // 堆顶0肯定是最大的元素，先排到后面，然后数组长减1 adjustHeap(arr, 0, i) // 数组长减1后，调整堆 } } let list = [5, 4, 8, 2, 1, 9, 7, 3, 6, 0] sort(list) console.log(list) 八，桶排序 采用分治思想(ps:把数组分成若干小份，排好每小份，在拼接起来) 1, 定义一个桶的大小（一个桶能装下几个值） 2，根据数组的长度，计算需要几个桶，每个桶都是小的数组，组成二维数组 3，往桶里放数据 4，每个桶的数组使用插入排序 5，把每个桶的数据拼接起来 /* arr = 待排序数组 bucketSize = 桶的大小，bucketSize = 5 一个桶装5个数 */ function sort(arr, bucketSize = 5) { if (arr.length < 2) return arr const buckets = createBucket(arr, bucketSize) return sortBuckets(buckets) } // 划分桶存二维数组 function createBucket(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] } if(arr[i] > maxValue) { maxValue = arr[i] } } // 桶个数 let bucketCount = Math.ceil((maxValue - minValue)/bucketSize) // 创建二维数组来存储 const buckets = [] for(let i = 0; i <= bucketCount; i++) { buckets[i] = [] } // 把数据放进桶 for(let i = 0, l = arr.length; i < l; i++) { let buckerIndex = Math.floor((arr[i] - minValue) / bucketSize) buckets[buckerIndex].push(arr[i]) } return buckets } function sortBuckets(buckets) { let sortArray = [] for(let i = 0, l = buckets.length; i < l; i++) { if (buckets[i] != null) { let sorted = inserSort(buckets[i]) sortArray = [...sortArray, ...sorted] } } return sortArray } // 插入排序 function inserSort(arr) { if (arr.length < 2) return arr for(let i = 0, l = arr.length; i < l; i++) { let key = arr[i] let j = i - 1 while (j >=0&&arr[j] > key) { arr[j + 1] = arr[j] j-- } arr[j + 1] = key } return arr } let list = [5,4,8,2,1,9,7,3,6] console.log(sort(list)) 九，计数排序 1，找出最大和最小元素。 2，统计每个元素出现的次数，以元素的值为索引，次数为value。 3,对所有计数开始累加，从min开始,每一项和前一项相加（加起来最后一个的值是数组的长度,用于下一步值的填充） 4，反向填充目标数组，将每个元素i放在新数组的第C[i]项，每放一个元素，计数-1 function sort(arr) { let len = arr.length, bucket = [], min = arr[0], max = arr[0], newArr = [] for(let i = 0; i < len; i++) { min = min <= arr[i] ? min : arr[i] // 找出最小值 max = max >= arr[i] ? max : arr[i] // 找出最大值 bucket[arr[i]] = bucket[arr[i]] ? bucket[arr[i]]+1 : 1 // 收集值为索引 } // 对所有计数累加 for(let j = min; j < max; j++) { bucket[j + 1] = (bucket[j + 1] || 0) + (bucket[j] || 0) } for(let k = len - 1; k >= 0; k--) { newArr[bucket[arr[k]] - 1] = arr[k] bucket[arr[k]]-- } // 也可以这样的填充 // for(let k = 0; k <= max; k++) { // while (bucket[k]-- > 0) { // newArr.push(k) // } // } return newArr } let list = [2, 2, 3, 8, 7, 1, 2, 7, 3, 9, 8, 1, 4, 2, 4, 6, 9, 2] console.log(sort(list)) 十，基数排序 适用，例如当你的数很大，如手机号码，的排序 1， 先按排序个位数，以各位的值为key, 这个的值为value, 进行按各位的排序 2，排好个位数后，用排好的数组在按十位数排，以十位数的值为key, 这个值为value, 进行按十位的排序，依次类推 /* arr = 待排序数组 max = 最大位数 */ function sort(arr, max) { const buckets = [] let unit = 10 let base = 1 for(let i = 0; i < max; i++, base *= 10, unit *= 10 ){ //先排好个位，在排十位... for(let j = 0; j < arr.length; j++) { let index = Math.floor((arr[j]%unit) / base) // 过滤出个位数，十位数，... if (buckets[index] == null) { buckets[index] = [] } buckets[index].push(arr[j]) } let pos = 0 let value for(let j = 0, l = buckets.length; j < l; j++) { if (buckets[j] != null) { while ((value = buckets[j].shift()) != null) { arr[pos++] = value } } } } } let list = [15,24,38,16,22,15,49,71,43] sort(list, 2) console.log(list)