【排序】常用的有几种？

先上十大排序的分析图，当然其中希尔排序的分析我不太确定，大家忽略即可


别被吓着了，就参考看看，也没必要全部掌握，lz一般常用三种：快排、归并排序、堆排序，当然冒泡、插入排序也比较常用，不过刷题这么久还没遇到必须冒泡插入的。所以就介绍下快排和归并，堆排序其实是根据具体题目进行堆优化，今天先focus on排序

1、快速排序
三个步骤：
    （1）在数组中找一个数k，一般是取中间的
    （2）把数组中小于k的放其左边，大于k的放其右边
    （3）递归处理两边
基本思路是这样，在进行第（2）步的时候，实际上用的双指针，大家可以参考下代码
具体讲下边界问题，下方代码红色部分可以看到，虽然是取中间的数，但写的(l+r)>>1，而递归处理两边的时候，前一部分带入的是l ~ j，后部分带入的是j+1 ~ r，这就是边界问题；比如当只有两个数[0, 1]时，此时l, r分别为0和1，假如我们找的数的位置是（l+r+1）>>1  =  0 + 1 + 1 >>1  =  1，因此选中的数是右边的1，在while循环里出来后i = 1, j = 1，因此递归处理两边时，左边的范围是0 ~ 1，右边是2 ~ 1；右边的会直接return，但左边的范围0~1和当前的l ~ r即0~1是一样的，无限递归下去

结论：当选择(l+r)>>1，递归处理的范围就要写 l ~ j 和 j + 1 ~ r，这就是用j进行划分

那可不可以用i来划分呢？当然可以

换一种方式：当用i划分时，就写成 l ~ i-1和i ~ r，而选取的位置就应该是（l+r+1）>>1

至于为什么这样，都是前辈高人们总结出来的，感兴趣的话可以自己用一些例子调试，都是边界问题，如果不想深究了，那就记住好了~当然还有些细节问题，可以看看注释

<>

1. n = int(input())
   
2. nums = list(map(int, input().split()))
   
3. 
   
4. def quick_sort(nums, l, r):
   
5.     if(l >= r): # 只有一个数或没有
   
6.         return
   
7.     pick, i, j = nums[[color=#ff0000](l+r)>>1[/color]], l-1, r+1
   
8.     while i<j:
   
9.         i+=1
   
10.         while nums[i] < pick:
    
11.             i += 1
    
12.         j-=1
    
13.         while nums[j] > pick:
    
14.             j -= 1
    
15.         if i < j: # 这个改成≤是无所谓的，等于时交换无影响
    
16.             nums[i], nums[j] = nums[j], nums[i]
    
17.     quick_sort(nums, l, [color=#ff0000]j[/color]) # 若这换成i-1，下面换成i，则前面的nums里(l+r)>>1也要再加1，防止边界问题
    
18.     quick_sort(nums, [color=#ff0000]j+1[/color], r)
    
19. 
    
20. if __name__ == "__main__":
    
21.     quick_sort(nums, 0, n-1) # 列表整个传参时，相当于引用传参
    
22.     for i in range(n):
    
23.         print(nums[i], end=" " if i<n-1 else "")

复制代码

2、归并排序
三个步骤：
    （1）在数组中找一个位置k，一般是取中间的
    （2）先对左边的进行归并排序，再对右边进行归并排序
    （3）将已经排好序的两边进行归并
其实这个归并的思想不止是在排序的时候用，刷题的时候有时也会用到

这里的边界问题和快排是类似的，当mid = (l+r+1)>>1时，在递归到子数组长度为2时，mid会取到右边界 r，下个循环的范围又是l~r，无限循环了

因此，当mid = (l+r)>>1，范围应该是l~mid和mid+1~r
当mid = （l+r+1）>>1，范围写l~mid-1和mid~r

当然归并里面除了改边界，还要该归并时操作的范围，下面是第一种mid = (l+r)>>1的情况，当mid = (l+r+1)>>1的情况，大家可以自己动手试试

1. n = int(input())
   
2. nums = list(map(int, input().split()))
   
3. 
   
4. def merge_sort(nums, l, r):
   
5.     if l >= r:
   
6.         return
   
7. 
   
8.     mid = [color=#ff0000](l + r) >> 1[/color]
   
9.     merge_sort(nums, l, [color=#ff0000]mid[/color])
   
10.     merge_sort(nums, [color=#ff0000]mid + 1[/color], r)
    
11. 
    
12.     i, j, tmp = l, mid + 1, []
    
13. 
    
14.     while i <= mid and j <= r:
    
15.         if nums[i] <= nums[j]:
    
16.             tmp.append(nums[i])
    
17.             i += 1
    
18.         else:
    
19.             tmp.append(nums[j])
    
20.             j += 1
    
21. 
    
22.     if i <= mid:
    
23.         tmp.extend(nums[i:mid+1])
    
24.     if j <= r:
    
25.         tmp.extend(nums[j:r+1])
    
26. 
    
27.     nums[l:r+1] = [per for per in tmp]
    
28. 
    
29. if __name__ == "__main__":
    
30.     merge_sort(nums, 0, n-1)
    
31.     for i in range(n):
    
32.         print(nums[i], end=" " if i < n-1 else "")

复制代码

最后，求米各位！！加米不扣自己的！