python 数据结构算法-归并排序和快速排序以及两者的比较_快速排序和归并排序空间复杂度比较

归并排序算法和快速排序及比较

归并排序：

包括两个步骤，分开和合并，它的时间复杂度是O(nlog(n))，但是并不能代表它的排序速度快，因为还要考虑空间复杂度，它需要占用较大的辅助内存空间。

具体实现

假如我们有一个n个数的数列，下标从0到n-1
首先是分开的过程：
1 我们按照 n//2 把这个数列分成两个小的数列
2 把两个小数列 再按照新长度的一半 把每个小数列都分成两个更小的
。。。一直这样重复，一直到每一个数分开了
比如： 6 5 4 3 2 1
第一次 n=6 n//2=3 分成 6 5 4 3 2 1
第二次 n=3 n//2=1 分成 6 5 4 3 2 1
第三次 n=1的部分不分了
n=2 n//2=1 分成 5 4 2 1
之后是合并排序的过程：
3 分开之后我们按照最后分开的两个数比较大小形成正确顺序后组合绑定
刚刚举得例子 最后一行最后分开的数排序后绑定 变成 4 5 1 2
排序后倒数第二行相当于把最新分开的数排序之后变成 6 4 5 3 12
4 对每组数据按照上次分开的结果，进行排序后绑定
6 和 4 5(两个数绑定了) 进行排序
3 和 1 2(两个数绑定了) 进行排序
排完后 上述例子第一行待排序的 4 5 6 1 2 3 两组数据
5 对上次分开的两组进行排序
拿着 4 5 6 1 2 3两个数组，进行排序，每次拿出每个数列中第一个(最小的数)比较，把较小的数放入结果数组。再进行下一次排序。
每个数组拿出第一个数，小的那个拿出来放在第一位 1 拿出来了， 变成4 5 6 2 3
每个数组拿出第一个书比较小的那个放在下一个位置 1 2被拿出来， 待排序 4 5 6 2
每个数组拿出第一个书比较小的那个放在下一个位置 1 2 3 被拿出来， 待排序 4 5 6
如果一个数组空了，说明另一个数组一定比排好序的数组最后一个大 追加就可以结果 1 2 3 4 5 6
相当于我们每次拿到两个有序的列表进行合并，分别从两个列表第一个元素比较，把小的拿出来，在拿新的第一个元素比较，把小的拿出来 这样一直到两个列表空了 就按顺序合并了两个列表
时间复杂度： 最好最坏都是 O( n log n )
稳定性：稳定
缺点：每次拆分数组都要开心的数组， 每次合并数组都要开新数组，空间复杂度很大
在python中这样实现

 def merge_sort( unsort_list ):
      #不断递归调用自己一直到拆分成成单个元素的时候就返回这个元素，不再拆分了
      if len(lunsort_list) == 1:
          return unsort_list
      #取拆分的中间位置
      mid = len(unsort_list) // 2
      #拆分过后左右两侧子串
      left = unsort_list[:mid]
      right = unsort_list[mid:]
 
     #对拆分过后的左右再拆分 一直到只有一个元素为止
     #最后一次递归时候ll和lr都会接到一个元素的列表
     # 最后一次递归之前的ll和rl会接收到排好序的子序列
     ll = merge_sort( left )
     rl =merge_sort( right ) 
     # 我们对返回的两个拆分结果进行排序后合并再返回正确顺序的子列表
     # 这里我们调用拎一个函数帮助我们按顺序合并ll和lr
     return merge(ll , rl)
 
 #这里接收两个列表
 def merge( left , right ):
     # 从两个有顺序的列表里边依次取数据比较后放入result
     # 每次我们分别拿出两个列表中最小的数比较，把较小的放入result
     result = []
     while len(left)>0 and len(right)>0 :
         #为了保持稳定性，当遇到相等的时候优先把左侧的数放进结果列表，因为left本来也是大数列中比较靠左的
         if left[0] <= right[0]:
             result.append( left.pop(0) )
         else:
             result.append( right.pop(0) )
     #while循环出来之后 说明其中一个数组没有数据了，我们把另一个数组添加到结果数组后面
     result += left
     result += right
     return result
 
 if __name__ == '__main__':
     li = [5,4 ,3 ,2 ,1]
     li2 = merge_sort(li)
     print(li2)
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

另一个实现过的代码;

def merge_sort(unsort_list):
    if len(unsort_list)==1:
        return unsort_list
    length = len(unsort_list)
    mid = length//2
    ll = unsort_list[:mid]
    rl =unsort_list[mid:]
    ll = merge_sort(ll)
    rl = merge_sort(rl)
    return merge(ll,rl)
    
def merge(ll,rl):
    s_list=[]
    while (len(ll)>0 and len(rl)>0):
        if ll[0]<=rl[0]:
            s_list.append(ll.pop(0))
        else:
            s_list.append(rl.pop(0))
    s_list += ll
    s_list += rl
    return s_list
 
if __name__=="__main__":
    unsort_input = input("Enter the list of needing sort separate by clima\n").strip()
    unsort_input = [int(tmp) for tmp in unsort_input.split(':')]
    print(merge_sort(unsort_input))
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

快速排序（Quicksort）

快速排序(quick sort)的采用了分治的策略。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

1、原理

1.在数列之中，选择一个元素作为”基准”（pivot），或者叫比较值。
2.数列中所有元素都和这个基准值进行比较，如果比基准值小就移到基准值的左边，如果比基准值大就移到基准值的右边
3.以基准值左右两边的子列作为新数列，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

2.快排的特点

1.稳定性：快排是一种不稳定排序，比如基准值的前后都存在与基准值相同的元素，那么相同值就会被放在一边，这样就打乱了之前的相对顺序

2.比较性：因为排序时元素之间需要比较，所以是比较排序

3.时间复杂度：快排的时间复杂度为O(nlogn)；空间复杂度：排序时需要另外申请空间，并且随着数列规模增大而增大，其复杂度为：O(nlogn)
4.归并排序与快排 ：归并排序与快排两种排序思想都是分而治之，但是它们分解和合并的策略不一样：归并是从中间直接将数列分成两个，而快排是比较后将小的放左边大的放右边，所以在合并的时候归并排序还是需要将两个数列重新再次排序，而快排则是直接合并不再需要排序，所以快排比归并排序更高效一些。
快速排序有一个缺点就是对于小规模的数据集性能不是很好。

python 实现代码：

def quick_sort(unsort_list):
    
    if len(unsort_list) >= 2:
        #index = 0
        left = []
        right = []
        mid = unsort_list[len(unsort_list)//2] #找一个比较值
        unsort_list.remove(mid) #移除比较值
        for tmp in unsort_list:
            if tmp <= mid:
                left.append(tmp)#小于比较值的放在左边
            else:
                right.append(tmp) #大于的放在右边
        return quick_sort(left)+[mid]+quick_sort(right) #递归实现
    else:
        return unsort_list #递归停止的条件
b = [11, 99, 33, 69, 77, 88, 55, 11, 33, 36, 39, 66, 44, 22]
quick_sort(b)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18