酒店网站报价方案,做网站算软件行业吗,关键词推广优化app,果洛电子商务网站建设哪家快冒泡排序#xff08;Bubble Sort#xff09;是一种典型的交换排序算法#xff0c;通过交换数据元素的位置进行排序。 一、算法基本思想 #xff08;1#xff09;基本思想 冒泡排序的基本思想就是#xff1a;从无序序列头部开始#xff0c;进行两两比较#xff0c;根据… 冒泡排序Bubble Sort是一种典型的交换排序算法通过交换数据元素的位置进行排序。 一、算法基本思想 1基本思想 冒泡排序的基本思想就是从无序序列头部开始进行两两比较根据大小交换位置直到最后将最大小的数据元素交换到了无序队列的队尾从而成为有序序列的一部分下一次继续这个过程直到所有数据元素都排好序。 算法的核心在于每次通过两两比较交换位置选出剩余无序序列里最大小的数据元素放到队尾。 2运行过程 冒泡排序算法的运作如下 1、比较相邻的元素。如果第一个比第二个大小就交换他们两个。 2、对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对。这步做完后最后的元素会是最大小的数。 3、针对所有的元素重复以上的步骤除了最后已经选出的元素有序。 4、持续每次对越来越少的元素无序元素重复上面的步骤直到没有任何一对数字需要比较则序列最终有序。 3示例 二、算法实现核心代码 C实现 void bubble_sort(int arr[], int len) {int i, j;for (i 0; i len - 1; i)for (j 0; j len - 1 - i; j)if (arr[j] arr[j 1])swap(arr[j], arr[j 1]);
} Java实现 public static void bubble_sort(int[] arr) {int i, j, temp, len arr.length;for (i 0; i len - 1; i)for (j 0; j len - 1 - i; j)if (arr[j] arr[j 1]) {temp arr[j];arr[j] arr[j 1];arr[j 1] temp;}
} 三、算法改进和变种 1设置标志变量change 标志变量用于记录每趟冒泡排序是否发生数据元素位置交换。如果没有发生交换说明序列已经有序了不必继续进行下去了。 void bubble_sort(int arr[], int len) {int i, j, change1;for (i 0; i len - 1 change!0; i){change0;for (j 0; j len - 1 - i; j)if (arr[j] arr[j 1]){swap(arr[j], arr[j 1]);change 1;}}
} 2鸡尾酒排序 鸡尾酒排序又叫定向冒泡排序搅拌排序、来回排序等是冒泡排序的一种变形。此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。 鸡尾酒排序在于排序过程是先从低到高然后从高到低而冒泡排序则仅从低到高去比较序列里的每个元素。它可以得到比冒泡排序稍微好一点的效能原因是冒泡排序只从一个方向进行比对由低到高每次循环只移动一个项目。 以序列(2,3,4,5,1)为例鸡尾酒排序只需要从低到高然后从高到低就可以完成排序但如果使用冒泡排序则需要四次。 但是在乱数序列的状态下鸡尾酒排序与冒泡排序的效率都很差劲。 void cocktail_sort(int arr[], int len) {int j, left 0, right len - 1;while (left right) {for (j left; j right; j)if (arr[j] arr[j 1])swap(arr[j], arr[j 1]);right--;for (j right; j left; j--)if (arr[j - 1] arr[j])swap(arr[j - 1], arr[j]);left;}
} 四、性能算法时间、空间复杂度、稳定性分析 1时间复杂度 在设置标志变量之后 当原始序列“正序”排列时冒泡排序总的比较次数为n-1移动次数为0也就是说冒泡排序在最好情况下的时间复杂度为O(n) 当原始序列“逆序”排序时冒泡排序总的比较次数为n(n-1)/2移动次数为3n(n-1)/2次所以冒泡排序在最坏情况下的时间复杂度为O(n^2) 当原始序列杂乱无序时冒泡排序的平均时间复杂度为O(n^2)。 2空间复杂度 冒泡排序排序过程中需要一个临时变量进行两两交换所需要的额外空间为1因此空间复杂度为O(1)。 3稳定性 冒泡排序在排序过程中元素两两交换时相同元素的前后顺序并没有改变所以冒泡排序是一种稳定排序算法。
