排序算法总结

冒泡排序与选择排序算法

选择排序

选择排序是一种简单直观的排序算法。
选择排序的基本步骤是：

首先，第一次从一个数组中选取最小值，与数组的第一个值arr[0]交换，，第二次从剩余的数组中选取最小值，与数组的第二个值交换，…..依次类推，重复以上步骤，总共是通过n-1次，这样就得到一个按排序码从小到大排列的有序序列。

说明：
选择排序一共有数组大小-1次的排序
每一轮的排序，又是一个循环，循环的规则代码
先假定当前的这个数是最小的，然后和后面的数依次比较，如果发现有比当前数更小的数，就重新确定最小数，并得到下标。
当遍历到数组的最后时，就得到本轮最小数和下标

Java 代码

/**
    * 选择排序方法
    * @param arr
    */
   public static void selectSort(int[] arr){
	
       int minIndex;
       int min;
       for (int i = 0; i<arr.length-1;i++){
           minIndex = i;
           min = arr[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;
           }
       }
	
	
   }

上述代码的执行顺序

首先是定义指向最小值的下标，以及最小值的变量，因为要经过n-1次的过程。

首先初始化最小值为第一个数组，最小值下标为0。在每一次中，把最小值和每一个元素进行比较，如果较小就更新最小值，并更新最小值的下标。在每一次的比较结束，进行位置交换。上述的n-1次按照这种方式依次进行比较。

冒泡排序

冒泡排序的基本思想是：通过对待排序序列从前向后遍历（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就像水底下的气泡一样，逐渐向上冒。。

因为在排序的过程中，各个元素不断的被移动到接近自己的位置，如果一趟比较下来，没有元素进行过交换，那就说明序列有序，因此在冒泡排序的过程中需要设置一个标志 flag 判断元素是否进行过交换，从而减少不必要的比较。

Java实现冒泡排序


public static void maopaoSort(int[] arr){

      int temp= 0;
      boolean flag = false;  //定义一个标志变量，来表示是否发生过交换，如果一趟比较发生过交换，则置为true

      for (int i=0;i<arr.length;i++){
          for (int j = 0;j<arr.length-1-i;j++){
              if (arr[j] > arr[j+1]){
                  flag = true;
                  temp = arr[j];
                  arr[j] = arr[j+1];
                  arr[j+1] = temp;
              }
          }
          if (!flag){
              break;
          }else {
              flag = false;
          }
      }
  }