1 选择法
原理
简单说来就是每次遍历列表，选出其中最小的，放在新的列表中。为了节省空间，对于单一列表来说，则是遍历列表，选出最小的元素，与排在第一位的元素交换位置，以此类推。
时间复杂度
虽然每次检查的元素都减少了，但是由于大O表示法省略常数，其时间复杂度为O(n2)
代码
for(i = 0;i < n-1;i++)
{
temp = a[i];
iPot = i;
for(j = i+1;j < 10;j++) //从每一个数字依次向后查找
{
if(a[j] < temp)
{
temp = a[j]; //记录当前查找到的最小值与最小值对应的位号
iPot = j;
}
}
a[iPot] = a[i];
a[i] = temp;
}
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 <= 9; i++)//外层循环是比较的轮数，数组内有10个数，那么就应该比较10-1=9轮
{
for (j = 0; j <= 9 - i; j++)//内层循环比较的是当前一轮的比较次数，例如：第一轮比较9-1=8次，第二轮比较9-2=7次
{
if (n[j] > n[j + 1])//相邻两个数如果逆序，则交换位置
{
temp = n[j];
n[j] = n[j + 1];
n[j + 1] = temp;
}
}
}
printf("排序过后的数顺序:\n");
for (i = 0; i < 10; i++)
printf("%-4d", n[i]);
printf("\n");
3 快速排序
原理
选取中间值，把比中间值小的数字放在左边，比中间值大的数字放在右边，两边分别递归使用这个过程。
时间复杂度
O(nlogn)
代码
CelerityRun(int left,int right,int array[])
{
int i,j;
int middle;
int temp;
i = left;
j = right;
middle = array[((right - left) >> 1) + left]; //实际这里的middle可以取左右边界内任意的一个值
do
{
while((array[i] < middle) && (i < right))
{
i++;
}
while((array[j] > middle) && (j > left))
{
j--;
}
if(i<=j)
{
temp = array[i];
array[i] = array[j];
array[j] = array[i];
i++;
j--;
}
}while(i<=j)
if(left < j)
CelerityRun(left,j,array);
if(right > i)
CelerityRun(i,right,array);
}
====================================分割==================================
leetcode例题：合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
进阶：你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？
解1：选择法
分析
可以直接用上述方法做该题。
代码
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.append(nums2)
# for i in range(nums1):
# temp = nums1[i]
t=0
for k in range(m,len(nums1)):
nums1[k] = nums2[t]
t += 1
for i in range(len(nums1)):
for j in range(i+1,len(nums1)):
if nums1[i]>nums1[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博客
参考文章
发表评论