相关概念
稳定性
- 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
- 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
时间复杂度
- 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
最坏时间复杂度
- 最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。
平均时间复杂度
- 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。设每种情况的出现的概率为pi,平均时间复杂度则为sum(pi*f(n))
和平均时间复杂度
空间复杂度
- 一个程序的空间复杂度是指运行完一个程序所需内存的大小。
注意
- 基于比较的排序算法时间复杂度最快为O(nlogn)
- 部分情况下，O(n²) 也会比O(nlogn)快（数据长度较小时），一般的用于算法时，数据量都可以超过临界点，所以一般关注算法复杂度级别
- 非线性比较算法，基数排序和计数排序都是特别的桶排序，桶排序是一种空间换时间的算法
算法对照表
1.png
一、冒泡排序
算法思想：
- 对相邻的元素进行两两比较，顺序相反则进行交换，这样，每一趟会将最小或最大的元素“浮”到顶端，最终达到完全有序。
function bubbleSort(arr){
for(let i=0;i<arr.length;i++){
for(let j=1;j<arr.length-i;j++){
if(arr[j-1] > arr[j]){
let swap = arr[j-1]
arr[j-1] = arr[j]
arr[j] = swap
}
}
}
}
二、选择排序
算法思想:
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
function selectSort(arr){
for(let i=0;i<arr.length;i++){
let min = i
for(let j=i+1;j<arr.length;j++){
if(arr[min] > arr[j]){
min = j
}
}
if(i != min){
let swap = arr[i]
arr[i] = arr[min]
arr[min] = swap
}
}
}
三、插入排序
算法思想:
- 每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。
function insertSort(arr){
for(let i=1;i<arr.length;i++){
let cur = i
while(arr[cur] < arr[cur-1]){
let swap = arr[cur]
arr[cur] = arr[cur-1]
arr[cur-1] = swap
cur--
}
}
}
四、快速排序
算法思想:
- 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
function quickSort(arr){
if(arr.length <2){
return arr
}
let left = []
let right = []
let mid = arr.splice(0,1)[0]
for(let i=0;i<arr.length;i++){
if(arr[i] > mid){
right.push(arr[i])
}else{
left.push(arr[i])
}
}
return quickSort(left).concat(mid, quickSort(right))
}
五、堆排序
算法思想:
- 堆的特点就是堆顶的元素是一个
最值，大顶堆的堆顶是最大值，小顶堆则是最小值。 - 堆排序就是把堆顶的元素与最后一个元素交换，交换之后破坏了堆的特性，我们再把堆中剩余的元素再次构成一个大顶堆，然后再把堆顶元素与最后第二个元素交换….如此往复下去，等到剩余的元素只有一个的时候，此时的数组就是有序的了。
function swap(arr, i, j){
let swap = arr[i]
arr[i] = arr[j]
arr[j] = swap
}
function sort(arr){
for(let i=Math.floor(arr.length/2)-1;i>=0;i--){
heap(arr, i, arr.length)
}
for(let i=arr.length-1;i>0;i--){
swap(arr, 0, i)
heap(arr, 0, i)
}
}
function heap(arr, i, length){
let temp = arr[i]
for(let k=2*i+1;k<length;k=2*k+1){
if(k+1 < length && arr[k] < arr[k+1]){
k++
}
if(temp < arr[k]){
arr[i] = arr[k]
i = k
}else{
break;
}
arr[i] = temp
}
}
六、归并排序
算法思想:
- 将一个大的无序数组有序，我们可以把大的数组分成两个，然后对这两个数组分别进行排序，之后在把这两个数组合并成一个有序的数组。由于两个小的数组都是有序的，所以在合并的时候是很快的。
- 通过递归的方式将大的数组一直分割，直到数组的大小为 1，此时只有一个元素，那么该数组就是有序的了，之后再把两个数组大小为1的合并成一个大小为2的，再把两个大小为2的合并成4的 ….. 直到全部小的数组合并起来。
function merge(begin,end){
if(end-begin <2){
return
}
let mid = begin + end >> 1
merge(begin,mid)
merge(mid,end)
sort(begin,mid,end)
}
function sort(begin, mid, end){
let li = 0,le = mid-begin
let ri = mid,re = end
let ai = begin
let leftArray = []
for(let i=0;i<le;i++){
leftArray[i] = arr[begin++]
}
while(li < le){
if(ri < re && arr[ri] <= leftArray[li]){
arr[ai++] = arr[ri++]
}else{
arr[ai++] = leftArray[li++]
}
}
}
七、希尔排序 （缩小增量排序）
算法思想:
- 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
function shell(arr){
let step = stepArr(arr)
for(let i=0;i<step.length;i++){
insert(arr,step[i])
}
}
function stepArr(arr){
let step = arr.length
let squense = []
while((step>>=1)>0){
squense.push(step)
}
return squense
}
function swap(arr,i,j){
let swap = arr[i]
arr[i] = arr[j]
arr[j] = swap
}
function insert(arr, step){
for(let col = 0;col < step;col++){
for(let i=col+step;i<arr.length;i+=step){
let cur = i
while(cur > 0 && arr[cur] < arr[cur-step]){
swap(arr,cur,cur-step)
cur-=step
}
}
}
}
八、计数排序
算法思想:
- 就是把数组元素作为数组的下标，然后用一个临时数组统计该元素出现的次数，例如 temp[i] = m, 表示元素 i 一共出现了 m 次。最后再把临时数组统计的数据从小到大汇总起来，此时汇总起来是数据是有序的。
function countSort(arr){
let max = arr[0]
for(let i=1;i<arr.length;i++){
if(arr[i] > max){
max = arr[i]
}
}
let count = []
count.length = max+1
count.fill(0,0,max+1)
for(let i=0;i<arr.length;i++){
count[arr[i]]++
}
let newArray = []
for(let i=0;i<count.length;i++){
while(count[i] > 0){
newArray.push(i)
count[i]--
}
}
}
九、基数排序
算法思想:
- 先以个位数的大小来对数据进行排序，接着以十位数的大小来多数进行排序，接着以百位数的大小，以此类推...排到最后，就是一组有序的元素了。
function baseSort(arr){
let max = arr[0]
for(let i=1;i<arr.length;i++){
if(max < arr[i]){
max = arr[i]
}
}
let j=0
while(Math.pow(10,j) <= max){
let array = []
array.length = 10
for(let i=0;i<10;i++){
array[i] = new Array()
}
for(let i=0;i<arr.length;i++){
let digit = Math.floor(arr[i] / Math.pow(10,j)) % 10
let len = array[digit].length
array[digit][len] = arr[i]
}
arr = []
for(let i=0;i<array.length;i++){
if(array[i].length>0){
arr = arr.concat(array[i])
}
}
j++
}
}
十、桶排序
算法思想:
- 基数排序和计数排序都是特殊的桶排序，主要思想就是按照一定的规则将长度为n的数组，放进k个桶中，在分别进行排序在合并。
时间复杂度：
(n/k)lg(n/k)k+n => n(lgn-lgk)+n => n+k
网友评论