排序

选择排序

  • 时间复杂度(O(N^2))

在 N个数中 遍历N-1次 找到最小的数字和第一个数字交换
在便利N-2个中找到最小的数字和第二个数字交换
循环往复 直到N个数遍历完成

  1. package algorithm;
  3. import java.util.Arrays;
  5. public class selectSort {
  6.     // 选择排序 第i个位置存放第i位序列
  7.     public static int tempSize = 20; // 测试多少组数据的长度
  8.     public static int tempValue = 30; // 数据的值在哪个范围
  9.     public static int tempTime = 100; // 比较多少组数据
  11.     public static void selectSort(int[] arr) {
  12.         if (arr == null) {
  13.             return;
  14.         }
  16.         for (int i = 0; i < arr.length; i++) { // 循环次数
  17.             int minValue = i; // 比较值
  18.             for (int j = i + 1; j < arr.length; j++) {
  19.                 if (arr[minValue] > arr[j]) {
  20.                     minValue = j;
  21.                 }
  22.             }
  23.             swap(arr, i, minValue);
  24.         }
  25.     }
  27.     public static void swap(int[] arr, int i, int j) {
  28.         int temp = arr[i];
  29.         arr[i] = arr[j];
  30.         arr[j] = temp;
  31.     }
  33.     public static void sort(int[] arr) {
  34.         Arrays.sort(arr);
  35.     }
  37.     public static boolean isEqual(int[] arr, int[] arr2) {
  38.         if ((arr == null && arr2 != null) || (arr != null && arr2 == null)) {
  39.             return false;
  40.         }
  41.         if (arr == null) {
  42.             return true;
  43.         }
  44.         if (arr.length != arr2.length) {
  45.             return false;
  46.         }
  47.         for (int i = 0; i < arr.length; i++) {
  48.             if (arr[i] != arr2[i]) {
  49.                 return false;
  50.             }
  51.         }
  52.         return true;
  53.     }
  55.     public static int[] generator(int size, int value) {
  56.         int[] arr = new int[(int) ((Math.random() + 1) * size)];
  57.         for (int i = 0; i < size; i++) {
  58.             //            [-value,value]
  59.             arr[i] = ((int) (Math.random() * (value + 1)) - (int) (Math.random() * value));
  60.         }
  61.         return arr;
  62.     }
  64.     // 拷贝数组
  65.     public static int[] copyArray(int[] array) {
  66.         // 引用数据类型 都可以为null
  67.         if (array == null) {
  68.             return null;
  69.         }
  70.         int[] tempArray = new int[array.length];
  71.         for (int i = 0; i < array.length; i++) {
  72.             tempArray[i] = array[i];
  73.         }
  74.         return tempArray;
  75.     }
  77.     public static void printf(int[] a, int[] b, int[] c) {
  78.         for (int i = 0; i < a.length; i++) {
  79.             System.out.println("排序值,sort值,初始值");
  80.             System.out.printf("%d,%d,%d", a[i], b[i], c[i]);
  81.             System.out.println();
  82.         }
  83.     }
  85.     public static void main(String[] args) {
  86.         for (int i = 0; i < tempTime; i++) {
  87.             int[] arr = generator(tempSize, tempValue);
  88.             int[] arr1 = copyArray(arr);
  89.             int[] arr2 = copyArray(arr);
  90.             selectSort(arr1);
  91.             sort(arr2);
  92.             if (!isEqual(arr1, arr2)) {
  93.                 printf(arr1, arr2, arr);
  94.                 return;
  95.             }
  96.         }
  97.         System.out.println("ok");
  98.     }
  99. }

冒泡排序

  • 时间复杂度O(N^2)

比较两个相邻的数字的结果 判断是否要交换顺序 (一轮下来的时间复杂度是O(N))
以此重复 知道所有排序完成 

  1. package algorithm;
  3. import java.util.Arrays;
  5. public class bubblingSort {
  6.     //  冒泡排序
  7.     public static int tempSize = 20; // 测试多少组数据的长度
  8.     public static int tempValue = 10; // 数据的值在哪个范围
  9.     public static int tempTime = 50; // 比较多少组数据
  11.     // 比较两个相邻的元素，将值大的元素交换到右边
  12.     // 时间复杂度O(n^2)
  13.     public static void bubblingSort(int[] arr) {
  14.         if (arr == null || arr.length < 2) { // 注意边界问题
  15.             return;
  16.         }
  17.         for (int i = 0; i < arr.length - 1; i++) { // 循环次数
  18.             // 每次循环都会确定i+1个排序 所以要 arr.length - (i + 1)
  19.             // 注意这里的arr.length - i -1
  20.             for (int j = 0; j < arr.length - i - 1; j++) {
  21.                 // 这里的
  22.                 if (arr[j] > arr[j + 1]) {
  23.                     swap(arr, j, j + 1);
  24.                 }
  25.             }
  26.         }
  27.     }
  29.     public static void sort(int[] arr) {
  30.         Arrays.sort(arr);
  31.     }
  33.     // 交换顺序
  34.     public static void swap(int[] arr, int i, int j) {
  35.         int temp = arr[i];
  36.         arr[i] = arr[j];
  37.         arr[j] = temp;
  38.     }
  40.     // 生成随机数组
  41.     public static int[] generateRandomArray(int size, int value) {
  42.         // 生成size长度的数组 并且值在 [0-value - 1] 之间
  43.         int[] array = new int[(int) ((Math.random() + 1) * size)];
  44.         for (int i = 0; i < array.length; i++) {
  45.             array[i] = (int) (Math.random() * value);
  46.         }
  47.         return array;
  48.     }
  50.     // 拷贝数组
  51.     public static int[] copyArray(int[] array) {
  52.         // 引用数据类型 都可以为null
  53.         if (array == null) {
  54.             return null;
  55.         }
  56.         int[] tempArray = new int[array.length];
  57.         for (int i = 0; i < array.length; i++) {
  58.             tempArray[i] = array[i];
  59.         }
  60.         return tempArray;
  61.     }
  63.     public static boolean isEqual(int[] arr, int[] rightArray) {
  64.         if (arr == null && rightArray != null || arr != null && rightArray == null) {
  65.             return false;
  66.         }
  67.         if (arr == null) {
  68.             return true;
  69.         }
  70.         if (arr.length != rightArray.length) {
  71.             return false;
  72.         }
  73.         for (int i = 0; i < arr.length; i++) {
  74.             if (arr[i] != rightArray[i]) {
  75.                 return false;
  76.             }
  77.         }
  78.         return true;
  79.     }
  81.     public static void printf(int[] a, int[] b, int[] c) {
  82.         for (int i = 0; i < a.length; i++) {
  83.             System.out.println("排序值,sort值,初始值");
  84.             System.out.printf("%d,%d,%d", a[i], b[i], c[i]);
  85.             System.out.println();
  86.         }
  87.     }
  89.     public static void main(String[] args) {
  90.         for (int i = 0; i < tempTime; i++) {
  91.             int[] arr = generateRandomArray(tempSize, tempValue); // 第一组数据
  92.             int[] rightArray = copyArray(arr); // 拷贝一组数组 用于比较
  93.             int[] tempArray = copyArray(arr); // 拷贝一组数组 用于比较
  94.             bubblingSort(arr);
  95.             sort(rightArray);
  96.             // 比较是否两个相等
  97.             if (!isEqual(arr, rightArray)) {
  98.                 printf(arr, rightArray, tempArray);
  99.                 return;
  100.             }
  101.         }
  102.         System.out.println("ok");
  103.     }
  104. }

插入排序

  • 时间复杂度O(N^2)

    将第i位的元素插入到前0- (i-1) 中去 ```java package algorithm;

import java.util.Arrays;

public class insertSort { // 插入排序 i>=1 从小到大 // 将第i位的元素插入到前0- (i-1) 中去 public static int tempSize = 20; // 测试多少组数据的长度 public static int tempValue = 100; // 数据的值在哪个范围 public static int tempTime = 1000; // 比较多少组数据

  1. // 时间复杂度O(n^2)
  2. public static void insertSort(int[] arr) {
  3.     if (arr == null || arr.length < 2) { // 注意边界问题
  4.         return;
  5.     }
  6.     for (int i = 1; i < arr.length; i++) {
  7.         for (int j = 0; j < i; j++) {
  8.             if (arr[j] > arr[i]) {
  9.                 // 往后移动一位
  10.                 move(arr, j, i);
  11.             }
  12.         }
  13.     }
  15. }
  17. public static void sort(int[] arr) {
  18.     Arrays.sort(arr);
  19. }
  21. // 插入 往后位移 从i到j位往后移
  22. public static void move(int[] arr, int i, int j) {
  23.     // 数据移动是从 [i,j)
  24.     int tampValue = arr[j];
  25.     for (int k = j - 1; k >= i; k--) {
  26.         arr[k + 1] = arr[k];
  27.     }
  28.     arr[i] = tampValue;
  29. }
  31. // 生成随机数组
  32. public static int[] generateRandomArray(int size, int value) {
  33.     // 生成size长度的数组 并且值在 [0-value - 1] 之间
  34.     int[] array = new int[(int) ((Math.random() + 1) * size)];
  35.     for (int i = 0; i < array.length; i++) {
  36.         array[i] = (int) (Math.random() * value);
  37.     }
  38.     return array;
  39. }
  41. // 拷贝数组
  42. public static int[] copyArray(int[] array) {
  43.     // 引用数据类型 都可以为null
  44.     if (array == null) {
  45.         return null;
  46.     }
  47.     int[] tempArray = new int[array.length];
  48.     for (int i = 0; i < array.length; i++) {
  49.         tempArray[i] = array[i];
  50.     }
  51.     return tempArray;
  52. }
  54. public static boolean isEqual(int[] arr, int[] rightArray) {
  55.     if (arr == null && rightArray != null || arr != null && rightArray == null) {
  56.         return false;
  57.     }
  58.     if (arr == null) {
  59.         return true;
  60.     }
  61.     if (arr.length != rightArray.length) {
  62.         return false;
  63.     }
  64.     for (int i = 0; i < arr.length; i++) {
  65.         if (arr[i] != rightArray[i]) {
  66.             return false;
  67.         }
  68.     }
  69.     return true;
  70. }
  72. public static void printf(int[] a, int[] b, int[] c) {
  73.     for (int i = 0; i < a.length; i++) {
  74.         System.out.println("排序值,sort值,初始值");
  75.         System.out.printf("%d,%d,%d", a[i], b[i], c[i]);
  76.         System.out.println();
  77.     }
  78. }
  80. public static void main(String[] args) {
  81.     for (int i = 0; i < tempTime; i++) {
  82.         int[] arr = generateRandomArray(tempSize, tempValue); // 第一组数据
  83.         int[] rightArray = copyArray(arr); // 拷贝一组数组 用于比较
  84.         int[] tempArray = copyArray(arr); // 拷贝一组数组 用于比较
  85.         insertSort(arr);
  86.         sort(rightArray);
  87.         // 比较是否两个相等
  88.         if (!isEqual(arr, rightArray)) {
  89.             printf(arr, rightArray, tempArray);
  90.             return;
  91.         }
  92.     }
  93.     System.out.println("ok");
  94. }

}

<a name="W5egR"></a>
# 快速排序
```java
import java.util.Arrays;

public class quickSort {
    /**
     * 快速排序
     * 时间复杂度nlogn
     * @param arr
     * @desc 选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分；
     * 其中一部分的所有数据都比另外一部分的所有数据都要小。然后，再按此方法对这两部分数据分别进行快速排序，
     * 整个排序过程可以递归进行，以此达到整个数据变成有序序列。
     */
    public static void quickSort(int[] arr) {
        if(arr == null || arr.length < 2) return;
        int pre = 0; //左边界
        int next = arr.length -1; //右边界
        quickSortStack(arr,pre,next);
    }
    public static void quickSortStack(int[] arr,int i, int j) {
        if(i >= j) return;
        int current = arr[i]; //基准值
        // 保存边界值
        int pre = i;
        int next = j;
        while(pre < next) {
            // 如果 next的值比当前的值大 则继续往下查找
            while(pre < next && arr[next] >= current) {
                next--;
            }
            // 这里会走 arr[next] < current 交换顺序
            if(pre < next) {
                arr[pre] = arr[next];
                //之后往pre向上走判断
                pre++;
                // 之后next这个数字就是基准值下标了
            }
            // pre的值比当前基准值小
            while(pre < next && arr[pre] <= current) {
                pre++;
            }
            // arr[pre] > current
            if(pre < next) {
                arr[next] = arr[pre];
                next--;
                // 之后pre这个数字就是基准值下标了
            }
        }
        // 结束后 pre = next 基准值放于中间
        arr[pre] = current;
        quickSortStack(arr,i,pre-1);
        quickSortStack(arr,pre+1,j);
    }
    public static void sort (int[] arr) {
        Arrays.sort(arr);
    }
    public static void swapArray(int[] arr,int a,int b) {
        if(a == b) return;
        arr[a] = arr[a] ^ arr[b];
        arr[b] = arr[a] ^ arr[b];
        arr[a] = arr[a] ^ arr[b];
    }
    public static boolean isEqual(int[] arr, int[] sort) {
        if((arr == null && sort !=null) || (arr != null && sort == null)) {
            return false;
        }
        if(sort == null) {
            return true;
        }
        if(arr.length != sort.length) {
            return false;
        }
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] != sort[i]) {
                return false;
            }
        }
        return true;
    }
    public static int[] tempNumber(int size,int result) {
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = ((int)((Math.random() *result) + 1) - (int)(Math.random() * result));
        }
        return arr;
    }
    public static int[] copyArr(int[] arr) {
        int[] copyArr = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            copyArr[i] = arr[i];
        }
        return copyArr;
    }
    public static void systemOut(int[] arr, int[] sortArr, int[] tempArr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("arr:%d,sortArr:%d,tempArr:%d",arr[i],sortArr[i],tempArr[i]);
            System.out.println();
        }
    }
    public static void main(String[] args) {
        int tempSize = 2; //比较次数
        int size = 10;// 数组长度
        int result = 50;
        for (int i = 0; i < tempSize; i++) {
            int[] resultArr = tempNumber(size,result);
            int[] sortArr = copyArr(resultArr);
            int[] tempArr = copyArr(resultArr);
            quickSort(resultArr);
            sort(sortArr);
            if(!isEqual(resultArr,sortArr)) {
                systemOut(resultArr,sortArr, tempArr);
                return;
            }
        }
        System.out.println("ok");
    }
}

二分法

时间复杂度： log2^N (二分不一定要有序)

  • 一个有序数组 查找某个数是否存在
  • 一个有序数组 找>=某个数的最左侧的位置
  • 一个有序数组 找<=某个数的最右侧位置
  • 局部最小值问题(数组可以无序 但是相邻位置的数组不能相等)
    // 二分法 谨记二分法不一定要有序
  public static int dichotomy(int[] arr, int result) {
      int flag = -1;
      if (arr == null) {
          return flag;
      }
      int pre = 0;
      int next = arr.length - 1;
      while (pre < next) {
          int middle = (int) ((pre + next) / 2);
           // 这里的middle 可以优化 pre + next 可能会有长度溢出的风险
          // int middle = (int) pre +((next - pre) >> 1)
          if (arr[middle] > result) {
              next = middle - 1;
          }
          if (arr[middle] < result) {
              pre = middle + 1;
          }
          if (arr[middle] == result) {
              flag = middle;
              break;
          }
      }
      return flag;
  }