Algorithm Sorting

A few algorithm about array sorting

binary-tree sorting | stack sorting

Posted by Maizi on 2016-09-24 with time read
排序算法合集之二叉树

二叉树排序算法描述:


算法分析:

假若排成升序,用顺序表的数据结构来解决该问题,希尔排序是对直接插入排序的改进算法,该算法的时间复杂度O(n)=nlog₂n(最好时复杂度)

①先找到一种算法对整个数组进行’分列’,该博文中使用的是用数组长度加一依次除以 2 3 4…得到的结果最为每’列’中元素相邻位置在原一维数组中的 增量

②将 ① 中的每一列依次进行直接插入排序,直至最后 增量 为1时再对整个数组进行一次直接插入排序

希尔排序算法优劣:

优势 : 算法的空间复杂度较小
劣势 : 算法略复杂,且时间复杂度还是不小,但相对于n²还是小了不少.

贴上代码:

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
63
64
65
66
67
68
69
70
71
72
73
74
#include <stdio.h>
/**
 * 直接插入排序
 * @param arr 待排序的数组
 * @param col 当前对第几'列'进行操作
 * @param delta 当前每列中相邻元素在待排序一维数组中的增量
 * @param len 该'列'元素的个数
 */
void inserting_sort(int *arr, int const col, int const delta, int const len) {
    int i, j;
    for (i = 1; i < len; ++i) {
        int low = 0, high = i - 1;
        while (low < high) {//二分搜索定位
            int pivot = (low + high) >> 1;
            if (*(arr + col + pivot * delta) > *(arr + col + i * delta))
                high = pivot - 1;
            else
                low = pivot + 1;
        }
        if (low == high)//特殊情况处理
            if (*(arr + col + low * delta) < *(arr + col + i * delta))
                low++;
        for (j = i; j > low; --j) {//元素交换
            *(arr + col + j * delta) += *(arr + col + (j - 1) * delta);
            *(arr + col + (j - 1) * delta) = *(arr + col + j * delta) - *(arr + col + (j - 1) * delta);
            *(arr + col + j * delta) = *(arr + col + j * delta) - *(arr + col + (j - 1) * delta);
        }
    }
}
/**
 * 希尔排序
 * @param arr 待排序的数组
 * @param len 数组的长度
 */
void shellSort(int *const arr, size_t const len) {
    int row = 2;
    int delta = (len + 1) / row;   //首次将数组分成两半
    do {
        int residue = len % delta;  //数组长度模增量的余数
        int base_col_len = len / delta;  //列数组长度的基数
        int i;
        for (i = 0; i < delta; i++) {
            int j;
            if (residue && i < residue)  //若余数大于０且ｉ的值小于余数，那么当前列数组的长度为基数加一
                j = 1;
            else  //否则，当前数组的长度就等于基长度
                j = 0;
            inserting_sort(arr, i, delta, base_col_len + j);
        }
        delta = (len + 1) / row++;
    } while (delta != 2 && delta > 2);
    inserting_sort(arr, 0, 1, len);
}
/**
 * 打印数组
 * @param arr 数组的指针
 * @param len 数组的长度
 */
void print(int const *const arr, size_t const len) {
    int i;
    printf("the sequence of arr which have been sorted:\n");
    for (i = 0; i < len; ++i)
        printf("%d ", *(arr + i));
}
int main(void) {
    int arr[] = {12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    int len = sizeof(arr) / sizeof(int);
    shellSort(arr, len);
    print(arr, len);
    return 0;
}

附上测试结果:

1
2
the sequence of arr which have been sorted:
1 2 3 4 5 6 7 8 9 10 11 12
排序算法合集之快速

快速排序算法描述:


算法分析:

假若排成升序,用顺序表的数据结构来解决该问题,该算法的时间复杂度O(n)=nlog₂n.

①先定义两个整型变量low和high用于记录当前的最低和最高位置,依次初始化为0和数组的长度减一(len-1)

②从数组的最高位开始,依次向前寻找第一个比最低位元素小的元素且每向前一次high–,还要保证low
③递归调用 ② 过程直至数组不可再分为止就说明排完了

快速排序算法优劣:

优势 : 算法的时间复杂度较小,效率很高
劣势 : 该算法过度使用操作系统函数调用时的栈空间,导致空间复杂度较大,在jvm这种平台上还可能导致栈溢出.

贴上代码:

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
#include <stdio.h>
/**
 * 将当前"数组"一分为二
 * @param arr 待操作的数组
 * @param low 当前"数组"的首元素在原数组中的位置
 * @param high 当前"数组"的尾元素在原数组中的位置
 * @return 关键元素的位置
 */
int partition(int *const arr, long low, long high) {
    int pivotKey = *(arr + low);
    while (low < high) {
        while (low < high && *(arr + high) >= pivotKey)
            --high;
        *(arr + low) = *(arr + high);
        while (low < high && *(arr + low) <= pivotKey)
            ++low;
        *(arr + high) = *(arr + low);
    }
    *(arr + low) = pivotKey;
    return low;
}
/**
 * 快速排序
 * @param arr 待操作的数组
 * @param low 当前"数组"的首元素在原数组中的位置
 * @param high 当前"数组"的尾元素在原数组中的位置
 */
void fastSort(int *const arr, int const low, int const high) {
    if (low < high) {
        int pivotLoc = partition(arr, low, high);
        fastSort(arr, low, pivotLoc - 1);
        fastSort(arr, pivotLoc + 1, high);
    }
}
/**
 * 打印数组
 * @param arr 数组的指针
 * @param len 数组的长度
 */
void print(int const *const arr, size_t const len) {
    int i;
    printf("the sequence of arr which have been sorted:\n");
    for (i = 0; i < len; ++i)
        printf("%d ", *(arr + i));
}
int main(void) {
    int arr[] = {8, 4, 12, 2, 6, 10, 14, 1, 3, 15, 7, 11};
    long len = sizeof(arr) / sizeof(int);
    fastSort(arr, 0, len - 1);
    print(arr, len);
    return 0;
}

附上测试结果:

1
2
the sequence of arr which have been sorted:
1 2 3 4 6 7 8 10 11 12 14 15
排序算法合集之归并

归并排序算法描述:


算法分析:

假若排成升序,用顺序表的数据结构来解决这些问题,该算法的时间复杂度O(n)=nlog₂n.

①将数组按2º(0,1,2…)为步进均分成成多个”数组”,然后从数组的头部将相邻的数组合并且将合并后的数组进行排序.

②重复 ① 中的过程直至步进大于或等于数组长度的一半且小于数组长度时,就说明是最后一次合并了

归并排序算法优劣:

优势 : 算法原理较希尔和快速更易懂,由于合并的相邻的两个”数组”内部的元素各自都是有序的,在合并时就可以批量移动,且还可以利用二分搜索进行定位相关的操作.
劣势 : 该算法过度使用操作系统函数调用时的栈空间,导致空间复杂度较大,在jvm这种平台上还可能导致栈溢出.

贴上代码:

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <stdio.h>
/**
 * 将指定的一个或多个元素插入到指定的位置
 * @param arr 待操作的数组
 * @param si1 插入点的位置
 * @param si2 被插入的首个元素在原数组中的位置
 * @param ei2 被插入的最后一个元素在原数组中的位置
 */
void insertInto(int *arr, int si1, int si2, int ei2) {
    int len = ei2 - si2 + 1, i, j, length = si2 - si1, tmp;
    for (i = 0; i < len; ++i) {
        tmp = *(arr + si2 + i);
        for (j = length - 1; j >= 0; --j)
            *(arr + si1 + j + i + 1) = *(arr + si1 + j + i);
        *(arr + si1 + i) = tmp;
    }
}
/**
 * 合并两个"数组"
 * @param arr 待操作的数组的指针
 * @param si1 第一个"数组"的首元素在原数组中的位置
 * @param ei1 第一个"数组"的尾元素在原数组中的位置
 * @param si2 第二个"数组"的首元素在原数组中的位置
 * @param ei2 第二个"数组"的尾元素在原数组中的位置
 *///{8, 4, 12, 2, 6, 10, 14, 1, 3, 15, 7, 11, 9, 5, 13};
void merge(int *const arr, int si1, int ei1, int si2, int ei2) {
    int i = si2, j = si1, step = ei1 - si1 + 1;
    for (; i <= ei2; ++i) {
        for (; j <= ei1; ++j) {
            if (*(arr + i) < *(arr + j)) {
                int start = i++;
                while (step > 1 && i <= ei2 && *(arr + i) < *(arr + j)) { ++i; }//---批量插入优化
                insertInto(arr, j, start, --i);
                break;
            }
        }
    }//两个"数组"合并后,第一个数组的元素能保证是有序的,但第二个就不能保证了,重新合并排序第二个"数组"
    if(ei2 - si2) mergeSort(arr, si2, ei2 - si2 + 1, 1);
}
/**
 * 归并排序(使用的递归的策略)
 * @param arr 待操作的数组的指针
 * @param start 该趟"数组"起始位置
 * @param len 该趟"数组"的长度
 * @param pac 每个等份"数组"中元素的个数
 */
void mergeSort(int *const arr, int const start, int const len, int const pac) {
    int i;
    int combine_len = pac << 1;
    int residue = len % combine_len;//余数
    int base_len = len / combine_len;
    for (i = 0; i < base_len; ++i) {
        int si1 = start + (combine_len * i);
        int ei1 = si1 + pac - 1;
        int si2 = ei1 + 1;
        int ei2 = si2 + pac - 1;
        merge(arr, si1, ei1, si2, ei2);
    }
    if (residue * 1.0f / pac > 1) {
        int si1 = start + (combine_len * i);
        int ei1 = si1 + pac - 1;
        int si2 = ei1 + 1;
        merge(arr, si1, ei1, si2, start + len - 1);
    }
    if (combine_len < len)
        mergeSort(arr, start, len, combine_len);
}
/**
 * 打印数组
 * @param arr 数组的指针
 * @param len 数组的长度
 */
void print(int const *const arr, size_t const len) {
    int i;
    printf("the sequence of arr which have been sorted:\n");
    for (i = 0; i < len; ++i)
        printf("%d ", *(arr + i));
    printf("\n");
}
int main(int argc, char **argv) {
    int arr[] = {8, 4, 12, 2, 6, 10, 14, 1, 3, 15, 7, 11, 9, 5, 13};
    long len = sizeof(arr) / sizeof(int);
    mergeSort(arr, 0, len, 1);
    print(arr, len);
    return 0;
}

附上测试结果:

1
2
the sequence of arr which have been sorted:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15


2016-09-15
— Maizi

FEATURED TAGS
Algorithm Sorting
FRIENDS