目录[-]

查找


二分查找

- 代码实现:
- 利用递归原理
    python
        def binary_search(start_index, end_index, list, item):
            mid_index = (start_index + end_index)//2
            if start_index > end_index:
                return -1
            if list[mid_index] == item:
                return mid_index
            elif list[mid_index] < item:
                return binary_search(mid_index, end_index, list, item)
            else:
                return binary_search(start_index, mid_index, list, item)

排序


排序分为以下几种:

时间复杂度与空间复杂度对照:

冒泡排序:

- 把相邻的元素两两比较,当一个元素大于右侧相邻元素时,交换他们的位置;当一个元素小于等于右侧相邻元素时,位置不变。
- 是一种稳定排序,值相等的元素并不会打乱原有的顺序。每一轮都要遍历元素,总共遍历(元素数量-1)轮,所以平均时间复杂度为o(n^2)
- 代码实现
    ```python
        def bubble_sort(list):
            for i in range(len(list)):
                for j in range(len(list)-i-1):
                    if list[j-1] > list[j]:
                        list[j-1],list[j] = list[j],list[j-1]
                print(list)

    list = [12,44,3,20,17]
    bubble_sort(list)
```
运行结果:
```
    ---------
    [12, 44, 3, 20, 17]
    ---------
    [12, 3, 44, 20, 17]
    ---------
    [12, 3, 20, 44, 17]
    ---------
    [12, 3, 20, 17, 44]
    ---------
    [3, 12, 20, 17, 44]
    ---------
    [3, 12, 20, 17, 44]
    ---------
    [3, 12, 17, 20, 44]
    ---------
    [3, 12, 17, 20, 44]
    ---------
    [3, 12, 17, 20, 44]
    ---------
    [3, 12, 17, 20, 44]

```

快速排序:

- 是对冒泡排序的改进,通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
- 代码实现递归思想
    python
        def quick_sort(list):
            if len(list) >= 2:
                mid = list[len(list) // 2]  # 选取基准
                left, right = [], []  # 定义基准左右两侧的列表
                list.remove(mid)  # 从原始数据中移除基准值
                for num in list:
                    if num >= mid:
                        right.append(num)
                    else:
                        left.append(num)
                return quick_sort(left) + [mid] + quick_sort(right)
            else:
                return list

简单选择排序:

  • 所需移动记录的次数比较少,最好的情况下,即待排序记录初始状态就已经是正序排列了,不需要移动记录
  • 方法是所排序序列的记录个数为n。i取1,2,….,n-1,从所有n-i+1个记录(Ri,Ri+1,…,Rn)中找出排序码最小的记录,与第i个记录交换。执行n-1趟后就完成了记录序列的排序
  • 代码实现:
    def choice_sort(list):
      for i in range(len(list) - 1):
          min_index = list.index(min(list[i + 1:]))
          list[i], list[min_index] = list[min_index], list[i]
      return list
    
  • 堆排序:
    • 利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),是不稳定排序。