### 排序

#### 堆排序

1. 建堆（升序-大顶堆，降序-小顶堆）
2. 堆顶与末尾交换，重新建堆

- 时间复杂度：O（n log n）
- 空间复杂度：O（n）

```Java
class Solution {
	public int[] HeapSort(int[] nums) {
		int[] heap = Arrays.copyOf(nums, nums.length);
		int len = heap.length;
		
		buildMaxHeap(heap);
		
		for (int i=heap.lengh-1; i>=0; i--) {
			swap(heap, 0, i);
			len--;
			heapify(heap, 0, len);
		}
		
		return heap;
	}
	
	public void buildMaxHeap(int[] heap) {
		for (int i=heap.length/2; i>=0; i--) {
			heapify(heap, i, heap.length);
		}
	}
	
	public void heapify(int[] heap, int i, int len) {
		int l = 2 * i + 1;
		int r = 2 * i + 2;
		int largest = i;
		
		if (l < len && heap[l] > heap[largest]) {
			largest = l;
		}
		if (r < len && heap[r] > heap[largest]) {
			largest = r;
		}
		if (largest != i) {
			swap(heap, largest, i);
			heapify(heap, largest, len);
		}
	}
	
	public void swap(int[] heap, int x, int y) {
		int temp = heap[x];
		heap[x] = heap[y];
		heap[y] = temp;
	}
}
```

#### 快排

- 分治思想
- 时间复杂度：O（n log n）
- 空间复杂度：O（n）
1. 选择基准，通常是第一个值
2. 左右同时向中间搜索，找到左边第一个大于基准和右边第一个小于基准的，交换
3. 左右指针相遇后与基准值交换
4. 划分为两个小数组，重复2、3

```Java
class Solution {
	public int[] quickSort(int[] nums) {
		partion(nums, 0, nums.length-1);
		return nums;
	}
	
	public void partion(int[] nums, int start, int end) {
		if (start > end) return;
		
		int i = start;
		int j = end;
		while (i < j) {
			while (nums[j] >= nums[start] && i < j) j--;
			while (nums[i] <= nums[start] && i < j) i++;
			if (i < j) {
				swap(nums, i, j);
			}
		}
		swap(nums, i, start);
		partion(nums, start, i-1);
		partion(nums, i+1, end);
	}
	
	public void swap(int[] nums, int x, int y) {
		int temp = nums[x];
		nums[x] = nums[y];
		nums[y] = temp;
	}
}
```

### 随机采样

#### 水塘采样

- 适用于无法将全部元素存入内存，需要随机采样
- 时间复杂度：O(n)
- 空间复杂度：O(k)，k为采样数

```Java
class Solution {
	Random random = new Random();
	ListNode head;
	public void Solution(ListNode head) {
		this.head = head;
	}
	
	public int getRandom() {
		ListNode node = head;
		int val = node.val;
		int n = 1;
		
		while (node != null) {
			if (random.nextFloat() <= 1.0/n) {
				val = node.val;
			}
			n++;
			node = node.next;
		}
		
		return val;
	}
}
```

### 查找

#### 二分查找

- 适用于已排序数组
- 时间复杂度：O(log n)

```java
class Solution {
	public int binarySearch(int[] nums, int target) {
		int l = 0;
		int r = nums.length-1;
		
		while (l <= r) {
			int mid = l + (r - l) / 2;
			if (nums[mid] == target) {
				return mid;
			} else if (nums[mid] < target) {
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		
		return -1;
	}
}
```