三种排序（冒泡，插入，选择）-- java实现和时间复杂度分析

文章目录

算法实现
算法分析
结论

算法实现

选择算法

遍历，找到最大值，最大值跟边边的值交换
遍历剩下的值，找到最大值，最大值跟边边的值交换
…
直至没东西遍历

package cn.edut.test_sort;

/** * 选择算法 * 1.遍历，找到最大值，最大值跟边边的值交换 * 2.遍历剩下的值，找到最大值，最大值跟边边的值交换 * ... * 3.直至没东西遍历 */
public class SelectingSort {
	public static void main(String[] args) {
		int a[]=new int[]
				{
						3,21,12,5,5,47,564,64,13,48,12,3,4,5,3,87,54,98
						};
		for(int i=0 ; i<a.length ; i++) {
			int maxIndex = i ;
			for(int x=i+1 ; x<a.length ; x++ ) {
				if(a[maxIndex]<a[x]) {
					maxIndex = x; 
				}
			}
			int temp = a[i] ; 
			a[i] = a[maxIndex] ;
			a[maxIndex] = temp;
		}
		
		for(int i=0 ; i<a.length ; i++) {
			System.out.print(a[i]+",");
		}
	}
}

插入算法

假设前第一位排好序
从第二位开始跟前一位对比，插入到正确的位置
从第三位开始跟前两位对比，插入到正确位置
…
从最后一位开始跟前面对比，插入到正确位置。。

package cn.edut.test_sort;

/** * 插入排序 * 1.假设前第一位排好序 * 2.从第二位开始跟前一位对比，插入到正确的位置 * 3.从第三位开始跟前两位对比，插入到正确位置 * ... * 4.从最后一位开始跟前面对比，插入到正确位置。。 * @author Administrator * */
public class InsertingSort {
	public static void main(String[] args) {
		int b[] = new int[]
				{
						2, 6, 45, 54, 6, 8, 9, 12, 45, 6546, 13, 134, 13, 156, 48, 2
						};
		
		for(int i=1 ; i<b.length ; i++) {
			for(int index=0; index<i; index++ ) {
				if(b[index]<b[i]) {
					int temp = b[i] ;
					b[i] = b[index];
					b[index] = temp;
				}
			}
		}
		
		for(int i=0 ;i<b.length ;i++) {
			System.out.print(b[i]+",");
		}
	}
}

冒泡算法

从左边第一位开始，向右比较
发现右边大的，左右调换
遍历n次后，左边为最大的
从左边第二位开始，向右比较
发现右边大的，左右调换
遍历n-1次后，左边为最大的
…
从左边第倒数二位开始，向右比较
发现右边大的，左右调换
遍历1次后，左边为最大的

package cn.edut.test_sort;


/** * 冒泡算法 * 1.从左边第一位开始，向右比较 * 2.发现右边大的，左右调换 * 3.遍历n次后，左边为最大的 * * 1.从左边第二位开始，向右比较 * 2.发现右边大的，左右调换 * 3.遍历n-1次后，左边为最大的 * ... * * * * 1.从左边第倒数二位开始，向右比较 * 2.发现右边大的，左右调换 * 3.遍历1次后，左边为最大的 * @author Administrator * */
public class BubblingSort {
	public static void main(String[] args) {
		 int a[] = new int[]
				 {
				 2, 6, 45, 54, 6, 8, 9, 12, 45, 6546, 13, 134, 13, 156, 48, 2
				 };
		 for(int i=0 ; i<a.length-1 ; i++) {
			 for(int x=i+1; x<a.length ; x++) {
				 if(a[i] -a[x]<0) {
					 int temp = a[i] ; 
					 a[i] = a[x] ; 
					 a[x] = temp;
				 }
			 }
		 }
		 for(int i=0 ; i<a.length ; i++) {
			 System.out.print(a[i]+",");
		 }
	}
}

算法分析

冒泡算法

先给出结论，冒泡算法的算法复杂度O(N²)
看代码，分析复杂度怎么得出来的

		 for(int i=0 ; i<a.length-1 ; i++) { //循环n-1次
			 for(int x=i+1; x<a.length ; x++) { //第一次循环n-1次，第二次循环n-2次。。。第n-1次循环1次
			
				 if(a[i] -a[x]<0) {
					 int temp = a[i] ; 
					 a[i] = a[x] ; 
					 a[x] = temp;
				 }
			 }
		 }

因此，总共循环了 $1 + 2 + 3 + . . . + (n - 1) = (n - 1 + 1) * (n - 1) / 2$ 次。
O(（n²-n）/2) = O(n²)
由此得出，冒泡算法的算法复杂度O(N²)。

插入算法

由下面分析可知，插入算法的复杂度也是O(N^2)。

for(int i=1 ; i<b.length ; i++) { //循环n-1次
			for(int index=0; index<i; index++ ) {
			//子循环次数分别为：1、2、3、...、n-1
				if(b[index]<b[i]) {
					int temp = b[i] ;
					b[i] = b[index];
					b[index] = temp;
				}
			}
		}

【看很多人说这是时间复杂度，还有一个空间复杂度。。emmm 好像好有道理，不过没学到那，就先这样】

选择算法

选择排序的时间复杂度仍然为O(N²)

for(int i=0 ; i<a.length ; i++) { // 循环n次
			int maxIndex = i ;
			for(int x=i+1 ; x<a.length ; x++ ) { 
			//分别循环 n-1、 n-2 、... 、1、 0次
				if(a[maxIndex]<a[x]) {
					maxIndex = x; 
				}
			}
			int temp = a[i] ; 
			a[i] = a[maxIndex] ;
			a[maxIndex] = temp;
		}

结论

三种算法的时间复杂度一样？