怎么申请免费的网站,线上营销的优势和劣势,做直播网站找哪家网站好,dedecms+wordpress什么是排序算法的稳定性#xff1f;
排序算法的稳定性#xff1a;
假定在待排序的记录序列中#xff0c;存在多个具有相同的关键字的记录#xff0c;若经过排序#xff0c;这些记录的相对次序保持不变#xff0c;即在原序列中#xff0c;r[i] r[j]#xff0c;且 r[i…什么是排序算法的稳定性
排序算法的稳定性
假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i] r[j]且 r[i] 在 r[j] 之前而在排序后的序列中r[i] 仍在 r[j] 之前则称这种排序算法是稳定的否则称为不稳定的。
以下以冒泡排序和选择排序作为比较分析排序算法的稳定性。
冒泡排序
一边比较一边向后两两交换将最大值 / 最小值冒泡到最后一位 经过优化的写法使用一个变量记录当前轮次的比较是否发生过交换如果没有发生交换表示已经有序不再继续排序 进一步优化的写法除了使用变量记录当前轮次是否发生交换外再使用一个变量记录上次发生交换的位置下一轮排序时到达上次交换的位置就停止比较。
public static void bubbleSort(int[] arr) {// 记录每轮冒泡是否发生了交换boolean swapped;for (int i 0; i arr.length - 1; i) {swapped false;for (int j 0; j arr.length - 1 - i; j) {if (arr[j] arr[j 1]) {swap(arr, j, j 1);swapped true;}}// 如果没有发生过交换直接退出循环if (!swapped) break;}
}
选择排序
选择排序的思想是双重循环遍历数组每经过一轮比较找到最小元素的下标将其交换至首位。
public static void selectionSort(int[] arr) {int minIndex;for (int i 0; i arr.length - 1; i) {minIndex i;for (int j i 1; j arr.length; j) {if (arr[minIndex] arr[j]) {// 记录最小值的下标minIndex j;}}// 将最小元素交换至首位int temp arr[i];arr[i] arr[minIndex];arr[minIndex] temp;}
}选择排序就好比第一个数字站在擂台上大吼一声“还有谁比我小”。剩余数字来挨个打擂如果出现比第一个数字小的数则新的擂主产生。每轮打擂结束都会找出一个最小的数将其交换至首位。经过 n-1 轮打擂所有的数字就按照从小到大排序完成了。
现在让我们思考一下冒泡排序和选择排序有什么异同
相同点
都是两层循环时间复杂度都为 O(n^2); 都只使用有限个变量空间复杂度 O(1)。 不同点
冒泡排序在比较过程中就不断交换而选择排序增加了一个变量保存最小值 / 最大值的下标遍历完成后才交换减少了交换次数。 事实上冒泡排序和选择排序还有一个非常重要的不同点那就是
冒泡排序法是稳定的选择排序法是不稳定的。
排序算法的稳定性有什么意义?
其实它只在一种情况下有意义当要排序的内容是一个对象的多个属性且其原本的顺序存在意义时如果我们需要在二次排序后保持原有排序的意义就需要使用到稳定性的算法。
举个例子如果我们要对一组商品排序商品存在两个属性价格和销量。当我们按照价格从高到低排序后要再按照销量对其排序这时如果要保证销量相同的商品仍保持价格从高到低的顺序就必须使用稳定性算法。
当然算法的稳定性与具体的实现有关。在修改比较的条件后稳定性排序算法可能会变成不稳定的。如冒泡算法中如果将「左边的数大于右边的数则交换」这个条件修改为「左边的数大于或等于右边的数则交换」冒泡算法就变得不稳定了。
同样地不稳定排序算法也可以经过修改达到稳定的效果。思考一下选择排序算法如何实现稳定排序呢
实现的方式有很多种这里给出一种最简单的思路新开一个数组将每轮找出的最小值依次添加到新数组中选择排序算法就变成稳定的了。
但如果将寻找最小值的比较条件由arr[minIndex] arr[j]修改为arr[minIndex] arr[j]即使新开一个数组选择排序算法依旧是不稳定的。所以分析算法的稳定性时需要结合具体的实现逻辑才能得出结论我们通常所说的算法稳定性是基于一般实现而言的。
