排序

// ../../../../../src/main/java/com/dll/sort/BubbleSort.java

package com.dll.sort;

public class BubbleSort {

  private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }

  public void sort(int[] arr) {
    boolean swapped = false;
    for (int i = 0; i < arr.length - 1; i++) {
      for (int j = 0; j < arr.length - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
          this.swap(arr, j, j + 1);
          swapped = true;
        }
      }
      if (!swapped) {
        break;
      }
    }
  }
}

// ../../../../../src/main/java/com/dll/sort/SelectionSort.java

package com.dll.sort;

public class SelectionSort {
    private void swap(int[] arr, int first, int second) {
        int temp = arr[first];
        arr[first] = arr[second];
        arr[second] = temp;
    }

    public void sort(int[] arr) {
        for (int i=0; i < arr.length-1; i++) {
            int minIndex = i;
            for (int j=i+1; j < arr.length; j++) {
                if(arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            this.swap(arr, i, minIndex);
        }
    }
}

// ../../../../../src/main/java/com/dll/sort/QuickSort.java

package com.dll.sort;

public class QuickSort {

  private void swap(int[] arr, int first, int second) {
    int temp = arr[first];
    arr[first] = arr[second];
    arr[second] = temp;
  }

  private void sort_recursion(int[] arr, int start, int end) {
    if (start >= end) {
      return;
    }
    int pivot = arr[start];
    int l = start, r = end;
    while (l < r) {
      while (arr[r] >= pivot && l < r) {
        r--;
      }
      while (arr[l] <= pivot && l < r) {
        l++;
      }
      this.swap(arr, l, r);
    }
    this.swap(arr, start, l);
    this.sort_recursion(arr, start, l - 1);
    this.sort_recursion(arr, l + 1, end);
  }

  public void sort(int[] arr) {
    this.sort_recursion(arr, 0, arr.length - 1);
  }
}

// ../../../../../src/main/java/com/dll/sort/MergeSort.java

package com.dll.sort;

import java.util.Arrays;

public class MergeSort {

  /**
   * 用于合并两个升序的数组
   */
  public int[] mergeSortedArray(int[] arr1, int[] arr2) {
    int[] merged = new int[arr1.length + arr2.length];
    int i = 0;
    int j = 0;
    int k = 0;
    while (i < arr1.length && j < arr2.length) {
      merged[k++] = arr1[i] > arr2[j] ? arr2[j++] : arr1[i++];
    }
    while (i < arr1.length) {
      merged[k++] = arr1[i++];
    }
    while (j < arr2.length) {
      merged[k++] = arr2[j++];
    }
    return merged;
  }

  // [start, mid)
  // [mid, end)
  public int[] merge(int[] arr, int start, int mid, int end) {
    int[] t1 = Arrays.copyOfRange(arr, start, mid);
    int[] t2 = Arrays.copyOfRange(arr, mid, end);
    int[] result = this.mergeSortedArray(t1, t2);
    for (int i = 0; i < result.length; i++) {
      arr[start + i] = result[i];
    }
    return result;
  }

  public void splitAndMerge(int[] arr, int start, int end) {
    if (end - start <= 1) {
      return;
    }
    int mid = start + (end - start) / 2;
    this.splitAndMerge(arr, start, mid);
    this.splitAndMerge(arr, mid, end);
    this.merge(arr, start, mid, end);
  }

  public void sort(int[] arr) {
    this.splitAndMerge(arr, 0, arr.length);
  }
}

// ../../../../../src/main/java/com/dll/sort/InsertSort.java

package com.dll.sort;

/**
 * 插入排序将数组分为两个部分:有序部分和待排序部分
 * 待排序部分中的每个元素和有序部分的每个元素做比较，并插入到合适的位置
 * 第一个元素本身就是有序的，不需要排序
 * 从第二个元素开始，每次都比较
 */
public class InsertSort {

  public void sort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
     for (int j = 0; j < i; j++) {
       if (arr[i] < arr[j]) {
         int temp = arr[i];
         for (int z = i - 1; z >= j; z--) {
           arr[z + 1] = arr[z];
         }
         arr[j] = temp;
       }
     }
    }
  }
}

  t = a;
  a = b;
  b = t;