时间复杂度的计算

https://zhuanlan.zhihu.com/p/50479555

选择排序

对于给定的一组记录，经过第一轮比较后得到最小记录，然后将该记录与第一个记录进行交换；接着对不包括第一个记录外的其他记录进行第二轮比较，得到最小记录并与第二个记录进行位置交换；重复该过程，直到进行比较记录只有一个为止。
示例：
原数组：{38,65,97,76,13,27,49}

13【65 97 76 38 27 49】
13 27【97 76 38 65 49】
13 27 38【76 97 65 49】
13 27 38 49【97 65 76】
13 27 38 49 65【97 76】
13 27 38 49 65 76【97】

13 27 38 49 65 76 97 ```python def select_soft(lists):

选择排序

count = len(lists) for i in range(0, count):

 min = i
 for j in range(i + 1, count):
     if lists[min] > lists[j]:
         min = j
 lists[min], lists[i] = lists[i], lists[min]

return lists

new_lists = select_soft([38, 65, 97, 76, 13, 27, 49]) print(new_lists)

<a name="gQNeO"></a>
## 冒泡排序
对于给定的N个记录，从第一个记录开始 依次对相邻的两个记录进行比较，当前面的记录大于后面的记录时，交换其位置，进行一轮比较和换位后，N个记录中最大记录将位于第N位，然后对前（n-1）个记录进行第二轮比较，重复该过程直到比较记录剩下一个为止。<br />**答题语言：**<br />**从宏观来讲我们可以把它我们在生活中按照身高排队的例子，我从前看到后，如果发现前面的比后面高，我就把他往后移动，如果后面比前面高，那就不动，反正就是我的视线从前往后移，只将我视线中的人与这个人后面人的身高进行对比，高的往后移，矮的不变，那么这一轮排序下来可以保证的是：那个最高的现在一定排到最后面，那我现在就不管他了，假设总共有N个人，那我现在只管他前面的N-1个人，在循环上述操作。**
**示例：原数组【36  25  48  12  25  65  43  57  】**
```python
def bubble_sort(lists):
    # 冒泡排序
    for i in range(len(lists) - 1):
        for j in range(len(lists) - i - 1):
            if lists[j] > lists[j + 1]:
                lists[j], lists[j + 1] = lists[j + 1], lists[j]
    return lists
new_lists = bubble_sort([36, 25, 48, 12, 25, 65, 43, 57])
print(new_lists)

快速排序

采用分而治之的思想，大的拆成小的，小的拆成更小的。
从宏观来讲：
对于一组给定的记录，通过一趟排序后，将原序列分为两个部分，其中前部分的所有记录均比后部分所有记录小，然后再依次对前后两部分的记录进行快速排序，递归该过程序列中所有记录均有序为止。
从微观来讲：
假设这个列表的长度为N，那么有两个游标一个是low，一个是high，low往右边移动，high往左边移动，我们要保证的是low < high ，并且在移动的过程中 low < mid，high > mid

假设：low一直往前走，一旦出现low>mid，那么low在这个位置停止，这时high开始走，一旦发现high < mid 那么high停止，这时low和high两数位置交换。（这个交换的过程就是把所有大的都移动到右边去，把所有小的都移动到左边来）
紧接着low又可以走了，如果发生low与high重合，那么这个重合前面的位置，就是这个mid值所应该在的位置
现在就可以发现mid左边的都比mid小，mid右边的都比mid大
同理：再将左右两边的按照上述步骤重复操作执行相同的过程。

就是找出序列的第一个值，然后两边游标相夹，通过改值，把整个序列分成两个部分。

面试

算法

时间复杂度的计算

选择排序

选择排序

快速排序