排序算法
$O(n^2)$ 算法
Bubble Sort
-
原理
- 两层循环，内循环对比每一个元素及其右边的元素并将较大的元素swap到右边，在内循环结束后，当前最大的元素将会被移动到其正确的位置上。外层循环控制检查的次数，最多检查length-1次。
- 在执行算法的过程中，数组分为两部分，左半部分是未排序的，右半部分是排好序的。
时间复杂度：$O(n2)$。执行$O(n2) / 2$次比较，$O(n^2) / 4$次swap。原因是每次需要比较的元素都比上次少一个，因为当前最大元素已经被移动到正确位置上，所以共有$n + (n - 1) + (n - 2) + ... + 1$次比较，既$O(n^2) / 2$次比较。而每次比较移动两个元素，所以共有$O(n^2) / 4$次swap。
最坏的情况出现在数组倒叙排列的情况下，在这种情况下每个元素都需要被移动。
代码如下：
public int[] bubbleSort(int[] nums) {
if (nums == null || nums.length <= 0) {
return nums;
}
int len = nums.length;
for (int i = 0; i < len - 1; i++) {
boolean swapped = false;
for (int j = 0; j < len - 1 - i; j++) {
if (nums[j] > nums[j + 1]) {
swapped = true;
swap(nums, j, j + 1);
}
}
//if no numbers being swapped, the array is fully sorted already.
if (!swapped) {
break;
}
}
return nums;
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
Selection Sort
-
原理
- 将要排序的对象分成两部分，一部分是已排序的，一部分是未排序的。如果排序是由小到大，从后端未排序的部分选择一个最小值并放入前段已排序的部分的UI后一个。
时间复杂度：$O(n2)$，$O(n2) / 2$ swap worst case。
代码如下：
public void selectionSort(int[] nums) {
if (nums == null || nums.length <= 1) {
return;
}
int min;
int len = nums.length;
for (int i = 0; i < len - 1; i++) {
min = i;
for (int j = i + 1; j < len; j++) {
if (nums[j] < nums[min]) {
min = j;
}
}
swap(nums, i, min);
}
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
Insert Sort
-
原理
- 将要排序的对象分作两部分，一个是已排序的，一个是未排序的。每次从后端未排序部分取得最前端的值，然后插入前段已排序的部分的适当位置。
时间复杂度：$O(n^2)$，$O(n)$ in the best case.
public void insertSort(int[] nums) {
if (nums == null || nums.length <= 1) {
return;
}
int len = nums.length;
for (int i = 1; i < len; i++) {
int tmp = nums[i];
int j = i;
while (j > 0 && nums[j - 1] >= tmp) {
nums[j] = nums[j - 1];
j--;
}
nums[j] = tmp;
}
}
$O(nlogn)$ 算法
Merge Sort
-
原理
- Merge sort利用了divide-and-conquer的思想。
- 将原有的排序问题对半分割
- 利用相同的方法分别解决每个子问题
- 最终将子问题的结果组合起来。
- 这就是divide-and-conquer的三个重要步骤：divide-conquer-combine
-
步骤
- 对第一部分进行排序
- 对第二部分进行排序
- 将两部分分别排好序的子数组merge到一起
时间复杂度：$O(n^2)$ on average。
算法如下：
public int[] mergeSort(int[] nums) {
if (nums == null || nums.length <= 1) {
return nums;
}
int len = nums.length;
int mid = len / 2;
int[] left = new int[mid];
int[] right = new int[len - mid];
copyArray(nums, left, 0, mid - 1);
copyArray(nums, right, mid, len - 1);
left = mergeSort(left);
right = mergeSort(right);
return merge(left, right);
}
private int[] merge(int[] left, int[] right) {
int[] merged = new int[left.length + right.length];
int index_left = 0;
int index_right = 0;
int index_m = 0;
while (index_left < left.length && index_right < right.length) {
if (left[index_left] < right[index_right]) {
merged[index_m] = left[index_left++];
} else {
merged[index_m] = right[index_right++];
}
index_m++;
}
if (index_left < left.length) {
for (int i = index_left; i < left.length; i++) {
merged[index_m++] = left[i];
}
} else {
for (int i = index_right; i < right.length; i++) {
merged[index_m++] = right[i];
}
}
return merged;
}
private void copyArray(int[] nums, int[] target, int start, int end) {
int index = 0;
for (int i = start; i <= end; i++) {
target[index++] = nums[i];
}
}
Quick Sort
-
原理
- 找一个pivot，将原数组分成两部分，然后对每一部分重复这个过程直到每一个元素都被选为pivot一次并得到处理。
-
步骤
- 选取一个pivot
- 将原数组分成三部分：
- 第一部分：所有小于pivot的元素
- 第二部分：所有大于等于pivot的元素
- 第三部分：pivot自己
- 对第一部分和第二部分进行quick sort
代码如下：
public void quickSort(int[] nums) {
if (nums == null || nums.length <= 1) {
return;
}
quickSortHelper(nums, 0, nums.length - 1);
}
private void quickSortHelper(int[] nums, int left, int right) {
if (left >= right) {
return;
} else {
int pivot = nums[right];
int pivotIndex = partition(nums, left, right, pivot);
quickSortHelper(nums, left, pivotIndex - 1);
quickSortHelper(nums, pivotIndex + 1, right);
}
}
private int partition(int[] nums, int left, int right, int pivot) {
int leftPointer = left - 1;
int rightPointer = right;
while (true) {
while (leftPointer < rightPointer && nums[++leftPointer] < pivot);
while (rightPointer > leftPointer && nums[--rightPointer] > pivot);
if (leftPointer >= rightPointer) {
break;
} else {
swap(nums, leftPointer, rightPointer);
}
}
swap(nums, leftPointer, right);
return leftPointer;
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
对于quick sort，需要注意的是其时间复杂度不一定总是$O(nlogn)$，在最坏情况下其时间复杂度是$O(n^2)$。当quick sort每次都将数组分割成两个长度分别为$n-1$和$0$的子数组时出现。这种情况会在数组是正序或者倒叙排列时出现。此时$T(n) = T(n-1) + O(n)$，从而使得时间复杂度为$O(n^2)$。那么我们怎么解决这个问题呢？
可以使用randomized quick sort来解决。在选取pivot的时候，我们不再使用最右边的元素作为pivot而是从数组中随机选择一个来作为pivot从而避免刚好选到最大值或者最小值的情况初选。通过这种方式，quick sort可以得到平均$O(nlogn)$的时间复杂度。
Heap Sort
待完善
搜索算法
$O(n)$算法
Linear Search
-
原理
- 将全部元素清点一遍，寻找需要的值。
时间复杂度：$O(n)$
public int lineSearch(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
for (int i = 0; i < nums.length; i++0 {
if (nums[i] == target) {
return i;
}
}
return -1;
}
Quick Select
$O(logn)$算法
Binary Search
-
原理
- 每次搜索扔掉一半的元素，只有能够线性定位的结构能够使用。（比如LinkedList就不能使用，因为无法再O(1)时间内直接得到中间点。）
- 数组必须是排好序的
时间复杂度：$O(logn)$
public int binarySearch(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int start = 0;
int end = nums.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
//avoid int overflow
if (nums[mid] == target) {
return mid;
}
if (nums[mid] < target) {
start = mid + 1;
}
if (nums[mid] > target) {
end = mid - 1;
}
}
return -1;
}
