冒泡、选择排序

冒泡排序

介绍

基本思想: 冒泡排序，类似于水中冒泡，较大的数沉下去，较小的数慢慢冒起来

假设从小到大，即为较大的数慢慢往后排，较小的数慢慢往前排。

时间复杂度：O(n^2)
稳定度：稳定

思路

比较相邻的元素，如果前一个比后一个大，两数交换。
第一趟：第1个和第2个元素比较与交换，随后第2个和第3个比较交换…，直到将最大的数移动到最后一位。
第二趟将第二大的数移动至倒数第二位
直到最后一趟完成所有排序

实现

public void bubbleSort(int[] arr) {
	//临时变量
	int temp = 0;
	//总共进行 arr.length-1 排序
	for(int j = 0; j < arr.length -1; j++) {
		for(int i = 0;i < arr.length - j - 1) {
			//比较，大于则交换位置
			if(arr[i] > arr[i+1]) {
				temp = arr[i];
				arr[i] = arr[i+1];
				arr[i+1] = temp;
			}
		}
	}
}

优化

思考
假设要排序的数组为 45 23 21 71 63
第一轮 23 21 45 63 71
第二轮 21 23 45 63 71
第三轮 21 23 45 63 71
第四轮 21 23 45 63 71

发现：在第二轮的时候结果就已经出来了，第三轮的排序的时候就元素位置就不会发生改变，第四轮则非常多余
结论：在某一轮元素位置没有发生变化时，表示其就是有序的了

改进

public static void bubbleSort(int[] arr){
       //临时变量
       int temp = 0;
       //标识变量，表示是否进行过交换
       boolean flag = false;
       //总共进行 arr.length-1 轮排序
       for (int j = 0; j < arr.length-1; j++) {
           for (int i = 0;i < arr.length-j-1;i++) {
           	//比较，大于则交换位置
               if (arr[i]>arr[i+1]) {
                   flag = true;
                   temp = arr[i];
                   arr[i] = arr[i+1];
                   arr[i+1] = temp;
               }
           }
           if (!flag) {
               break;
           } else {
               //重置flag，用于下次判断
               flag = false;
           }
       }
   }

选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零

时间复杂度： O(n^2)
稳定度：不稳定

思路：

第一轮：在所有元素中选择出一个最小值，和第1个元素交换
第二轮：剩下的元素中找出一个最小值，和第2个元素交换（此时确定了第1个元素是最小值，不参与后面排序）
直到最后一趟完成所有排序

实现

public static void selectSort(int[] arr) {
       //记录最小值下标
      for (int i=0;i<arr.length - 1; i++) {
          //最小值
          int min = arr[i];
          //记录最小值下标
          int minIndex = i;
          for (int j = i+1;j<arr.length;j++) {
              if (min>arr[j]) {
                  min = arr[j];
                  minIndex = j;
              }
          }
          if (minIndex!=i) {
              arr[minIndex]=arr[i];
              arr[i] = min;
          }
      }
   }

冒泡和选择排序速度比较

随机生成 80000 个数字，比较排序时间

优化后的冒泡排序 vs 选择排序

/**
    * 测试一下冒泡排序的速度O(n^2),80000个数据
    */
   @Test
   public void testBubbleSort(){
       int[] arr = new int[80000];
       Random random = new Random();
       for (int i = 0;i<80000;i++) {
           arr[i] = random.nextInt();
       }
       long start = System.currentTimeMillis();
       bubbleSort(arr);
       long end = System.currentTimeMillis();
       System.out.println("80000个数据，冒泡排序所花时间："+(end-start));
   }
   
   /**
    * 测试一下选择排序的速度O(n^2),80000个数据
    */
   @Test
   public void testSelectSort() {
       int[] arr = new int[80000];
       Random random = new Random();
       for (int i = 0; i < 80000; i++) {
           arr[i] = random.nextInt();
       }
       long start = System.currentTimeMillis();
       selectSort(arr);
       long end = System.currentTimeMillis();
       System.out.println("80000个数据，选择排序所花时间：" + (end - start));
   }