怎么查网站备案的公司,树莓派安装wordpress,少女大人免费观看高清电视剧韩剧,开发网站建设方案冒泡排序就这么简单在我大一的时候自学c语言和数据结构#xff0c;我当时就接触到了冒泡排序(当时使用的是C语言编写的)。现在大三了#xff0c;想要在暑假找到一份实习的工作#xff0c;又要回顾一下数据结构与算法的知识点了。排序对我们来说是一点也不陌生了#xff0c;…冒泡排序就这么简单在我大一的时候自学c语言和数据结构我当时就接触到了冒泡排序(当时使用的是C语言编写的)。现在大三了想要在暑假找到一份实习的工作又要回顾一下数据结构与算法的知识点了。排序对我们来说是一点也不陌生了当你打王者荣耀的时候也会有段位之分当你打Dota的时候也有天梯分。从高往下数这个排名是有规律的就是一种排序。我最开始接触的就是冒泡排序所以这篇博文主要讲的是冒泡排序。冒泡排序的实现来源百度百科冒泡排序(Bubble Sort台湾译为泡沫排序或气泡排序)是一种简单的排序算法。它重复地走访过要排序的数列一次比较两个元素如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换也就是说该数列已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端故名。算法描述i从0开始i与i1比较如果ii1那么就互换i不断增加直到i从最简单开始首先我们创建一个数组该数组有5位数字int[] arrays {2, 5, 1, 3, 4};一、第一趟排序下面我们根据算法的描述来进行代码验算 (第一趟排序)//使用临时变量让两个数互换int temp;//第一位和第二位比if (arrays[0] arrays[1]) {//交换temp arrays[0];arrays[0] arrays[1];arrays[1] temp;}//第二位和第三位比if (arrays[1] arrays[2]) {temp arrays[1];arrays[1] arrays[2];arrays[2] temp;}//第三位和第四位比if (arrays[2] arrays[3]) {temp arrays[2];arrays[2] arrays[3];arrays[3] temp;}//第四位和第五位比if (arrays[3] arrays[4]) {temp arrays[3];arrays[3] arrays[4];arrays[4] temp;}如果前一位的数比后一位的数要大那么就交换直到将数组的所有元素都比较了一遍经过我们第一趟比较我们可以发现最大的值就在数组的末尾了!一、第二趟排序第二趟排序跟第一趟排序一样也是用前一位与后一位比较如果前一位比后一位要大那就交换。值得注意的是并不需要与最后一位比较了因为在第一趟排序完了最后一位已经是最大的数了。同理我们第二趟排序完了之后倒数第二位也是第二大的数了。第二趟排序的代码如下//第一位和第二位比if (arrays[0] arrays[1]) {//交换temp arrays[0];arrays[0] arrays[1];arrays[1] temp;}//第二位和第三位比if (arrays[1] arrays[2]) {temp arrays[1];arrays[1] arrays[2];arrays[2] temp;}//第三位和第四位比if (arrays[2] arrays[3]) {temp arrays[2];arrays[2] arrays[3];arrays[3] temp;}//第四位不需要和第五位比了因为在第一趟排序结束后第五位是最大的了。结果我们的第二大数已经排在了倒数第二位了三、代码简化值得说明的是上面的结果看起来已经是排序好的了其实是我在测试时数据还不足够乱如果数据足够乱的话是需要4(n-1)趟排序的但我们从上面的代码就可以发现第一趟和第二趟的比较、交换代码都是重复的并且我们的比较都是写死的(0,1,2,3,4)并不通用我们的数组有5位数字第一趟需要比较4次第二趟需要比较3次我们可以根据上面规律推断出第三趟需要比较2次第四躺需要比较1次再从上面的规律可以总结出5位数的数组需要4躺排序的每躺排序之后次数减1(因为前一趟已经把前一趟数的最大值确定下来了)于是我们可以根据for循环和变量将上面的代码进行简化int temp;//外层循环是排序的趟数for (int i 0; i arrays.length - 1 ; i) {//内层循环是当前趟数需要比较的次数for (int j 0; j arrays.length - i - 1; j) {//前一位与后一位与前一位比较如果前一位比后一位要大那么交换if (arrays[j] arrays[j 1]) {temp arrays[j];arrays[j] arrays[j 1];arrays[j 1] temp;}}}四、冒泡排序优化从上面的例子我们可以看出来如果数据足够乱的情况下是需要经过4躺比较才能将数组完整排好序。但是我们在第二躺比较后就已经得到排好序的数组了。但是我们的程序在第二趟排序后仍会执行第三趟、第四趟排序。这是没有必要的因此我们可以对其进行优化一下如果在某躺排序中没有发生交换位置那么我们可以认为该数组已经排好序了。这也不难理解因为我们每趟排序的目的就是将当前趟最大的数置换到对应的位置上没有发生置换说明就已经排好序了。代码如下//装载临时变量int temp;//记录是否发生了置换 0 表示没有发生置换、 1 表示发生了置换int isChange;//外层循环是排序的趟数for (int i 0; i arrays.length - 1; i) {//每比较一趟就重新初始化为0isChange 0;//内层循环是当前趟数需要比较的次数for (int j 0; j arrays.length - i - 1; j) {//前一位与后一位与前一位比较如果前一位比后一位要大那么交换if (arrays[j] arrays[j 1]) {temp arrays[j];arrays[j] arrays[j 1];arrays[j 1] temp;//如果进到这里面了说明发生置换了isChange 1;}}//如果比较完一趟没有发生置换那么说明已经排好序了不需要再执行下去了if (isChange 0) {break;}}五、扩展阅读C语言实现第一种方式:void bubble ( int arr[], int n){int i;int temp;for (i 0; i n - 1; i) {if (arr[i] arr[i 1]) {temp arr[i];arr[i] arr[i 1];arr[i 1] temp;}}}void bubbleSort ( int arr[], int n){int i;for (i n; i 1; i--) {bubble(arr, i);}}C语言实现第二种方式递归:void bubble ( int arr[], int L, int R){if (L R) ;else {int i;for (i L; i R - 1; i)//i只能到达R-1if (arr[i] arr[i 1]) {int temp arr[i];arr[i] arr[i 1];arr[i 1] temp;}bubble(arr, L, R - 1);//第一轮已排好R}}测试代码:int main (){int arr[] {2, 3, 4, 511, 66, 777, 444, 555, 9999};bubbleSort(arr, 8);for (int i 0; i 9; i)cout arr[i] endl;return 0;}5.1时间复杂度的理解如果文章有错的地方欢迎指正大家互相交流。习惯在微信看技术文章想要获取更多的Java资源的同学可以关注微信公众号:Java3y
