从头到尾遍历,找最大的元素的下标,找到之后把最大的元素和最后一个位置的元素交换
易错点:
- max作为保存最大元素下标的存在,每次使用完应该清零
- 找到值去交换,最大的元素位置是没有发生变化的
将一次选择一个最大值变为一次选择一个最大值和最小值
最大值放在最后面的end位置,最小值放在最前面的begin位置
普通选择排序缺陷:
- 存在大量的重复比较
易错点:
- index的值每次遍历查找前要重置
- minpos和maxpos使用完之后的值也要重置
对一组数据,一直均分到一组只有一个元素,然后将其归并,逐步变为有序
易错点:
- 只有元素有序才可以归并
- begin2是以mid开始,如果以mid+1开始,会越界
- 先处理左半部分,在处理右半部分,都有序之后,归并,写回原数组
- 归并的时候申请辅助空间如果是在函数里,函数调用结束会释放,所以使用参数传递进去
- 空间只需要一份,所以不能当作mergeData的参数,因为递归进来每次都会创建
-
使用两个指针来依次对比左半部分和右半部分的第一个元素,先把小的放进去
-
放进去的那部分指针后移,继续比较,一直比到放完为止,长度不一致的情况循环结束单独处理
为了方便调用,进行一下封装,其实不封装也无所谓,那时候还没学C++所以用malloc,现在自然用new
说真的,我不是很喜欢递归的归并排序代码,我觉得memcpy那里需要加left真的很难理解
- 0-5这一整体,分组0-1 2-5,处理右边的部分的时候left是2,如果处理完了往回拷贝的时候不加left
- array默认指向数组第一个元素,等于2-5这边的数据没有接在前两个元素后面,而是有两个把之前的左半部分覆盖了
与递归不同的是,循环不需要先分组了,因为每个元素都是单独的,可以看作已经分好组了,直接开始归并
易错点:
- 需要在循环里手动赋予left的值
- i应该+=2*gap
- gap可以看作一组元素的个数,所以left,mid,right的值用gap表示
- mid和right有可能会超出size的范围造成越界,需要单独处理