广州康体设备网站建设,删除wordpress主题字体载入,网站设置关键词,来年做啥网站能致富排序算法稳定性假定在待排序的记录序列中#xff0c;存在多个具有相同的关键字的记录#xff0c;若经过排序#xff0c;这些记录的相对次序保持不变#xff0c;即在原序列中#xff0c;r[i]r[j]#xff0c;且r[i]在r[j]之前#xff0c;而在排序后的序列中#xff0c;r[…排序算法稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。冒泡排序bubble sort列表中每相邻的两个数进行比较如果前面比后面大则交换这两个数。一趟排序完成后无序区减少了一个数有序区增加了一个数。代码关键点总趟数n-1每一趟无序区范围,每一趟下标最大值为(n-i-1)代码关键点分析总趟数n-1无序列表arr[n] {val0, val1, ..., val(n-1)};n 1时即无序列表只有1个元素只要进行比较0趟n 2 时即无序列表有2个元素只要进行比较1趟n 3 时即无序列表有3个元素只要进行比较2趟n n 时即无序列表有n个元素只要进行比较 n - 1 趟每一趟下标最大值为(n-i-1)n 3 时即无序列表有3个元素只要进行比较2趟趟数从0开始那么第0趟下标的最大值为n-i-1即3-0-1 2代码#include iostreamusing namespace std;templatetypename T
void bubble_sort(T *arr, int n)
{T temp;bool exchange;for (int i 0; i n-1; i) //总趟数n-1{exchange false;for (int j 0; j n-i-1; j) //每一趟下标最大值即j1这个下标的最大值为n-i-1{if (arr[j] arr[j1]){temp arr[j];arr[j] arr[j1];arr[j1] temp;exchange true;}}if (!exchange) //一趟中没有发生任何元素的交换说明列表已排好序break;}
}int main(int argc, char *argv[])
{int arr[] {3,5,2,1,4};int n sizeof(arr)/sizeof(*arr);cout ---before bubble sort--- endl;for (int i 0; i n; i){cout arr[i] ;}cout endl;bubble_sort(arr, n);cout ---after bubble sort--- endl;for (int i 0; i n; i){cout arr[i] ;}cout endl;return 0;
}结果时间复杂度O()因为冒泡排序算法外循环对总趟数进行循环内循环对每一趟进行循环所以算法时间复杂度为O()算法稳定性:稳定冒泡排序算法原无序列表中r[i]r[j]且r[i]在r[j]之前而在排序后的有序列表中r[i]仍在r[j]之前所以冒泡排序算法是稳定的。ending
