设计一套网站多少钱,CMS网站建设优势,潍坊优化网站,上海网络维护哪家品质好目录
直接选择排序算法的思想
优化直接选择排序算法的思想
代码实现#xff08;默认升序#xff09; 直接选择排序算法的思想
直接选择排序算法的思想类似与直接插入排序 区别在于从大到小选择最小的元素或者最大的元素直接放在元素应该停留的位置每次从待排序的元素中选…目录
直接选择排序算法的思想
优化直接选择排序算法的思想
代码实现默认升序 直接选择排序算法的思想
直接选择排序算法的思想类似与直接插入排序 区别在于从大到小选择最小的元素或者最大的元素直接放在元素应该停留的位置每次从待排序的元素中选出最小或者最大的元素根据降序或者升序选择 存放在序列的起始位置直到全部待排序的数据元素排完为止 优化直接选择排序算法的思想
优化前
每次从待排序的元素中选出最小或者最大的元素存放到应该停留的位置再次选出次大或者次小的数存放到应该停留的位置这样做的话每次只能选出一个元素
优化后
而可以优化的是每次在待排序的元素中选出最大和最小的两个元素放在各自最后应该停留的位置 再选出次大和次小的元素放在最后改停留的位置 代码实现默认升序
代码演示
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}void SelectSort(int* a, int size)
{int left 0;int right size - 1;while (left right){int min left;int max right;for (int i left; i right; i){if (a[i] a[min]){min i;}if (a[i] a[max]){max i;}}Swap(a[left], a[min]);if (max left){max min;}Swap(a[right], a[max]);left;right--;}
}
代码解析
left 表示数组首元素的下标right 表示数组尾元素的下标 以排成升序为例 找到数组中最小的元素时就放在下标为 left 的元素处 注意这里的放入不是直接覆盖首元素而是和首元素交换 且找到数组中最大的元素时就放在下标为 right 的元素处同样是交换 再找到数组中次小的元素和次大的元素进行交换……………… 每交换一对元素那么 left 就递增 1 而 right 就递减 1 直到 left right 时说明所有元素都停留再了最后应该停留的位置 这时的数组就是升序
min 是数组中最小元素的下标而 max 是数组中最大元素的下标 再通过 left 和 right 为数组的区间来遍历数组找到最小元素的下标赋值给 min 找到最大元素的下标赋值给 max 这样做的原因是因为最开始 left 是 0 right 是 size-1找到了最小和最大的元素后放在了首尾位置那么数组首尾位置就不用再遍历了而且刚好 left 递增了 1right 递减了 1如果找到了次大的元素和次小的元素时同样如此所以用 left 和 right 控制数组的区间刚好合适
找到最小元素的下标 min 时和首元素的下标 left 交换 找到最大元素的下标 max 时和尾元素的下标 right 交换 交换时需要注意一种情况因为是先把最小的元素交换到数组首元素的位置 当如果首元素就是最大的元素时就会出问题因为这时的 max 就在首元素的位置 但是已经把最小的元素交换到这里了而 max 的位置没有更新那么如果再交换最大元素和尾元素时就会发生错乱就会把最小的元素交换到尾元素去这样就不能实现升序了 改正的办法是判断 max 是否和 left 相同如果相同的话就更新 max 的位置 因为最开始 min 和 left 交换了所以此时最大的元素就在 min 处直接把 min 赋值给 max 即可
代码验证
