从头到尾遍历,找最大的元素的下标,找到之后把最大的元素和最后一个位置的元素交换

易错点:

• 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的范围造成越界,需要单独处理