1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

public int[] sort(int[] nums) {
  int len = nums.length;
  for(int i = 1; i < len; i++) {
    int n = nums[i];
    int j = i;
    for(; j>0 && n<nums[j-1]; j--) {
			nums[j] = nums[j-1];
    }
    nums[j] = n;
  }
  return nums;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

public int[] sort(int[] nums) {
    int len = nums.length;
        for(int i = 0; i < len; i++) {
            int min = i;
            for(int j = i + 1; j < len; j++) {
                    if(nums[j] < nums[min]) {
                        min = j;
                    }
            }
            int tmp = nums[i];
            nums[i] = nums[min];
            nums[min] = tmp;
        }
        return nums;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

public int[] sortArray(int[] nums) {
        int len = nums.length;
        for(int i = 0; i < len; i++) {
            for(int j = 0; j < len-i-1; j++) {
                    if(nums[j] > nums[j+1]) {
                        int tmp = nums[j];
                        nums[j] = nums[j+1];
                        nums[j+1] = tmp;
                    }
            }
        }
        return nums;
    }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public void fastSort(int[] a, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int left = lo;
        int right = hi;

        //保存基准值
        int pivot = a[left];
        while (left < right) {
            //从后向前找到比基准小的元素
            while (left < right && a[right] >= pivot)
                right--;
            a[left] = a[right];
            //从前往后找到比基准大的元素
            while (left < right && a[left] <= pivot)
                left++;
            a[right] = a[left];
        }
        // 放置基准值，准备分治递归快排
        a[left] = pivot;
        fastSort(a, lo, left - 1);
        fastSort(a, left + 1, hi);
    }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

public class Merge {

    //归并所需的辅助数组
    private static int[] aux;

    public static void sort(int[] a) {
        //一次性分配空间
        aux = new int[a.length];
        sort(a, 0, a.length - 1);
    }

    public static void sort(int[] a, int low, int high) {
        if (low >= high) {
            return;
        }
        int mid = (low + high) / 2;
        //将左半边排序
        sort(a, low, mid);
        //将右半边排序
        sort(a, mid + 1, high);
        merge(a, low, mid, high);
    }

    /**
     * 该方法先将所有元素复制到aux[]中，然后在归并会a[]中。方法咋归并时(第二个for循环)
     * 进行了4个条件判断：
     * - 左半边用尽(取右半边的元素)
     * - 右半边用尽(取左半边的元素)
     * - 右半边的当前元素小于左半边的当前元素(取右半边的元素)
     * - 右半边的当前元素大于等于左半边的当前元素(取左半边的元素)
     * @param a
     * @param low
     * @param mid
     * @param high
     */
    public static void merge(int[] a, int low, int mid, int high) {
        //将a[low..mid]和a[mid+1..high]归并
        int i = low, j = mid + 1;
        for (int k = low; k <= high; k++) {
            aux[k] = a[k];
        }

        for (int k = low; k <= high; k++) {
            if (i > mid) {
                a[k] = aux[j++];
            } else if (j > high) {
                a[k] = aux[i++];
            } else if (aux[j] < aux[i]) {
                a[k] = aux[j++];
            } else {
                a[k] = aux[i++];
            }
        }
    }

}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public int[] sortArray(int[] nums) {
  for(int i = nums.length-1; i>0;i--) {
    // 每次都重新构建一次堆
    max_heapify(nums, i);

    // 将堆顶放到最后，表示已经确定排序了
    int tmp = nums[0];
    nums[0] = nums[i];
    nums[i] = tmp;
  }
  return nums;
}
public void max_heapify(int[] nums, int f) {
  int child;
  // 遍历所有父节点
  for(int i = (f-1)/2;i>=0;i--) {
    child = i*2+1;
    if(child!=f && nums[child+1]>nums[child]) {
      child++;
    }
    // 如果父节点比最大的子节点小就交换。
    if(nums[i]<nums[child]) {
      int tmp = nums[i];
      nums[i] = nums[child];
      nums[child] = tmp;
    }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

public int[] sortArray(int[] nums) {
        sort(nums);
        return nums;
    }
    public static void sort(int[] arr) {
    if (arr.length <= 1) return;

    //取得数组中的最大数，并取得位数
    int max = 0;
    for (int i = 0; i < arr.length; i++) {
        if (max < arr[i]) {
            max = arr[i];
        }
    }
    int maxDigit = 1;
    while (max / 10 > 0) {
        maxDigit++;
        max = max / 10;
    }
    //申请一个桶空间
    int[][] buckets = new int[10][arr.length];
    int base = 10;

    //从低位到高位，对每一位遍历，将所有元素分配到桶中
    for (int i = 0; i < maxDigit; i++) {
        int[] bktLen = new int[10];        //存储各个桶中存储元素的数量

        //分配：将所有元素分配到桶中
        for (int j = 0; j < arr.length; j++) {
            int whichBucket = (arr[j] % base) / (base / 10);
            buckets[whichBucket][bktLen[whichBucket]] = arr[j];
            bktLen[whichBucket]++;
        }

        //收集：将不同桶里数据挨个捞出来,为下一轮高位排序做准备,由于靠近桶底的元素排名靠前,因此从桶底先捞。
        // 以个位数为例，个位数越大，加入arr的时间就越迟。那么在之后判断十位数的时候，也会较迟的加入arr中，因此而产生相同十位数，个位数的不同
        int k = 0;
        for (int b = 0; b < buckets.length; b++) {
            for (int p = 0; p < bktLen[b]; p++) {
                arr[k++] = buckets[b][p];
            }
        }
        System.out.println("Sorting: " + Arrays.toString(arr));
        base *= 10;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

public static void sort(int[] a) {
    int length = a.length;
    int h = 1;
    while (h < length / 3) h = 3 * h + 1;
    for (; h >= 1; h /= 3) {
        for (int i = 0; i < a.length - h; i += h) {
            for (int j = i + h; j > 0; j -= h) {
                if (a[j] < a[j - h]) {
                    int temp = a[j];
                    a[j] = a[j - h];
                    a[j - h] = temp;
                }
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/**
    * 左旋
    */
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                        TreeNode<K,V> p) {
    //这里的p即上图的A节点，r指向右孩子即C，rl指向右孩子的左孩子即D，pp为p的父节点
    TreeNode<K,V> r, pp, rl;
    if (p != null && (r = p.right) != null) {
        if ((rl = p.right = r.left) != null)
            rl.parent = p;
        //将p的父节点的孩子节点指向r
        // 如果A就是根节点，那么C换上来之后，要把它变成黑色，因为根节点都是黑色的
        if ((pp = r.parent = p.parent) == null)
            (root = r).red = false;
        else if (pp.left == p)
            pp.left = r;
        else
            pp.right = r;
        //将p置为r的左节点
        r.left = p;
        p.parent = r;
    }
    return root;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

/**
* 右旋
*/
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                        TreeNode<K,V> p) {
        //这里的p即上图的A节点，l指向左孩子即C，lr指向左孩子的右孩子即E，pp为p的父节点
    TreeNode<K,V> l, pp, lr;
    if (p != null && (l = p.left) != null) {
        if ((lr = p.left = l.right) != null)
            lr.parent = p;
        if ((pp = l.parent = p.parent) == null)
            (root = l).red = false;
        else if (pp.right == p)
            pp.right = l;
        else
            pp.left = l;
        l.right = p;
        p.parent = l;
    }
    return root;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

public List<Integer> ans = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root){
  preorder(root);
  return ans;
}

public void preorder(TreeNode node) {
  if(node == null) return;
  ans.add(node.val);
  preorder(node.left);
  preorder(node.right);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

public List<Integer> ans = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root){
  inorder(root);
  return ans;
}

public void inorder(TreeNode node) {
  if(node == null) return;
  inorder(node.left);
  ans.add(node.val);
  inorder(node.right);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

public List<Integer> ans = new ArrayList<>();
public List<Integer> postorderTraversal(TreeNode root){
  postorder(root);
  return ans;
}

public void postorder(TreeNode node) {
  if(node == null) return;
  postorder(node.left);
  postorder(node.right);
  ans.add(node.val);
}