算法题目.md · song/大数据笔记

# 1 线性查找法

```java
package selectionsort;

public class GenericSelectionSort {

private GenericSelectionSort(){}

public static <E extends Comparable> void sort1(E[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            for (int j = i; j < arr.length; j++) {
                if (arr[j].compareTo(arr[minIndex]) < 0) {
                    minIndex = j;
                }
            }
            swap(arr, i, minIndex);
        }
    }

private static <E> void swap(E[] arr, int i, int j){

E t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

public static void main(String[] args) {

Integer[] arr = {1, 4, 2, 3, 6, 5};
        sort1(arr);
        for(int e: arr) {
            System.out.print(e + " ");
        }
        System.out.println();
    }
}

```

# 2 选择排序法

- 思想
  - 先把最小的拿出来
  - 剩下的，再把最小的拿出来
  - 剩下的，再把最小的拿出来

- 原地排序

```java
public class SelectionSort {

private SelectionSort(){}

public static void sort(int[] arr){

// arr[0...i) 是有序的；arr[i...n) 是无序的
        for(int i = 0; i < arr.length; i ++){

// 选择 arr[i...n) 中的最小值的索引
            int minIndex = i;
            for(int j = i; j < arr.length; j ++){
                if(arr[j] < arr[minIndex])
                    minIndex = j;
            }

swap(arr, i, minIndex);
        }
    }

private static void swap(int[] arr, int i, int j){

int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

public static void main(String[] args){

int[] arr = {1, 4, 2, 3, 6, 5};
        SelectionSort.sort(arr);
        for(int e: arr)
            System.out.print(e + " ");
        System.out.println();
    }
}

```

# 3 插入排序法

# 附录

## 附录1 性能测试

- 生成正序数列

```java
public class ArrayGenerator {

private ArrayGenerator() {}

public static Integer[] generateOrderedArray(int n) {
        Integer[] arr = new Integer[n];
        for (int i=0; i<n; i++) {
            arr[i] = i;
        }
        return arr;
    }
}

```

- 测试

```java
  public class LinearSearch {
  
      private LinearSearch(){}
  
      public static <E> int search(E[] data, E target){
  
          for(int i = 0; i < data.length; i ++) {
              if(data[i].equals(target)) {
                  return i;
              }
          }
  
          return -1;
      }
  
      public static void main(String[] args){
  
          int[] dataSize = {1000000, 10000000};
          for(int n: dataSize) {
              Integer[] data = ArrayGenerator.generateOrderedArray(n);
  
              long startTime = System.nanoTime();
              for (int k = 0; k < 100; k++) {
                  LinearSearch.search(data, n);
              }
              long endTime = System.nanoTime();
  
              double time = (endTime - startTime) / 1000000000.0;
              System.out.println("n = " + n + ", 100 runs : " + time + "s");
          }
      }
  }
  
  ```

# Leecode

song/大数据笔记

简介

发行版

贡献者

近期动态

song/大数据笔记 .gitee-modal { width: 500px !important; }

简介

发行版

贡献者

近期动态

搜索帮助

song/大数据笔记