数组排序(1) 冒泡排序

目录

       算法思想

       代码实现

       时间复杂度

算法思想：(以从小到大为例）

1. 从数组头部开始，不断比较相邻的两个元素，让较大的那个元素后移，直到数组的末尾。 经过第一轮的比较，就可以找到最大的元素，并将它移动到最后一个位置。
2. 从数组头部开始，不断比较相邻的两个元素，让较大的那个元素后移，直到与数组的倒数第二个元素比完。经过第二轮的比较，就可以找到第二大的元素，并将它移动到倒数第二个位置。
3. 以此类推，一共要找(n-1)次元素。（n为数组长度）

代码实现：（Java）

//从arr[0]开始比较
public void BubbleSort1(int arr[]) {
	if(arr!=null) {
		int length=arr.length;
		for(int i=0; i<length; i++) {
			for(int j=0; j<length-i-1; j++) {
				//从小到大排序
				if(arr[j]>arr[j+1]) {
					arr[j]*=arr[j+1];
					arr[j+1]=arr[j]/arr[j+1];
					arr[j]/=arr[j+1];
				}
				//从大到小排序
				/*if(arr[j]<arr[j+1]) {
					arr[j]*=arr[j+1];
					arr[j+1]=arr[j]/arr[j+1];
					arr[j]/=arr[j+1];
				}
				*/
			}
		}
		for(int i=0; i<length; i++) {
			System.out.println(arr[i]+" ");
		}
	}
}


//从arr[arr.length-1]开始比较
public void BubbleSort2(int arr[]) {
	if(arr!=null) {
		int length=arr.length;
		for(int i=length-1; i>0; i--) {
			for(int j=length-1; j>length-i-1; j--) {
				//从小到大排序
				if(arr[j]<arr[j-1]) {
					arr[j]*=arr[j-1];
					arr[j-1]=arr[j]/arr[j-1];
					arr[j]/=arr[j-1];
				}
				//从大到小排序
				/*if(arr[j]>arr[j-1]) {
					arr[j]*=arr[j-1];
					arr[j-1]=arr[j]/arr[j-1];
					arr[j]/=arr[j-1];
				}
				*/
			}
		}
		for(int i=0; i<length; i++) {
			System.out.println(arr[i]+" ");
		}
    }
}
           

时间复杂度：

外层for循环要循环执行（n-1）次，内层for循环最多的时候循环执行（n-1）次，最少的时候循环执行1次，一共执行

次

所以其时间复杂度为O(n^2)。