常用排序算法

一. 冒泡排序(BubbleSort)

• 基本思想：两个数比较大小，较大的数下沉，较小的数冒起来。

• 过程：

  • 比较相邻的两个数据，如果第二个数小，就交换位置。

  • 从后向前两两比较，一直到比较最前两个数据。最终最小数被交换到起始的位置，这样第一个最小数的位置就排好了。

  • 继续重复上述过程，依次将第2.3...n-1个最小数排好位置。
    [图片上传失败...(image-3d843-1583594594035)]

    冒泡排序

• 平均时间复杂度：O(n2)

• java代码实现：

  实例

冒泡.png

public static void BubbleSort(int [] arr){

     int temp;//临时变量
     for(int i=0; i<arr.length-1; i++){   //表示趟数，一共arr.length-1次。
         for(int j=arr.length-1; j>i; j--){

             if(arr[j] < arr[j-1]){
                 temp = arr[j];
                 arr[j] = arr[j-1];
                 arr[j-1] = temp;
             }
         }
     }
 }

• 优化：

  • 针对问题：
    数据的顺序排好之后，冒泡算法仍然会继续进行下一轮的比较，直到arr.length-1次，后面的比较没有意义的。

  • 方案：
    设置标志位flag，如果发生了交换flag设置为true；如果没有交换就设置为false。
    这样当一轮比较结束后如果flag仍为false，即：这一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去。

    实例

    public static void BubbleSort1(int [] arr){

    int temp;//临时变量
    boolean flag;//是否交换的标志
    for(int i=0; i<arr.length-1; i++){ //表示趟数，一共 arr.length-1 次

       // 每次遍历标志位都要先置为false，才能判断后面的元素是否发生了交换
       flag = false;
    
       for(int j=arr.length-1; j>i; j--){ //选出该趟排序的最大值往后移动
    
           if(arr[j] < arr[j-1]){
               temp = arr[j];
               arr[j] = arr[j-1];
               arr[j-1] = temp;
               flag = true;    //只要有发生了交换，flag就置为true
           }
       }
       // 判断标志位是否为false，如果为false，说明后面的元素已经有序，就直接return
       if(!flag) break;
    

    }
    }

二. 选择排序(SelctionSort)

• 基本思想：
  在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；
  第二次遍历n-2个数，找到最小的数值与第二个元素交换；
  。。。
  第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。

• 过程：

选择.png

选择排序

• 平均时间复杂度：O(n2)

• java代码实现：

  实例

  public static void select_sort(int array[],int lenth){

  for(int i=0;i<lenth-1;i++){

     int minIndex = i;
     for(int j=i+1;j<lenth;j++){
        if(array[j]<array[minIndex]){
            minIndex = j;
        }
     }
     if(minIndex != i){
         int temp = array[i];
         array[i] = array[minIndex];
         array[minIndex] = temp;
     }
  

  }
  }