数据结构算法之 常见算法

数据结构 阅读量

算法

常见概念

算法的概念

算法是计算机处理信息的本质，因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务。一般的，当算法在处理信息时，会从输入设备或者数据的存储地址读取数据，把结果写入输出设备或者某个存储地址供以后调用。
算法是独立存在的一种解决问题的方法和思想。
对于算法而言，实现的语言并不重要，重要的是思想。
算法可以有不同的语言描述实现版本（Objective-C，Swift，Python，Java描述等），而本文主要用OC，Swift，Python语言进行描述。

算法的5大特性

  1. 输入：算法具有0个或多个输入
  2. 输出：算法至少有1个或多个输出
  3. 有穷性：算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在接受的时间内完成
  4. 确定性：算法中的每一步都有确切的含义，不会出现二义性
  5. 可行性：算法的每一步都是可行的，也就是说每一步都能够执行有限的次数完成

数据结构的概念

数据是一个抽象的概念，将其进行分类后得到程序设计语言中的基本类型。如：int，float，char等。数据元素之间不是独立的，存在特定的关系，这些关系便是结构。数据结构指数据对象中数据元素之间的关系。

算法与数据结构的区别

数据结构只是静态的描述了数据元素之间的关系。高效的程序需要在数据结构的基础上设计和选择算法。
程序 = 数据结构 + 算法
总结：算法是为了解决实际问题而设计的，数据结构是算法需要处理的问题的载体。

常见算法

冒泡排序

冒泡排序（bubble sort）是一种简单的排序算法。它重复的遍历要排序的数组，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数组的工作是重复的进行直到没有再需要交换的元素，也就是说该数组已经排序完成。这个算法名字的由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

图解如下：

原理如下：

  • 比较相邻的元素。如果第一个比第二个大（升序），就交换它们两个。
  • 对每一对相邻的元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  • 针对所有的元素重复以上的步骤，最后一个除外。
  • 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

代码实现如下：

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
// OC实现
- (NSArray *)bubble_sort:(NSMutableArray <NSNumber *>*)array {
    if (array.count == 0) {
        return @[];
    }
    
    for (int i = 0; i < array.count - 1; i ++) {
        int count = 0;
        for (int j = 0; j < array.count - 1 - i; j ++) {
            if (array[j].intValue > array[j + 1].intValue) {
                NSNumber *temp = array[j];
                [array replaceObjectAtIndex:j withObject:array[j + 1]];
                [array replaceObjectAtIndex:(j + 1) withObject:temp];
                
                count ++;
            }
        }
        
        if (count == 0) {
            return array;
        }
    }
    return array;
}

// swift实现
//MARK: - 冒泡排序
func bubble_sort(array: [Int]) -> [Int] {
    if array.count == 0 {
        return []
    }
    
    var newArray = array
    for i in 0..<(newArray.count - 1) {
        var count = 0
        
        for j in 0..<(newArray.count - 1 - i) {
            if newArray[j] > newArray[j + 1] {
                let temp = newArray[j]
                newArray[j] = newArray[j + 1]
                newArray[j + 1] = temp
                count += 1
            }
        }
        
        if count == 0 {
            return newArray
        }
    }
    
    return newArray
}

选择排序

选择排序（selection-sort）是一种简单直观的排序算法。

原理如下：

  • 首先在未排序的数组中找到最小（大）的元素，存放到排序序列的起始位置。
  • 然后在从剩余未排序的元素中继续寻找最小（大）元素，放到已排序序列的末尾。
  • 以此类推，直到所有元素排序完毕。

图解如下：

动画示例：

红色的表示当前最小值，黄色表示已排序元素，蓝色表示当前位置。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，他们当中至少有一个将被移到其最终位置上，因此对n个元素的数组进行排序总共进行至多n-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
39
40
41
42
43
44
45
46
//OC实现
- (NSArray *)select_sort:(NSMutableArray <NSNumber *>*)array {
    if (array.count == 0) {
        return array;
    }
    
    for (int i = 0; i < array.count; i ++) {
        int mix_index = i;
        for (int j = i + 1; j < array.count; j ++) {
            if (array[j].intValue < array[mix_index].intValue) {
                mix_index = j;
            }
        }
        NSNumber *temp = array[i];
        [array replaceObjectAtIndex:i withObject:array[mix_index]];
        [array replaceObjectAtIndex:mix_index withObject:temp];
    }
    
    return array;
}

//swift实现
//MARK: - 选择排序
func select_sort(array: [Int]) -> [Int] {
    if array.count == 0 {
        return []
    }
    
    var newArray = array
    
    for i in (0..<newArray.count) {
        var min_index = i
        
        for j in (i + 1)..<newArray.count {
            if newArray[j] < newArray[min_index] {
                min_index = j
            }
        }
        
        let temp = newArray[i]
        newArray[i] = newArray[min_index]
        newArray[min_index] = temp
    }
    
    return newArray
}

插入排序

插入排序：（insertion-sort）是一种简单直观的排序算法。它的工作原理是通过构建有序的序列。对于未排序的元素，在已排序的元素中从后向前扫描，找到相应的位置并插入。插入排序在实现上，在从后向前的扫描过程中，需要反复把已排序元素逐步向后挪位，为新元素提供插入空间。

图解如下：

示例动画如下：

代码如下：

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
// OC实现
- (NSArray *)insert_sort:(NSMutableArray <NSNumber *>*)array {
    if (array.count == 0) {
        return @[];
    }
    
    for (int i = 1; i < array.count; i ++) {
        for (int j = i; j > 0; j --) {
            if (array[j - 1].intValue > array [j].intValue) {
                NSNumber *temp = array[j - 1];
                [array replaceObjectAtIndex:j - 1 withObject:array[j]];
                [array replaceObjectAtIndex:j withObject:temp];
            }
        }
    }
    return array;
}

// swift实现
//MARK: - 插入排序
func insert_sort(array: [Int]) -> [Int] {
    if array.count == 0 {
        return []
    }
    
    var newArray = array
    
    for i in (1..<newArray.count) {
        for j in (1...i).reversed() {
            if newArray[j - 1] > newArray[j] {
                let temp = newArray[j - 1]
                newArray[j - 1] = newArray[j]
                newArray[j] = temp
            }
        }
    }
    return newArray
}

快速排序

快速排序：（quickSort）又称划分交换排序（partition-exchange sort），通过一趟排序将要排序的数据分割为独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达成整个数据变成有序数组。

步骤如下：

  1. 从数列中挑出一个元素，称为“基准”(pivot)。
  2. 重新排列数列，所有元素比基准值小的摆放在基准前面，所有的元素比基准值大的摆在基准的后面（相同的数可以到任意一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
  3. 递归的把小于基准元素的子数组和大于基准元素的子数组排序。

递归的最底部情形是，数列的大小是0或者1，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，他至少会把一个元素摆到他最后的位置上。

图解如下：

代码如下：

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
//OC代码
/**
 快速选择

 @param array 快排之前的数组
 @param start 开始的下标
 @param end 结束的下标
 @return 排序后的数组
 */
- (NSArray *)quick_sort:(NSMutableArray <NSNumber *>*)array startIndex:(int)start endIndex:(int)end {
    if (start >= end) {
        return array;
    }
    
    int left = start;
    int right = end;
    
    NSNumber *temp = array[left];
    while (left < right) {
        while (left < right && array[right].intValue >= temp.intValue) {
            right --;
        }
        array[left] = array[right];
        
        while (left < right && array[left].intValue < temp.intValue) {
            left ++;
        }
        array[right] = array[left];
    }
    array[left] = temp;
    
    [self quick_sort:array startIndex:0 endIndex:left - 1];
    [self quick_sort:array startIndex:left + 1 endIndex:end];
    
    return array;
}

//Swift代码
//MARK: - 快速排序
func quick_sort(array: inout [Int], start: Int, end: Int) -> [Int] {
    if array.count == 0 {
        return []
    }
    
    if start >= end {
        return []
    }
    
    var left = start
    var right = end
    
    let mid_value = array[left]
    while left < right {
        while (left < right && array[right] >= mid_value) {
            right -= 1
        }
        array[left] = array[right]
        
        while (left < right && array[left] < mid_value) {
            left += 1
        }
        array[right] = array[left]
    }
    array[left] = mid_value
    
    quick_sort(array: &array, start: start, end: left - 1)
    quick_sort(array: &array, start: left + 1, end: end)
    return array
}

希尔排序

希尔排序（shell sort）是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非常稳定的排序算法。该方法因DL. Shell于1959年提出而得名。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

排序过程：
将数组列在一个表中并对列分别进行插入排序，重复这过程，不过每次用更长的列（步长更长了，列数更少了）来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序。

图解如下：

例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样(竖着的元素是步长组成)：

1
2
3
4
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然后我们对每列进行排序：

1
2
3
4
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]。这时10已经移至正确位置了，然后再以3为步长进行排序：

1
2
3
4
5
6
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

排序之后变为：

1
2
3
4
5
6
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

最后以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
39
40
41
42
43
44
45
46
47
48
//OC代码
- (NSArray *)shell_sort:(NSMutableArray <NSNumber *>*)array {
    if (array.count == 0) {
        return array;
    }
    
    int T = @(array.count / 2).intValue;
    while (T) {
        for (int i = T; i < array.count; i ++) {
            int j = i;
            while (j >= T && array[j - T].intValue > array[j].intValue) {
                NSNumber *temp = array[j - T];
                [array replaceObjectAtIndex:j - T withObject:array[j]];
                [array replaceObjectAtIndex:j withObject:temp];
                j -= T;
            }
        }
        
        T /= 2;
    }
    
    return array;
}

//Swift代码
func shell_sort(array: inout [Int]) -> [Int] {
    if array.count == 0 {
        return []
    }
    
    var T: Int = array.count / 2
    while T > 0 {
        for i in (T..<array.count) {
            var j = i
            
            while j >= T && (array[j - T] > array[j]) {
                let temp = array[j - T]
                array[j - T] = array[j]
                array[j] = temp
                j -= T
            }
        }
        
        T /= 2
    }
    
    return array
}

归并排序

归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了之后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另外一个数组的剩余部分复制过来即可。

归并排序分析图解：

代码如下：

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
91
//OC代码
- (NSMutableArray <NSNumber *>*)merge_sort:(NSMutableArray <NSNumber *>*)array {
    if (array.count <= 1) {
        return array;
    }
    
    int mid_index = @(array.count / 2).intValue;
    NSMutableArray <NSNumber *>*left_array = [NSMutableArray array];
    NSMutableArray <NSNumber *>*right_array = [NSMutableArray array];
    
    for (int i = 0; i < mid_index; i ++) {
        [left_array addObject:array[i]];
    }
    
    for (int i = mid_index; i < array.count; i ++) {
        [right_array addObject:array[i]];
    }
    
    left_array = [self merge_sort:left_array];
    right_array = [self merge_sort:right_array];
    
    NSMutableArray <NSNumber *>*result = [NSMutableArray array];
    int left_index = 0;
    int right_index = 0;
    
    while (left_index < left_array.count && right_index < right_array.count) {
        if (left_array[left_index].intValue > right_array[right_index].intValue) {
            [result addObject:right_array[right_index]];
            right_index ++;
        } else {
            [result addObject:left_array[left_index]];
            left_index ++;
        }
    }
    
    for (int i = left_index; i < left_array.count; i ++) {
        [result addObject:left_array[i]];
    }
    
    for (int i = right_index; i < right_array.count; i ++) {
        [result addObject:right_array[i]];
    }
    
    return result;
}

//swift代码
//MARK: - 归并排序
func merge_sort(array: inout [Int]) -> [Int] {
    if array.count <= 1 {
        return array
    }
    
    let mid = array.count / 2
    var left_array: [Int] = []
    for i in (0..<mid) {
        left_array.append(array[i])
    }
    
    var right_array: [Int] = []
    for i in (mid..<array.count) {
        right_array.append(array[i])
    }
    
    left_array = merge_sort(array: &left_array)
    right_array = merge_sort(array: &right_array)
    
    var result: [Int] = []
    var left_p = 0
    var right_p = 0
    
    while left_p < left_array.count && right_p < right_array.count {
        if left_array[left_p] < right_array[right_p] {
            result.append(left_array[left_p])
            left_p += 1
        } else {
            result.append(right_array[right_p])
            right_p += 1
        }
    }
    
    for i in (left_p..<left_array.count) {
        result.append(left_array[i])
    }
    
    for i in (right_p..<right_array.count) {
        result.append(right_array[i])
    }
    
    return result
}

常见的算法这么多，想了解更多的算法和数据结构的可以去看看相关的书籍比如《算法导论》、《数据结构与算法python语言描述》等。本文代码地址点这里

Powered by Hexo and Hexo-theme-hiker

Copyright © 2013 - 2020 KNOWLEDGE IS POWER All Rights Reserved.

访客数 : | 访问量 :