algorithm/[912]排序数组.java at master · Ada0910/algorithm · GitHub

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
import java.util.Arrays;

//leetcode submit region begin(Prohibit modification and deletion)
// 解法一：
//class Solution {
//	// 用于辅助合并有序数组
//	private static int[] temp;
//
//	public int[] sortArray(int[] nums) {
//		temp = new int[nums.length];
//		sort(nums, 0, nums.length - 1);
//		return nums;
//	}
//
//	/* 排序函数*/
//	public void sort(int[] nums, int lo, int hi) {
//		if (lo == hi) {
//			return;
//		}
//
//		int mid = lo + (hi - lo) / 2;
//		sort(nums, lo, mid);
//		sort(nums, mid + 1, hi);
//		merge(nums, lo, mid, hi);
//	}
//
//	/* 合并之后排序函数*/
//	public void merge(int[] nums, int lo, int mid, int hi) {
//		System.out.println("merge"+ lo +":"+ mid +":"+ hi );
//		for (int i = lo; i <= hi; i++) {
//			temp[i] = nums[i];
//		}
//		//i是会加的，从lo开始
//		int i = lo;
//		// j也是会递增的，从mid+1开始
//		int j = mid + 1;
//
//		for (int p = lo; p <= hi; p++) {
//			// 左边的合并完了，右边直接合并过去
//			if (i == mid + 1) {
//				nums[p] = temp[j++];
//			} else if (j == hi + 1) {
//				nums[p] = temp[i++];
//			} else if (temp[i] > temp[j]) {
//				nums[p] = temp[j++];
//			} else {
//				nums[p] = temp[i++];
//			}
//
//		}
//	}
//}

//解法二：
class Solution {
	public int[] sortArray(int[] nums) {
		//	//写一个随机函数，打乱数组
		suffle(nums);
		sort(nums, 0, nums.length - 1);
		return nums;
	}

	////随机函数
	private void suffle(int[] nums) {
		Random random = new Random();
		int n = nums.length;
		for (int i = 0; i < n; i++) {
			//在（n-i）之中，随机产生一个数
			int j = random.nextInt(n - i) + i;
			swap(nums, i, j);
		}
	}

	//// 原地交换数组中的两个元素
	private static void swap(int[] nums, int i, int j) {
		int temp = nums[i];
		nums[i] = nums[j];
		nums[j] = temp;
	}

	////前序遍历函数
	public void sort(int[] nums, int lo, int hi) {
		if (lo >= hi) {
			return;
		}

		int p = merge(nums, lo, hi);
		sort(nums, lo, p - 1);
		sort(nums, p + 1, hi);
	}

	////排序函数
	private int merge(int[] nums, int lo, int hi) {
		int temp = nums[lo];
		int i = lo + 1, j = hi;
		while (i <= j) {
			while (i < hi && temp >= nums[i]) {
				i++;
			}

			while (j > lo && temp < nums[j]) {
				j--;
			}

			if (i >= j) {
				break;
			}

			swap(nums, i, j);
		}

		swap(nums, lo, j);

		return j;
	}


}
//leetcode submit region end(Prohibit modification and deletion)