经典排序算法

经典排序算法

0. 放在前面

image-20210414224115837

img

==1. 冒泡排序（重点）==

比较相邻的元素，前面>后面，则调换位置

所有元素都进行这一操作

需要用到两个for循环

  • 时间复杂度：
    • 最好情况：O(n)
    • 平均情况：O(n^2)
    • 最坏情况：O(n^2)

  • 稳定性：稳定

  • 额外的空间：O(1)

    原地排序，不需要额外空间

1. 一般版

1
2
3
4
5
6
7
8
9
10
11
12
13
function bubbleSort1(arr) {
    var len = arr.length;
    for(var i=0;i<arr.length;i++){
        for(var j=0;j<len-1-i;j++){
            if(arr[j]>arr[j+1]){      //相邻元素两两对比
                var temp = arr[j+1];  //元素交换
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr
}

2. 改进版

设置pos，记录每轮排序中最后一次进行交换的位置。下一轮排序只扫描到pos位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function bubbleSort2(arr) {
    var i = arr.length - 1;
    while(i>0) {
        var pos = 0;  //每一轮都初始化pos值
        for(var j=0;j<i;j++){
            if(arr[j]>arr[j+1]){      //相邻元素两两对比
                pos = j;			 //记录交换的位置
                var temp = arr[j+1];  //元素交换
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
        i = pos;  //为下一趟做准备
    }
    return arr
}

3. 双向冒泡

正向和反向两遍冒泡

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function bubbleSort3(arr) {
    var low = 0;
    var high = arr.length - 1;
    while(low<high) {
        for(var j=low;j<high;++j){  //正向冒泡，找到最大值
            if(arr[j]>arr[j+1]){ 
                var temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
        --high;  //为下面的循环做准备
        for(var j=high;j<low;--j){  //反向冒泡，找到最小值
            if(arr[j]<arr[j+1]){ 
                var temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr
}

2. 选择排序

在序列中找到最小/最大值，放到序列起始位置

对所有未排序的元素进行相同的操作，每轮只找最小/最大值

选择排序 vs 冒泡排序：

  • 选择排序是记录这一轮遍历数组里的最小/最大值，遍历完成后将这个最值放在起始位置，只需要一次交换
  • 冒泡排序是两两之间进行交换，需要交换很多次

选择px

  • 时间复杂度：

    • 最好情况：O(n^2)
    • 平均情况：O(n^2)
    • 最坏情况：O(n^2)

  • 稳定性：不稳定

    大小相同的两个元素，相对前后位置对换了

    比如序列：{ 5, 8, 5, 2, 9 }，一次选择的最小元素是2，然后把2和第一个5进行交换，从而改变了两个元素5的相对次序。

  • 额外的空间：O(1)

1. 简单选择排序（基本）

1-1 取下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function selectionSort(arr) {
  let len = arr.length;
  for (let i=0;i<len-1;i++) {
    for (let j=i;j<len;j++) {
      let min = i;
      //从剩下项中去寻找最小项，遇到比假设项小的就把其当作最小项继续寻找，直到找完剩下的所有项
      if (arr[min] > arr[j]) { // 寻找最小数下标
        min = j;  //取出索引，下面进行判断，不相等就开始交换
      }
      if (min !== i) {
        let temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
      }
    }
  }
  return arr;
}

1-2 取值

和上面的方法类似，只不过这里是直接拿数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function selectionSort(arr) {
 for (let i = 0; i < arr.length - 1; ++i) {
    let min = arr[i];
    for (let j = i + 1; j < arr.length; ++j) {
      if (min > arr[j]) {
        let temp = min;
        min = arr[j];
        arr[j] = temp;
      }
    }
    arr[i] = min;
  }
  return arr;
}

==2. 堆排序（重点）==

  1. 堆概念

大顶堆：每个节点的值都大于或者等于它的左右子节点的值。

小顶堆：每个节点的值都小于或者等于它的左右子节点的值。

image-20210418171723516

  1. 具体操作

img

  1. 最大堆调整：将堆的末端子节点作调整，使得子节点永远小于父节点

  2. 创建最大堆：将堆中的所有数据重新排序

  3. 堆排序：移除位在第一个数据的根节点，并做最大堆调整的递归运算

  • 时间复杂度：
    • 最好情况：O(nlgn)
    • 平均情况：O(nlgn)
    • 最坏情况：O(nlgn)

  • 稳定性：不稳定

  • 额外的空间：O(1)

    每次只对一个元素操作，就地排序

    ==(↓ 下面代码是复制粘贴过来的，先放着吧)==

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
function buildMaxHeap(arr) {   //建堆
    var len = arr.length;
    // [n/2-1]表示的是最后一个有子节点 (本来是n/2（堆从1数起），但是这里arr索引是从0开始，所以-1)
    for (var i = Math.floor(len/2)-1; i>=0; i--) {
        maxHeapify(arr, i);
    }
    //对每一个节点（非叶节点），做堆调整
}
function maxHeapify(arr, i) {     //堆调整
    var left = 2*i+1,  
        right = 2*i+2, 
        largest = i;   //i为该子树的根节点
    if (left < len && arr[left] > arr[largest]) {  
        largest = left;
    }
    if (right < len && arr[right] > arr[largest]) {
        largest = right;
    }
    if (largest !== i) {  //即上面的if中有一个生效了
        swap(arr, i, largest);  //交换最大的为父节点
        maxHeapify(arr, largest);  //交换后，原值arr[i]（往下降了）（索引保存为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--;
        maxHeapify(arr, 0);
    }
    return arr;
}

3. 插入排序

从第二位开始抽

抽出一个数，往前一位从后往前以此进行比对，找到比这个数小的数时则放其后（其实不就是打扑克排牌时的做法嘛）

1）从第一个元素开始，该元素可以被认为已经被排序
2）取出下一个元素，在已经排好序的序列中从后往前扫描
3）直到找到小于或者等于该元素的位置
4）将该位置后面的所有已排序的元素从后往前依次移一位
5)将该元素插入到该位置
6)重复步骤2~5

插入排序

  • 时间复杂度：

    • 最好情况：O(n) 输入的数组是升序排序
    • 平均情况：O(n^2)
    • 最坏情况：O(n^2) 输入的数组是降序排序

  • 稳定性：稳定

    相等元素的相对次序没有改变

  • 额外的空间：O(1)

1. 直接插入排序（基本）

1
2
3
4
5
6
7
8
9
10
11
12
function InsertionSort(arr) {
    for(let i=1;i<arr.length;i++){
        let temp = arr[i];  //抽出一个数
        let j = i - 1;    //往前一位进行比对
        while(j>=0 && arr[j]>arr[i]){
            arr[j+1] = arr[j];  //如果前一位的数大于取出来的数，则arr[j]外后移一位
            j--；   //继续往前移动
        }   //当j<0时，循环结束
        a[j+1] = b; //此时把取出的元素插进去
    }
    return arr
}

2. 二分插入排序

使用二分查找法，实际上就是在上面的方法中更改了查找位置

在已排序序列中二分查找到第一个比它大的数的位置

时间复杂度：

  • 最好情况：O(nlogn)
  • 平均情况：O(n^2)
  • 最坏情况：O(n^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function binaryInsertSort(arr) {
    for (var i=1;i<arr.length; i++) {
        var temp=arr[i],left=0,right=i-1;
        while(left<=right){       //在已排序的元素中二分查找第一个比它大的值
          var mid= parseInt((left+right)/2); //二分查找的中间值
          if(temp<arr[mid]){ //当前值比中间值小,则在左边的子数组中继续寻找   
            right = mid-1;
          }else{
            left=mid+1;//当前值比中间值大,在右边的子数组继续寻找
          }
        }              
        for(var j=i-1;j>=left;j--){
          arr[j+1]=arr[j];
        }
        arr[left]=temp;
      }
    return arr;
}

3. 希尔排序（了解）

缩小增量排序

尽可能让小的值往前靠，让大的值靠后（避免大幅度的后移）

  1. 设置一个增量n，这个n为数组长度的1/2
  2. 相隔n个的元素视为同一组，在组内进行比较排序
  3. 再将n*1/2，重复2步骤，直到增量n为1（此时所有元素都是同一个组了）

在这里插入图片描述

（↓ 下面的代码是复制博客里的）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function shellSort(arr) {
    let interval = Math.floor(arr.length / 2);
    // 不断地缩小间隔的大小，进行分组插入排序
    while(interval >= 1) {
        // 从 arr[interval] 开始往后遍历，将遍历到的数据与其小组进行插入排序
        for(let i = interval; i < length; i++) {
            let temp = arr[i];
            let j = i;
            while(arr[j - interval] > temp && j - interval >= 0) {
                arr[j] = arr[j - interval];
                j -= interval ;
            }
            arr[j] = temp;       
        }
        // 缩小间隔
        interval = Math.floor(interval / 2);
    }
    return arr;
}

==4. 快速排序（重点）==

将数据分成两部分

一边的数据全都小于基准数，一边的数据全都大于基准数

按照这种方法再分别对这两部分的数据进行快速排序

快速排序

第一轮之后的效果：

image-20210418203839596

  • 时间复杂度：

    • 最好情况：O(nlogn)
    • 平均情况：O(nlogn)
    • 最坏情况：O(n^2)

  • 稳定性：不稳定

  • 额外的空间：O(logn)~O(n)

    递归造成的栈空间的使用(用来保存left和right等局部变量)，取决于递归树的深度

1. 有递归版本

递归是什么？ ==> 套娃

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function quick(arr, left = 0, right = arr.length - 1) { 
	if (left >= right) return arr;  //arr长度为0或1的时候
	var i = left, j = right, basic =i;
	while(i < j) {
		while(arr[j] >= arr[basic] && j > basic) j--;//如果j指针指向的值大于或等于基准，则j指针向左移动
		while(arr[i] <= arr[basic] && i < j) i++;  //同样的，如果i指针指向的值小于或等于基准，则i指针向右移动
		var temp = arr[basic];  //此时ij相遇，与基准数交换
		arr[basic] = arr[j];
		arr[j] = temp;
		basic = i
	}
	quick(arr, left, basic - 1); //对左边进行
	quick(arr, basic + 1, right); //对右边进行
    return arr;
}

由于使用了递归，所以要有条件，不然会无限套娃，然后就崩了 =。=

2. 无递归版本（栈）

先来了解一下栈：大概可以比喻成 ==> 把东西往容器里放，拿出来的时候只能是最后放的那个

  • 栈声明一些方法。
    • push(element(s))： 添加一个（或几个）新元素到栈顶
    • pop()：移除栈顶的元素，同时返回被移除的元素
    • peek()：返回栈顶的元素，不对栈做任何修改（该方法不会移除栈顶的元素，仅仅返回它）
    • isEmpty()：如果栈里没有任何元素就返回true，否则返回false
    • clear()：移除栈里的所有元素
    • size()：返回栈里的元素个数。该方法和数组的length 属性很类似

模拟栈，将待排序数组的[left,right]保存到数组中，循环取出进行快排

(↓贴个代码，看懂了，不会写)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function quickSort(arr) {
    let stack = [];  //栈
    stack.push([0, arr.length - 1]);  //push()添加元素到栈顶
    while (stack.length) {
      let list = stack.pop();  //pop()移除栈顶元素，同时返回被移除的元素
      let i = left = list[0];
      let j = right = list[1];
      let mid = arr[(i + j) >> 1];  //右移
      do {
        while (arr[i] < mid) ++i;
        while (arr[j] > mid) --j;
        if (i <= j) {
          let temp = arr[i];  //交换
          arr[i] = arr[j];
          arr[j] = temp;
          ++i;
          --j;
        }
      } while (i <= j);
      if (i < right) stack.push([i, right]);
      if (left < j) stack.push([left, j]);
    }
    return arr;
}

==5. 归并排序（重点）==

分而治之

将数组分组至两两比较，最后直到所有元素都被分到一组里

img

  • 时间复杂度：
    • 最好情况：O(nlogn)
    • 平均情况：O(nlogn)
    • 最坏情况：O(nlogn)
  • 稳定性：稳定
  • 额外的空间：O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
mergeSort = (arr) => {
	if(arr.length<=1){
		return arr;
	}else{
		var mid=Math.floor(arr.length/2);  //取中间值（向下取整）
		var left=arr.slice(0,mid);  //分成左右两部分
		var right=arr.slice(mid);
		left = mergeSort(left);
		right = mergeSort(right);
		var temp=[];  //一个空数组
		while(left.length && right.length){  //左右两部分长度均存在
			if(left[0] < right[0]){  //比较两个数的大小，先把小的放进去
				temp.push(left.shift()); //shift()方法用于把数组的第一个元素从其中删除，并返回第一个元素的值
			}else{
				temp.push(right.shift());
			}
		}
		return  temp.concat(left,right);  //用递归继续进行分割，用concat进行合并
	}
}

6. 基数排序（了解）

从个位数开始，依次放入0~9的桶中，再依次拿出来排序；十位、千位……重复上述操作，一直排到最高位为止

基数排序

  • 时间复杂度：
    • 最好情况：O(n+k)
    • 平均情况：O(n+k)
    • 最坏情况：O(n+k)
  • 稳定性：稳定
  • 额外的空间：O(n+k)

（贴一个大佬的代码，写法有点帅）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
radixSort = (arr) => {
    if (arr.length < 2) {
        return arr;
    }
    let maxDigit = String(parseInt(Math.max(...arr))).length // 取最大位数
    let mod = 10;
    let dev = 1;
    let counter = [];
    for (let i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for(let j = 0; j < arr.length; j++) {
            let bucket = parseInt((arr[j] % mod) / dev);  // 123%10/1=3；123%100/10=2；==> 取位
            counter[bucket] = counter[bucket] == null ? [] : counter[bucket];
            counter[bucket].push(arr[j]);
        }
        let pos = 0;
        for(let j = 0; j < counter.length; j++) {
            let value = null;
            if(counter[j]!=null) {
                while ((value = counter[j].shift()) != null) {
                    arr[pos++] = value;
                }
            }
        }
    }
    return arr;
}