冒泡排序

基本思想：两个数比较大小，较大的向下沉，较小的向上冒出来
过程：

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

image.png
时间复杂度为：O(n^2)

  1. public static void BubbleSort1(int [] arr){
  3.    int temp;//临时变量
  4.    boolean flag;//是否交换的标志
  5.    for(int i=0; i<arr.length-1; i++){   //表示趟数，一共 arr.length-1 次
  7.        // 每次遍历标志位都要先置为false，才能判断后面的元素是否发生了交换
  8.        flag = false;
  10.        for(int j=arr.length-1; j>i; j--){ //选出该趟排序的最大值往后移动
  12.            if(arr[j] < arr[j-1]){
  13.                temp = arr[j];
  14.                arr[j] = arr[j-1];
  15.                arr[j-1] = temp;
  16.                flag = true;    //只要有发生了交换，flag就置为true
  17.            }
  18.        }
  19.        // 判断标志位是否为false，如果为false，说明后面的元素已经有序，就直接return
  20.        if(!flag) break;
  21.    }
  22. }

选择排序

基本思想：在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；
第二次遍历n-2个数，找到最小的数值与第二个元素交换；
。。。
第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。
image.png
时间复杂度：O(n^2)

  1. public static void select_sort(int array[],int lenth){
  3.    for(int i=0;i<lenth-1;i++){
  5.        int minIndex = i;
  6.        for(int j=i+1;j<lenth;j++){
  7.           if(array[j]<array[minIndex]){
  8.               minIndex = j;
  9.           }
  10.        }
  11.        if(minIndex != i){
  12.            int temp = array[i];
  13.            array[i] = array[minIndex];
  14.            array[minIndex] = temp;
  15.        }
  16.    }
  17. }