数据结构之排序算法-简单排序算法(冒泡，选择，插入)

     昨天太忙了，没时间整理，今天一起发布，我们来看看笔试或者面试中经常涉及的几类排序算法，打冲锋

的是冒泡，选择和排序，我们统称为简单排序算法：

 

1.定义：

首先我们定义个样例数组：  

88，33，44，66，11

      

     冒泡排序：顾名思义，就是整个过程就行气泡一样往上升，具体思想就是从头开始，依次比较相邻的两个数，将小数放在前面，大数放在后边，直至比较最后两个数，重复以上过程直至最终完成排序： 

   

33，44，66，11 [88] 88 浮出 
33，44，11 [88 66] 66 浮出
 33，11[88 66 44] 40浮出 
11[88 66 44 33] ...... 
[88 66 44 33 11] 结束 

     代码实现：

 

public static void bubbleSort(int[] number) {
		
		//定义一个标志位，如果内循环没有发生交换，则表示有序，直接退出
		boolean flag = true;
		for (int i = 0; i < number.length - 1 && flag; i++) {
			flag = false;
			for (int j = 0; j < number.length - i - 1; j++) {
				if (number[j + 1] < number[j]) {
					swap(number, j + 1, j);
					flag = true;
				}
			}
		}
	}

	private static void swap(int[] number, int i, int j) {
		int temp;
		temp = number[i];
		number[i] = number[j];
		number[j] = temp;
	}

 

    选择排序：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。

 

[11]88，33，44，66选择出最小值11 
[11 33]88，44，66选择出最小值33 
[11 33 44]88，66 选择出最小值44
 [11 33 44 66]88...... 
[11 33 44 66 88]结束 

 

    代码实现：

 

public static void selectionSort(int[] number) {
		for (int i = 0; i < number.length - 1; i++) {
			int num = i;
			for (int j = i + 1; j < number.length; j++)
				if (number[j] < number[num])
					num = j;
			if (i != num)
				swap(number, i, num);
		}
	}
	
	private static void swap(int[] number, int i, int j) {
		int temp;
		temp = number[i];
		number[i] = number[j];
		number[j] = temp;
	}

 

   插入排序： 每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。

 

[33 88]44，66，11 將33插入88前 
[33 44 88]66，11 將44插入88前 
[33 44 66 88]11 將66插入88前 
[11 33 44 66 88]將11插入33前 

   代码实现: 

 

public static void insertionSort(int[] number) {
		for (int j = 1; j < number.length; j++) {
			int temp = number[j];
			int i = j - 1;
			while (temp < number[i]) {
				number[i + 1] = number[i];
				i--;
				if (i == -1)
					break;
			}
			number[i + 1] = temp;
		}
	}

  

   2.典型案例&&时间复杂度分析

 

int[] data = new int[100000];
		java.util.Random r = new java.util.Random();
		for (int i = 0; i < data.length; i++) {
			data[i] = r.nextInt(10000);
		}
		
		int[] insertionSortArrays =data.clone();
		int[] selectionSort =data.clone();
		
		long insertstarttime = System.currentTimeMillis();
		System.out.println("insertionSort start.....");
		InsertSortedTest.insertionSort(insertionSortArrays);
		long insertendtime = System.currentTimeMillis();
		System.out.println("insertionSort end.....");
		System.out.println("insertionSort total time : "
				+ (insertendtime - insertstarttime) / 1000 + "秒");

		long csstarttime = System.currentTimeMillis();
		System.out.println("selectionSort start.....");
		CsortedTest.selectionSort(selectionSort);
		long csendtime = System.currentTimeMillis();
		System.out.println("selectionSort end.....");
		System.out.println("selectionSort total time : "
				+ (csendtime - csstarttime) / 1000 + "秒");

		long bubblestarttime = System.currentTimeMillis();
		System.out.println("bubbleSort start...");
		MpsortTest.bubbleSort(data);
		long bubbleendtime = System.currentTimeMillis();
		System.out.println("bubbleSort end...");
		System.out.println("bubbleSort total time : "
				+ (bubbleendtime - bubblestarttime) / 1000 + "秒");

 

 

 

执行结果：

 

insertionSort start.....
insertionSort end.....
insertionSort total time : 15秒
selectionSort start.....
selectionSort end.....
selectionSort total time : 41秒
bubbleSort start...
bubbleSort end...
bubbleSort total time : 73秒

 

可以看到在数据量不是很大的时候，插入排序优于选择排序，选择排序优于冒泡排序：

 

分析：

冒泡排序：若数组或者序列是正序，一次扫描就可以完成操作，所以最好的的时间复杂度为O(n)，反之，如果是倒序，正序排序，则需要的时间复杂度为O(n²)
外部总循环X内部总循环)，平均时间复杂度为O(n²)。

选择排序：无论文件初始状态如何，在第j趟排序中选出最小关键字的记录，需做j-i次比较，因此，总的比较次数为：n(n-1)/2=0(n²)，择排序的平均时间复杂

度为O(n²)。

插入排序：平均时间复杂度为O(n)

 

评论

1 楼 snowolf 2010-04-14  

继续关注，等待算法集锦PDF收藏