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
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
class Node:
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next

    def __str__(self):
        return str(self.data)

    def delete(self):
        self.data = None
        self.next = None

class LNode:
    def __init__(self, has_head=True):
        self.node = None
        if has_head:
            self.head = None
        self.length = 0
    
    def if_has_head(self):
        if hasattr(self, 'head'):
            return True
        else:
            return False

    def is_empty(self):
        if self.length == 0:
            return True
        return False

    def append(self, data):
        current = self.node
        if self.is_empty():
            self.node = Node(data)
        else:
            while current.next:
                current = current.next
            current.next = Node(data)
        self.length += 1
        
    def insert(self, pos, data):
        if pos > self.length + 1 or pos <=0:
            return False
        if pos == 1:
            self.push(data)
        else:
            current = self.node
            for i in range(pos-2):
                current = current.next
            temp = current.next
            current.next = Node(data,temp)
            self.length += 1
        return True

    def push(self, data):
        temp = self.node
        self.node = Node(data,temp)
        self.length += 1

    def pop(self):
        last = self.node
        for i in range(self.length-2):
            last = last.next
        data = last.next.data
        last.next.delete()
        last.next = None
        self.length -= 1
        return data

    def remove(self, pos):
        if pos > self.length or pos <= 0:
            return False
        else:
            if pos == 1:
                next = self.node.next
                self.node.delete()
                self.node = next
            else:
                last = self.node
                for i in range(pos-2):
                    last = last.next
                current = last.next
                next = current.next
                last.next = next
                current.delete()
            self.length -= 1
            return True

    def get_node(self, pos):
        if pos > self.length or pos <= 0:
            return None

        current = self.node
        for i in range(pos-1):
            current = current.next
        return current.data

    def find_node(self, data):
        current = self.node
        pos = 1
        while current:
            if current.data == data:
                return pos
            else:
                pos += 1
                current = current.next
        return -1 

    def get_lnode(self):
        current = self.node
        result = []
        while current:
            result.append(current.data)
            current = current.next
        return result

    def clear(self):
        if self.if_has_head:
            self.head = None
        current = self.node
        self.node = None
        while current:
            temp = current.next
            current.next = None
            current.delete()
            current = temp
        self.length = 0

    def __len__(self):
        return self.length
单链表的反转
1

插入排序

概述

  • 将新元素插入到有序序列中。

    步骤

  • 假设序列中第一个元素为有序序列，将其余元素都当做待插入元素处理
  • 每次当前待插入元素与有序序列最后一个元素开始依次进行比较，如果小于被比较元素，则进行交换，交换后继续进行比较直至有序序列第一个元素
  • 将列表分为有序区，待插入的无序区

代码实现

Python 插入排序
1
2
3
4
5
6
def sort_cr(v_list):
    for i in range(len(v_list)):
        for j in range(i,0,-1):
            if v_list[j] < v_list[j-1]:
                v_list[j],v_list[j-1] = v_list[j-1],v_list[j]
    return v_list
C 插入排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void svoid insertion_sort(int array[],int first,int last)
{
    int i,j;
    int temp;
    for(i=first+1;i<last;i++)
    {
        temp=array[i];
        j=i-1;
        //与已排序的数逐一比较，大于temp时，该数移后
        while((j>=0)&&(array[j]>temp))
        {
            array[j+1]=array[j];
            j--;
        }
        //存在大于temp的数
        if(j!=i-1)
            array[j+1]=temp;
    }
}

性能分析

时间复杂度

时间复杂度为O(n^2)

算法稳定性
  • 比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。
  • 如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。
  • 相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，排序是稳定的。

选择排序

概述

  • 走访列表长度次，每次选出最小（或最大）的元素，重新排顺序

步骤

  • 第一次选出最小（或最大）的元素，放在列表的起始位置，即与开头元素交换
  • 接下来每次选出最小（或最大）的元素，与索引等于当前的循环次数的元素进行交换
  • 将列表分为已选择出来的有序区，等待选择的无序区

代码实现

Python 选择排序
1
2
3
4
5
6
7
8
def sort_xz_1(v_list):
    for i in range(len(v_list)-1):
        min = i
        for j in range(i+1,len(v_list)):
            if v_list[min] > v_list[j]:
                min = j
        v_list[min],v_list[i] = v_list[i],v_list[min]
    return v_list
C选择排序
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
void swap(int*a,int*b)
{
    int temp;
    temp=*a;
    *a=*b;
    *b=temp;
}
void select_sort(int A[],int n)
{
    register int i,j,min,m;
    for(i=0;i<n-1;i++)
    {
        min=i;//查找最小值
        for(j=i+1;j<n;j++)
        {
            if(A[min]>A[j])
            {
                min=j;
            }
        }
        if(min!=i)
        {
            swap(&A[min],&A[i]);
            printf("第%d趟排序结果为:\n",i+1);
            for(m=0;m<n;m++)
            {
                if(m>0)
                {
                    printf("");
                }
                printf("%d",A[m]);
            }
            printf("\n");
        }
    }
}

性能分析

时间复杂度

比较时间复杂度为O(n^2)
交换时间复杂度未O(n)

算法稳定性
  • 在一趟选择中，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。
  • 举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。

冒泡排序

概述

  • 重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
  • 这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

步骤

  • 走n-1次，两两相比，当次当前的比较元素的索引最大值为未被比较元素（未冒泡）的索引-1
  • 每次从第一个元素开始进行两两比较。如果当前元素比下一个元素大，就交换他们两个，接下来有下一个元素与自己的下一个元素进行两两比较。
  • 当次最后的元素是本轮比较结果中最大的数，已冒好泡，下次无需理会。
  • 重复对未冒泡好的左区进行冒泡处理
  • 每轮比较结束后 ，已冒泡元素新增一个

代码实现

Python 冒泡排序

1
2
3
4
5
6
def sort_mp_py(v_list):
    for i in range(len(v_list)-1):
        for j in range(len(v_list)-i-1):
            if v_list[j] > v_list[j+1]:
                v_list[j],v_list[j+1] = v_list[j+1],v_list[j]
    return v_list

C冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
void sort_mp_c (elemType arr[], int len) {
    elemType temp;
    int i, j;
    for (i=0; i<len-1; i++) 
        for (j=0; j<len-1-i; j++) { 
            if (arr[j] > arr[j+1]) {  
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
}

性能分析

时间复杂度

平均时间复杂度为O(n^2)

算法稳定性

  • 冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。
  • 如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
Copyright © 2020 Fzg5_Shelling | Powered by Hexo | Theme by Snippet | Deploys by Netlify