算法笔记（一）冒泡排序

冒泡排序算法原理冒泡排序算法的原理如下：1.比较相邻元素。如果第一个大于第二个，则交换它们。2.对每一对相邻的元素做同样的事情，从开始的第一对到最后的最后一对。此时，最后一个元素应该是最大的数。3.对除最后一个元素之外的所有元素重复上述步骤。4.每次越来越少的元素不断重复上述步骤，直到没有一对数字可以比较。算法过程示例：sortint[]arr={10,5,9,3,6,8}从低到高：第一轮遍历：从0-arr.Length-1，取数组中最大的数,冒泡到最高位置。第二轮遍历：从0-arr.Length-2开始，把数组中第二大的数冒泡到第二高的位置。顺序遍历，从上到下依次确认位置。算法性能算法最佳时间最差时间平均时间额外空间气泡O(n)O(n2)O(n2)0/1Java代码publicclassBubbleSorting{publicstaticint[]BubbleSortingFunc(int[]arr){for(intcur=arr.length-1;cur>=0;cur--){for(inti=0;iarr[i+1])swap(arr,i,i+1);}}返回arr;}//交换数组中两个元素的位置，异或运算的性质，但i不等于jpublicstaticvoidswap(int[]arr,inti,intj){arr[i]=arr[i]^arr[j];arr[j]=arr[i]^arr[j];arr[i]=arr[i]^arr[j];}}