排序算法 | Personal Blog

排序算法

发表于
Sort

冒泡排序

逐一比较相邻的两个元素，若顺序不对则颠倒

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

堆排序

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
//传入数组和目标节点下标
function MAX-HEAPIFY(A,i)//若目标节点违反最大堆，则将其下放一级
{
    var largest; //最大值下标辅助变量
    var l=2*i;   //左节点下标
    var r=2*i+1; //右节点下标
    if(l < A.length && A[l] > A[i])//左节点落在数组范围且比根节点大
    {
        largest=l;
    }
    else
    {
        largest=i;
    }
    if(l < A.length && A[l] > A[i])//右节点落在数组范围且比根节点大
    {
        largest=r;
    }
    if(largest!=i)//i节点违反最大堆
    {
        var exchange;
        exchange=A[i];
        A[i]=A[largest];
        A[largest]=exchange;//交换根节点与最大节点
        MAX-HEAPIFY(A,largest);//观察原来的根节点是否满足最大堆
    }
}

function BUILD-MAX-HEAP(A)//将数组A转换为最大堆
{
    for(int i=A.length/2;i>0;i--)//从第一个非叶子节点开始调整
    {
        MAX-HEAPIFY(A,i);
    }
}

function HEAPSORT(A)
{
    BUILD-MAX-HEAP(A);
    for(int i=A.length;i>1;i--)
    {
        var exchange;
        exchange=A[1];
        A[1]=A[i];
        A[i]=exchange;//将最大堆的根节点调换出来，为本轮最大值
        MAX-HEAPIFY(A,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
//输入数组、左边界、右边界
function QUICKSORT(A,p,r)
{
    int q;//作为中间数
    if(p < r)
    {
        q=PARTITION(A,p,r);
        QUICKSORT(A,p,q-1);//对左数组排序
        QUICKSORT(A,q+1,r);
    }
}

function PARTITION(A,p,r)
{
    var x=A[r];//将最末尾的值设为参照值
    int i = p - 1;//i始终指向左数组的右边界
    for(int j = p ;j < r-1 ; j++)
    {
        if(A[j] <= x)//此时j指向右数组中小于参照值的数
        {
            i++;
            var exchange;
            exchange = A[i];
            A[i] = A[j];
            A[j] = exchange;//将右数组的左边界与小的数交换，并扩充左数组长度
        }
    }
    var exchange = A[i+1];
    A[i+1] = A[r];
    A[r] = exchange;//将右数组的左边界与参照值交换，此时左数组小于参照值；右数组大于参照值
}

本文共1277字符