网站建设的发展目标,西湖区住房和城乡建设局网站,微信官方免费下载,广东建设信息网站首页6引言
虽然选择排序好用 #xff0c;但有点问题 也就是频繁找最大值下标 放到 未排序的后面 因为每次需要扫描整个未排序序列#xff0c;找到最大值或最小值的下标#xff0c;并将其交换到未排序序列的最后一个位置。这样做的问题在于#xff0c;在后面的迭代中#xff0c…引言
虽然选择排序好用 但有点问题 也就是频繁找最大值下标 放到 未排序的后面 因为每次需要扫描整个未排序序列找到最大值或最小值的下标并将其交换到未排序序列的最后一个位置。这样做的问题在于在后面的迭代中我们仍然需要扫描整个未排序序列包括已经排序好的部分这是浪费时间的。
另外选择排序是不稳定的排序算法因为在找到最大值或最小值的下标时并没有考虑值相同的元素的顺序。如果有多个相同值的元素交换它们的位置可能会打乱它们的相对顺序
也就是说 相同的元素也交换 可能位置有变化 对于相同的元素它们在排序后的位置可能会改变因为冒泡排序会将相邻的两个元素进行比较和交换这样相同的元素就可能会在排序过程中交换位置。对于选择排序而言它在找到最大值或最小值的下标时并没有考虑值相同的元素的顺序因此如果有多个相同值的元素交换它们的位置可能会打乱它们的相对顺序。因此选择排序也是不稳定的排序算法。
冒泡排序算法思想 到i2的时候 已经是排序了 那么这里应该如何优化 如果有一种机制 一开始默认已排序 在内层循环判断第一个比第二大发生交换的时候 制定为false 内层循环结束判断这个排序标志 为真排序完成直接退出外层循环
冒泡排序的基本思想是通过对待排序序列从前向后从下标较小的元素开始依次比较相邻元素的值若发现逆序则交换使值较大的元素逐渐从前移向后部就像水底的气泡一样逐渐向上冒。 在这个过程中每次内循环都会将当前未排序部分的最大元素“冒泡”到其最终位置。因此每次外循环之后未排序部分的元素数目会减少一个。
冒泡排序算法专区
// 定义一个名为bubbleSort的函数它接收两个参数一个名为arr的整数数组和一个名为size的整数表示数组的大小
void bubbleSort(int arr[], int size) { // 外层循环用于控制排序的轮数。因为每一轮都会将最大的元素移动到数组的末尾所以最多需要size-1轮。 for (int i 0; i size - 1; i) { // 内层循环用于在每一轮中逐一比较相邻的元素。由于每一轮都会确保最大的元素移动到其应在的位置因此内层循环只需要遍历到“size-1-i”即可。 for (int j 0; j size - 1 - i; j) { // 如果当前元素大于下一个元素则交换它们的位置。这是冒泡排序的核心操作。 if (arr[j] arr[j1]) { // 调用swap函数交换两个元素的值。swap(arr[j], arr[j1]); } } }
}
}优化
// 定义一个名为bubbleSort的函数接收一个整数数组arr和数组的大小size作为参数
void bubbleSort(int arr[], int size) { // 外层循环遍历整个数组 for (int i 0; i size - 1; i) { // 定义一个布尔变量swapped用于记录是否发生了交换 bool swapped false; // 用于记录是否发生了交换 // 内层循环比较相邻的元素并进行交换 for (int j 0; j size - 1 - i; j) { // 如果当前元素大于下一个元素则进行交换 if (arr[j] arr[j1]) { // 调用swap函数交换两个元素的值 swap(arr[j], arr[j1]); // 将swapped设为true表示发生了交换 swapped true; // 发生了交换将swapped设为true } } // 如果内层循环结束时swapped仍然为false说明数组已经是有序的直接退出外层循环 if (!swapped) break; // 如果内层循环结束时swapped仍然为false说明数组已经是有序的直接退出外层循环 }
}升/降 序通用
// 定义一个函数 BubbleSort接受一个整数数组 arr数组的大小 size和一个比较函数 cmp 作为参数。这个函数用来对数组进行冒泡排序。
void BubbleSort(int arr[], int size, bool(*cmp)(const int, const int)) { // 检查传入的比较函数是否为空。如果为空则直接返回不进行任何操作。 if (cmp nullptr) { return; } // 开始进行外层循环从数组的第一个元素到倒数第二个元素i 从 0 到 size-2 for (int i 0; i size-1; i){ // 定义一个布尔变量 IsSort初始值为 true。这个变量用来检查数组是否已经有序。 bool IsSort true; // 进行内层循环从数组的第二个元素开始到倒数第三个元素j 从 0 到 size-1-i for (int j 0; j size-1-i; j){ // 使用比较函数 cmp 来判断 arr[j] 是否大于 arr[j 1]。如果大于则交换这两个元素的位置并将 IsSort 设为 false。 if (cmp(arr[j], arr[j 1])) { swap(arr[j], arr[j 1]); IsSort false; } } // 如果 IsSort 仍然为 true说明这个位置的元素已经是有序的可以结束内层循环。 if (IsSort) { break; } }
} // 定义一个函数 GreaterCmp接受两个整数作为参数如果第一个整数大于第二个整数返回 true否则返回 false。这个函数用于比较两个整数的大小。
bool GreaterCmp(const int val1, const int val2) { return val1 val2;
} // 定义一个函数 LessCmp接受两个整数作为参数如果第一个整数小于第二个整数返回 true否则返回 false。这个函数用于比较两个整数的大小。
bool LessCmp(const int val1, const int val2) { return val1 val2;
}
