基础算法

排序 查找 数据结构

Posted by jiang on December 8, 2018

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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
from tools import timer,num_timer,Time


def bubblesort(a):
    n=len(a)
    for i in range(n):
        for j in range(i+1,n):
            if a[j]>a[i]:
                a[i],a[j]=a[j],a[i]
    return a

def selectionsort(a):
    n=len(a)
    for i in range(n):
        small=i
        for j in range(i+1,n):
            if a[small]>a[j]:
                small=j
        if i!=small:
            a[i],a[small]=a[small],a[i]
    return a

def insertsort(a):
    n=len(a)
    for i in range(n):
        k=i
        v=a[i]
        while k>0 and a[k-1]>v:
            a[k]=a[k-1]
            k-=1
        a[k]=v
    return a

def quicksort(a):
    def _quicksort(a):
        if len(a)<=1:
            return a
        n=a.pop()
        less=[]
        more=[]

        for i in range(len(a)):
            if a[i]<=n:
                less.append(a[i])
            else:more.append(a[i])
        return _quicksort(less)+[n]+_quicksort(more)
    return _quicksort(a)


def mergesort(a):
    def merge(la,lb):
        if len(la)>len(lb):
            la,lb=lb,la
        n=len(la)
        m=len(lb)
        res=[]
        i=j=0
        while i<n and j<m:
            if la[i]<lb[j]:
                res.append(la[i])
                i+=1
            else:
                res.append(lb[j])
                j+=1
        if i==n:
            res.extend(lb[j:])
        else:
            res.extend(la[i:])
        return res

    def _mergesort(a):
        hi=len(a)
        if hi<=1:
            return a
        lo=0
        mid=(hi+lo)//2
        fl=_mergesort(a[:mid])
        el=_mergesort(a[mid:])
        return merge(fl,el)

    return _mergesort(a)

def insertSort(nums):
    '''
    每步将一个待排序的记录,
    按其关键码值的大小插入前面已经排序的数组中适当位置上,
    直到全部插入完为止。
    :param nums:
    :return: nums
    '''
    for i in range(len(nums)):
        for j in range(0,i):
            if nums[i]<nums[j]:
                nums[i],nums[j] = nums[j],nums[i]
    return nums


def bubbleSort(nums):
    '''
    :param nums:
    :return:
    '''
    for i in range(len(nums)):
        for j in range(i,len(nums)):
            if nums[i]>nums[j]:
                nums[i],nums[j] = nums[j],nums[i]
    return nums

def binarySearch(nums,item):
    '''
    :param nums:
    :param item:
    :return:
    '''
    low = 0
    high = len(nums) - 1
    while low <= high:
        mid = (low+high)//2
        if nums[mid]==item:
            return True
        elif nums[mid]<item:
            low = mid + 1
        else:
            high = mid - 1
    return False

def mergeSort(nums):
    def _merge(nums1,nums2):
        '''
        :param nums1:
        :param nums2:
        :return:
        '''
        res = []
        len1 = len(nums1)
        len2 = len(nums2)
        i = j = 0
        while i<len1 and j<len2:
            if nums1[i]<=nums2[j]:
                res.append(nums1[i])
                i += 1
            else:
                res.append(nums2[j])
                j += 1

        if len(nums1)==i:
            res.extend(nums2[j:])
        else:
            res.extend(nums1[i:])
        return res
    if len(nums)<=1:
        return nums
    mid = len(nums)//2
    low = mergeSort(nums[:mid])
    high = mergeSort(nums[mid:])
    return _merge(low,high)

def selectSort(nums):
    '''
    它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,
    存放在序列的起始位置,
    然后,再从剩余未排序元素中继续寻找最小(大)元素,
    然后放到已排序序列的末尾。
    以此类推,直到全部待排序的数据元素排完。
    选择排序是不稳定的排序方法。
    :param nums:
    :return:
    '''
    for i in range(len(nums)):
        min = i
        for j in range(i+1,len(nums)):
            if nums[min]>nums[j]:
                min = j
        if min!=i:
            nums[min],nums[i] = nums[i],nums[min]

    return nums


def quickSort(nums,left,right):
    '''
    :param nums: 数组
    :param left: 下标
    :param right: 上标
    :return: none
    '''
    if left>right:return
    i,j = left,right
    tmp = nums[left]
    while i!=j:
        while nums[j]>=tmp and i<j:
            j-=1

        while nums[i]<=tmp and i<j:
            i+=1
        if i<j:
            nums[i],nums[j] = nums[j],nums[i]

    nums[left],nums[i] = nums[i],tmp
    quickSort(nums,left,i-1)
    quickSort(nums,i+1,right)

def shellSort(arr):
    '''
    是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),
    是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法
    希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;
    随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
    :param arr:
    :return:
    '''
    n = len(arr)
    h = 1
    while h<n/3:
        h = 3*h + 1

    while h >= 1:
        for i in range(h,n):
            j = i
            while j >= h and arr[j] < arr[j-h]:
                arr[j],arr[j-h] = arr[j-h],arr[j]
                j -= h
        h = h//3

def binaryInsertSort(arr):
    '''
    折半插入排序又称二分法插入排序,是插入排序的一种,其基本思想是:设在数据表中有一个元素序列V[0],V[1],…,V[n-1]。
    其中V[0],V[1],…,V[i-1]是已经排好序的元素。在插入V[i]时,利用折半搜索方法寻找V[i]的位置。
    :param arr:
    :return:
    '''
    for i in range(1, len(arr)):
        tmp = arr[i]
        low, high = 0, i - 1
        while low <= high:
            mid = (low + high) // 2
            if arr[mid] >= tmp:
                high = mid - 1
            else:
                low = mid + 1

        j = i - 1
        while j >= low - 1:
            arr[j + 1] = arr[j]
            j -= 1
        arr[low] = tmp
    return arr

def heapSort(arr):
    '''
    堆排序(英语:Heapsort)是指利用堆这种数据结构所设计的一种排序算法。
    堆是一个近似完全二叉树的结构,并同时满足堆积的性质:
    即子结点的键值或索引总是小于(或者大于)它的父节点。
    :param arr:
    :return:
    '''
    def bigEndian(arr,start,end):
        root = start
        while True:
            child = root*2+1
            if child>end:
                break
            if child+1 <= end and arr[child]<arr[child+1]:
                child+=1
            if arr[root]<arr[child]:
                arr[root],arr[child] = arr[child],arr[root]
                root=child
            else:
                break

    first = len(arr)//2 - 1
    for i in range(first,-1,-1):
        bigEndian(arr,i,len(arr)-1)
    for j in range(len(arr)-1,0,-1):
        arr[0],arr[j] = arr[j],arr[0]
        bigEndian(arr,0,j-1)


a=[1,2,4,1,1,2,34,56,7,1]
bubbleSort(a)
print(a)

2.查找

  • 二分查找
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    
    def binary_search(s,a):
      low = 0
      high = len(s) - 1
      while low<=high :
          mid = (low + high) // 2
          print('low:{} high:{} mid:{},s:{}'.format(low,high,mid,s[mid]))
          if s[mid] == a:
              return True
    
          if s[mid] < a:
              low = mid + 1
          else:
              high = mid - 1
    
      return False
    

3.数据结构

  • 优先级队列
  • 链表
  • 队列
  • 堆栈
  • map
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    
    class priorityQueue:
      '''
      [(1,A),(2,D)]
      '''
      def __init__(self):
          self.data = []
      def add(self,item):
          if len(self.data)==0:
              self.data.append(item)
              return
          for k,v in enumerate(self.data):
              if v[0]>=item[0]:
                  break
          else:
              k += 1
          self.data.insert(k,item)