排序算法（以从小到大排列为例）

1 选择法

原理

���单说来就是每次遍历列表，选出其中最小的，放在新的列表中。为了节省空间，对于单一列表来说，则是遍历列表，选出最小的元素，与排在第一位的元素交换位置，以此类推。

时间复杂度

虽然每次检查的元素都减少了，但是由于大O表示法省略常数，其时间复杂度为O(n2)

代码

for(i = 0;i  
2 冒泡法
 
原理
 
将相邻两个数比较，小的放到前面，多次循环比较，可以使最大的数“沉底”，最小的数“浮起”。
（） 
n个数,进行n-1趟比较。在第1趟比较中要进行n-1次两两比较,在第i趟比较中要进行n-i次两两比较。
 
时间复杂度
 
外循环是进行比较的趟数，内循环是两两比较的次数。时间复杂度为O(n2)。
 
代码
 
int n[10] = { 25,35,68,79,21,13,98,7,16,62 };//定义一个大小为10的数组int i, j, temp;for (i = 1; i > 1) + left]; //实际这里的middle可以取左右边界内任意的一个值do{while((array[i]  middle) && (j > left)){j--;}if(inums1[j]:                    a = nums1[i]                    nums1[i] = nums1[j]                    nums1[j] = a        return nums1
 
注意事项
 
1.该种方法时间复杂度较高
 
2.在合并两个数组时不能直接使用nums1.append(nums2),因为nums1中后面有0元素来占位
 
3.针对某一计数参数，每次+1的情况，在python中除了可以用for in range之外，还可以直接用+=，直接修改该参数的值，更加方便直观
 
解2：sort函数排序法
 
分析
 
sort()在原数组上对数组元素进行排序，排序时不创建新的数组副本
 
代码
 
class Solution(object):    def merge(self, nums1, m, nums2, n):        """        :type nums1: List[int]        :type m: int        :type nums2: List[int]        :type n: int        :rtype: None Do not return anything, modify nums1 in-place instead.        """        nums1[m:] = nums2        nums1.sort()        return nums1
 
注意事项
 
1.此处使用了一种直接将nums1后续元素赋值为nums2的方法，不需要遍历每个元素位置进行赋值。
 
2.该种方法时间复杂度为O(n log n)，空间复杂度为O(n）
 
解3：双指针算法
 
分析
 
针对进阶题目，上述方法均无法满足要求。由于时间复杂度为 O(m + n) ，说明两个数组只能遍历1次。故考虑双指针算法。
 
而且由于nums1的后面是空的，故采用逆向双指针，利用nums1和nums2已经是有序数组的条件，对数组进行合并和排序。
 
代码
 
class Solution(object):    def merge(self, nums1, m, nums2, n):        """        :type nums1: List[int]        :type m: int        :type nums2: List[int]        :type n: int        :rtype: None Do not return anything, modify nums1 in-place instead.        """        p1 = m-1; p2 = n-1; p3 = m+n-1        while p1 >= 0 or p2>= 0:            if p1 == -1:                nums1[p3] = nums2[p2]                p2 -= 1            elif p2 == -1:                nums1[p3] = nums1[p1]                p1 -= 1            elif nums1[p1] > nums2[p2]:                nums1[p3] = nums1[p1]                p1 -= 1            else :                nums1[p3] = nums2[p2]                p2 -= 1            p3 -= 1
 
注意事项
 
1.特殊情况（有一个数组遍历完成）写在前面，避免数组索引超出限制
 
2.由于每次选出当前最大值放入nums1后面，p3指针每次需要-1
 
====================================分割==================================
 
参考文章：
 
C语言中数组的排序算法详解——选择法、冒泡法、交换法、插入法、折半法_c语言中选择法是什么-CSDN博客
 
C语言—冒泡排序_冒泡排序c语言-CSDN博客