排序算法

  • 冒泡排序

avatar

1
2
3
4
5
6
//交换两个位置数据 方法 的抽取
            ArrayList.prototype.swap = function (m, n) {
                var temp = this.array[m]
                this.array[m] = this.array[n]
                this.array[n] = temp
            }

  • 冒泡排序代码实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    ArrayList.prototype.bubbleSort = function () {
                   //获取数组的长度
                   var length = this.array.length
                   //第一次：j=length-1 比较到倒数第一个位置
                   //第二次：j=length-2 比较到倒数第二个位置
                   //。。。到第0个位置
                   for (var j = length - 1; j >= 0; j--) {
                       //第一次进来   i=0 比较0和1位置的两个数据  如果0位置大于1位置数据
                       //最后一次进来 i=length-2，比较length-2和length-1的两个数据
                       for (var i = 0; i < j; i++) {
                           if (this.array[i] > this.array[i + 1]) {
                               //交换数据
                               this.swap(i, i + 1)
                           }
                       }
                   }
               }

  • 选择排序

  • avatar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//选择排序
            ArrayList.prototype.selecttionSort = function () {
                //1.获取数组长度
                var length = this.array.length

                //2.外层循环  从0位置取数据
                for (var i = 0; i < length - 1; i++) {
                    //3.内层循环 从i+1位置开始与后面的内容比较
                    var min = i
                    for (j = min + 1; j < length; j++) {
                        //4.如果i的位置的数据大于j的位置的数据，那么记录最小值让min=j
                        if (this.array[min] > this.array[j]) {
                            min = j
                        }
                        //交换数据
                        this.swap(min, i)
                    }
                }
            }

  • 插入排序

  • avatar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//插入排序
       ArrayList.prototype.insertionSort = function () {
           //获取长度
           var length = this.array.length
           //外层循环 从1位置开始，依次遍历到最后  因为0的位置默认可以看成是有序的
           for (var i = 1; i < length; i++) {
               //记录选中的元素 放到变量item中，
               var item = this.array[i]
               var j = i
               //内层循环 将j-1位置元素于item比较
               while (this.array[j - 1] > item && j > 0) {
                   //将j-1位置的元素放在j位置.
                   this.array[j] = this.array[j - 1]
                   //j位置向前移.
                   j--
               }
               // 5.将选出的j位置, 放入temp元素
               this.array[j] = item
           }
       }

高级排序

avatar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
ArrayList.prototype.shellSort = function () {
                //获取数组长度
                var length = this.array.length
                //根据数组的长度计算gap的大小
                var gap = Math.floor(length / 2)
                //gap不断变小 
                while (gap >= 1) {
                    //实现插入排序
                    for (i = gap; i < length; i++) {
                        //保存临时变量
                        var temp = this.array[i]
                        var j = i
                        //内层
                        while (this.array[j - gap] > temp && j > gap - 1) {
                            this.array[j] = this.array[j - gap]
                            j -= gap
                        }
                        //选出的位置设置为temp
                        this.array[j] = temp
                    }
                    //重新计算gap  新的间隔
                    gap = Math.floor(gap / 2)
                }
            }

快速排序

avatar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//快速排序
var quickSort = function(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  var pivotIndex = Math.floor(arr.length / 2);
  var pivot = arr.splice(pivotIndex, 1)[0];
  var left = [];
  var right = [];

  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// 快速排序
            // 1. 选择枢纽
            ArrayList.prototype.medium = function (left, right) {
                // 1. 取出中间的位置
                var center = Math.floor((left + right) / 2);

                // 2. 判断大小，并且进行交换
                if (this.array[left] > this.array[right]) {
                    this.swap(left,right);
                };
                if (this.array[left] > this.array[center]) {
                    this.swap(left,center);
                };
                if (this.array[center] > this.array[right]) {
                    this.swap(center, right);
                };
 
                // 3.将center换到right-1的位置
                this.swap(center, right - 1)

                return this.array[right - 1]
            };

            // 2. 快速排序的实现
            ArrayList.prototype.quickSort = function () {
                this.quick(0, this.array.length - 1);

            };

            ArrayList.prototype.quick = function (left, right) {
                // 1. 结束条件
                if (left >= right) {
                    return
                };

                // 2. 获取枢纽
                var pivot = this.medium(left, right);

                // 3. 定义变量，用于当前找到的位置
                var i = left;
                var j = right - 1;

                // 4. 开始进行交换
                while (i < j) {
                    while (this.array[++i] < pivot) { };
                    while (this.array[--j] > pivot) { };
                    if (i < j) {
                        this.swap(i, j);
                    } else {
                        break;
                    };

                }
                // 5. 将枢纽放置在正确的位置，i的位置
                this.swap(i, right - 1);

                // 6. 分而治之
                this.quick(left, i - 1);
                this.quick(i + 1, right);
            };

        }

归并排序

归并排序主要思想是分而治之 通过将问题分解成小问题

归并排序的步骤大概是:

  1. 将给定的列表分为两半（如果列表中的元素数为奇数，则使其大致相等）。
  2. 以相同的方式继续划分子数组，直到只剩下单个元素数组。
  3. 从单个元素数组开始，合并子数组，以便对每个合并的子数组进行排序。
  4. 重复第 3 步单元，直到最后得到一个排好序的数组。

code

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
/* 
merge函数 是将两个排好序的子数组(left,right)合并获得一个排好序的大数组  
*/


function merge (left,right){
    let arr = []
    while(left.length && right.length){
        //默认left right 数组已经排好序 所以直接比较最小元素
        if(left[0]<right[0]){
            arr.push(left.shift())
        } else {
            arr.push(right.shift())
        }
    }
    //连接剩余元素
    return [...arr,...left,...right]
}

function mergeSort(array) {
    const half = array.length / 2
    
    if(array.length < 2){
      return array 
    }
    
    const left = array.splice(0, half)
    //先递 再归   当递到只剩一个元素 那么就变成有序的  再不断merge 最后就有序了
    return merge(mergeSort(left),mergeSort(array))
  }

  array = [4,5,6,3,2,1,0,11]
  console.log(mergeSort(array))

排序算法稳定性