常用排序算法(冒泡,选择,插入)

排序算法及其优化

1.冒泡算法

原算法

• 时间复杂度: O(n^2)

• 空间复杂度: O(1)

• 稳定性 :稳定

• 排序思想 : 每趟排序将从头开始两两比较,按照大的在后小的在前的顺序进行交换,每趟可以确定最大的数在数组的末尾,需要遍历N趟,每次遍历(N-i)次.

  ​

   public static <T extends Comparable<T>> void bubbleSort(T[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j].compareTo(arr[j + 1]) > 0) {
                    swap(arr, j, j + 1);
                }
            }
        }
    }
    private static <T> void swap(T[] arr, int x, int y) {
        T temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }

优化算法

• 优化思想 : 能在一定程度上减少遍历次数 , 给每趟遍历设定一个flag = false, 如果在本趟遍历中发生了交换,则将flag 置为 true , 如果本趟遍历flag 一直为false ,则说明本趟没有发生交换,则证明数组已经有序了,直接退出,

  ​

    public static <T extends Comparable<T>> void bubbleSort(T[] arr) {
          for (int i = 0; i < arr.length - 1; i++) {
              boolean flag = false ; 
              for (int j = 0; j < arr.length - 1 - i; j++) {
                  if (arr[j].compareTo(arr[j + 1]) > 0) {
                      swap(arr, j, j + 1);
                      flag = true ; 
                  }
              }
              if(!flag){
                  return ; 
              }
          }
      }
      private static <T> void swap(T[] arr, int x, int y) {
          T temp = arr[x];
          arr[x] = arr[y];
          arr[y] = temp;
      }
  
  

2.选择排序

原算法

• 时间复杂度 : O(n^2) 最好情况为原本数组为递增,只需遍历一趟 : O(n)
• 空间复杂度 : O(1)
• 算法思想 : 和冒泡类似,只不过每趟选择的是数组元素中最小的值与每趟排序的最开始的元素交换,同样需要遍历N趟,而每趟遍历数组元素N-1个.

   public static <T extends Comparable<T>> void selectSort(T []arr){
        for (int i = 0; i <arr.length-1 ; i++) {
               int minIndex = i ;
            for (int j = i+1; j <arr.length-1 ; j++) {
                if(arr[minIndex].compareTo(arr[j]) > 0 ){
                    minIndex = j ;
                }
            }
            swap(arr,i,minIndex);
        }
    }
    private static <T> void swap(T[] arr, int x, int y) {
        T temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }

优化算法

• 时间复杂度 : O(n^2)

• 空间复杂度 : O(n^2)

• 优化思想 : 每次在内循环中可以将最大值和最小值同时得出,可以将其同时赋值给数组首尾

   public static <T extends Comparable<T>> void selectSort(T[] arr) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            int minIndex = left;
            int maxIndex = right;
            for (int i = left; i <= right; i++) {
                if (arr[minIndex].compareTo(arr[i]) > 0) {
                    minIndex = i;    // 获取每趟排序的最小值的index
                }
                if (arr[maxIndex].compareTo(arr[i]) < 0) {
                    maxIndex = i;  // 获取每趟排序的最大值的index 
                }
            }
            if (left != minIndex) {
                swap(arr, left, minIndex);
                left++;
            }
            swap(arr, right, maxIndex);
            right--;
        }
    }

    private static <T> void swap(T[] arr, int x, int y) {
        T temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }

3. 简单插入排序算法

原算法

• 时间复杂度 : O(n^2)
• 空间复杂度 : O(1)
• 稳定性 : 稳定
• 算法思想 : 每趟排序在为排序序列找出和小于已排序序列的数然后将这个数以及之后的向后移动一位,然后对空位赋值,首先以 Index = 1为第一个值,用temp 保存其值,判断之前的已排序序列如果大于当前值,就将其后移,找的temp的合适的位置,然后再将其插入.

 public static <T extends Comparable<T>> void insertSort(T arr[]) {
        int j = 0;
        for (int i = 1; i < arr.length - 1; i++) { // 从第二位开始
           int j = i ; 
           while(j != 0  && arr[j].compareTo(arr[j-1]) > 0 ){
					swap(arr[j],arr[j-1]);
					j--;
				}
        }
    }

优化算法

插入排序的优化算法为希尔排序,是第一个突破时间复杂度O(n^2) ,时间复杂度可以达到O(n^1.3) ~ O(n^1.5)