排序
中位数
function middle(arr){
let len = arr.length
return (arr[(len - 1) >> 1] + arr[len >> 1]) / 2
}
range
[min, max]
function random(min,max){
min = Math.ceil(min)
max = Math.floor(max)
// [min,max) = max - min
return Math.floor(Math.random() * (max - min + 1) + min)
}
冒泡排序
简单排序算法。重复访问要排序的数组，每次比较两个元素，如果它们的顺序不对就进行交换。直到排序完成
- 时间复杂度
O(n^2) - 空间复杂度
O(n)
一般排序
function bubbleSort(arr: number[]) : number[]{
const len = arr.length;
for(let i=0;i<len;i++){
for(let j=0;j<len-i-1;j++){
if(arr[j] > arr[j+1]){
let temp = arr[j+1]
arr[j+1] = arr[j]
arr[j] = temp
}
}
}
return arr
}
改进后
function bubbleSortChange(arr: number[]): number[]{
let i = arr.length - 1;
while(i>0) {
let pos = 0;
for(let j = 0;j<i;j++){
if(arr[j]>arr[j+1]){
pos = j;
let temp = arr[j+1]
arr[j+1] = arr[j]
arr[j] = temp
}
}
i = pos
}
return arr
}
选择排序
在未排序序列中找到最小 (大) 元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小 (大) 元素，然后放到已排序序列的末尾，以此类推。
- 时间复杂度
O(n^2) - 空间复杂度
O(n^2)
function selectSort(arr: number[]) : number[]{
const 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
}
插入排序
构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。类似扑克牌
- 时间复杂度
O(n^2) - 空间复杂度
O(n^2)
function insertSort(arr: number[]): number[]{
let len = arr.length
for(let i=1;i<len;i++){
let key = arr[i], j = i-1
while(j>=0 && arr[j]>key){
arr[j+1] = arr[j]
j--
}
arr[j+1] = key
}
return arr
}
希尔排序
是简单插入排序的改进版；它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。核心在于间隔序列的设定
O(nlog n)
function shellSort(arr: number[]): number[]{
let len = arr.length, temp, gap = 1;
// define distance
while(gap < len/5) {
gap = gap*5 + 1
}
for(gap;gap>0;gap = Math.floor(gap/5)){
for(let i=gap;i<len;i++){
temp = arr[i]
let j
for(j = i-gap;j>=0&&arr[j]> temp;j-=gap){
arr[j+gap] = arr[j]
}
arr[j+gap] = temp
}
}
return arr
}
归并排序
采用分治法 (Divide and Conquer) 的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序
时间复杂度：
O(nlog n)把长度为 n 的输入序列分成两个长度为 n/2 的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列
function mergeSort(arr: number[]) : number[]{
const 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: number[], right: number[]){
let res: number[] = []
while(left.length && right.length){
if(left[0] <= right[0]){
res.push(left.shift() as number)
} else{
res.push(right.shift() as number)
}
}
while(left.length) res.push(left.shift() as number)
while(right.length) res.push(right.shift() as number)
return res
}
快速排序
使用分治法来把一个串 (list) 分为两个子串 (sub-lists)
从数列中挑出一个元素，称为 “基准” (pivot)；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面 (相同的数可以到任一边)。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区 (partition) 操作；
递归地 (recursive) 把小于基准值元素的子数列和大于基准值元素的子数列排序。
O(nlogn)
function quickSort(arr: number[]): number[]{
if(arr.length <= 1) return arr
let left = [], right = [], index = Math.floor(arr.length/2), middle = arr.splice(index,1)[0]
for(let i=0;i<arr.length;i++){
if(arr[i] < middle){
left.push(arr[i])
} else {
right.push(arr[i])
}
}
return quickSort(left).concat([middle], quickSort(right))
}
堆排序
堆排序 (Heapsort) 是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于 (或者大于) 它的父节点。
O(nlogn)
//