概述
- 一般排序算法(以元素比较为基础) => 快速排序、归并排序、插入排序、冒泡排序、堆排序
- 特殊排序算法 => 基数排序、桶排序
循环不变式 for/while
循环不变式过程
- 初始化 => 循环的第一次迭代之前循环不变式为真
- 保持 => 如果循环的某次迭代之前它为真，那么下次迭代之前它仍为真 => 在从当前状态到下一个状态的过程中能得以保持
- 终止 => 在循环终止时，不变式为我们提供了一个有用的性质，该性质有助于证明算法是正确的。如果程序可以在某种条件下终止，那么在终止的时候，就可以得到自己想要的正确结果
插入排序 Insertion Sort
- 时间复杂度
- Best => O(n) => 数组已经排序
- Average => O(n^2) => 确定在什么位置插入元素 num，平均地数组中有一半元素大于 num，一半小于 num
- Worse => O(n^2) => 数组反向排序
- 空间复杂度：O(1)
模板
public class InsertionSort {
public void sort(int[] nums) {
// check input
if (nums == null || nums.length == 0) {
return;
}
for (int i = 1; i < nums.length; i++) {
int j = i - 1;
int key = nums[i];
while (j >= 0 && nums[j] > key) {
nums[j + 1] = nums[j];
j--;
}
nums[j + 1] = key;
}
}
}
循环不变式
在 for 循环(循环变量为i)的每次迭代的开始，包含元素 nums[0, i - 1] 的子数组是有序的
冒泡排序 Bubble Sort
- 核心想法 => 反复交换相邻的未按次序排列的元素
- 时间复杂度
- Best => O(n)(改进后)/O(n^2)
- Average=> O(n^2)
- Worse => O(n^2)
- 空间复杂度：O(1)
模板
public class BubbleSort {
public void sort(int[] nums) {
// 时间复杂度：O(n^2)
// check input
if (nums == null || nums.length == 0) {
return;
}
int length = nums.length;
int temp;
for (int i = 0; i < length; i++) {
for (int j = 1; j < length - i; j++) {
if (nums[j] < nums[j - 1]) {
temp = nums[j - 1];
nums[j - 1] = nums[j];
nums[j] = temp;
}
}
}
}
public void sortRefine(int[] nums) {
// check input
if (nums == null || nums.length == 0) {
return;
}
int length = nums.length;
int temp;
for (int i = 0; i < length; i++) {
boolean flag = true;
for (int j = 1; j < length - i; j++) {
if (nums[j] < nums[j - 1]) {
temp = nums[j - 1];
nums[j - 1] = nums[j];
nums[j] = temp;
flag = false;
}
}
if (flag) {
break;
}
}
}
}
循环不变式
在 for 循环(循环变量为i)的每次迭代的开始，包含元素 nums[length - i - 1, length - 1] 的子数组是有序的
归并排序 Merge Sort
- 核心想法 => 分治法(Divide and Conquer) => 找中点，之后分别排序，再合并两个有序数组 => 分成最小，然后两两比较合并
- 时间复杂度：O(nlogn)
- 空间复杂度：O(n)
- 注意：合并两个有序数组，剩余部分使用 while 循环
模板1
import java.util.Arrays;
public class MergeSort {
public void sort(int[] nums) {
// check input
if (nums == null || nums.length == 0) {
return;
}
mergeSort(nums, 0, nums.length - 1);
}
private void mergeSort(int[] nums, int start, int end) {
if (start < end) {
int mid = start + (end - start) / 2;
mergeSort(nums, start, mid);
mergeSort(nums, mid + 1, end);
mergeTwoSortedArray(nums, start, mid, end);
}
}
private void mergeTwoSortedArray(int[] nums, int start, int mid, int end) {
// copy arrays
int[] left = new int[mid - start + 1];
int[] right = new int[end - mid];
for (int i = 0; i < left.length; i++) {
left[i] = nums[i + start];
}
for (int i = 0; i < right.length; i++) {
right[i] = nums[i + mid + 1];
}
// merge two sorted array
int index = start;
int first = 0;
int second = 0;
while (first < left.length && second < right.length) {
if (left[first] < right[second]) {
nums[index++] = left[first++];
} else {
nums[index++] = right[second++];
}
}
// remaining
while (first < left.length) {
nums[index++] = left[first++];
}
while (second < right.length) {
nums[index++] = right[second++];
}
}
}
模板2
import java.util.Arrays;
public class MergeSort {
public void sortTwo(int[] nums) {
// check input
if (nums == null || nums.length == 0) {
return;
}
int[] temp = new int[nums.length];
mergeSort(nums, temp, 0, nums.length - 1);
}
private void mergeSort(int[] nums, int[] temp, int start, int end) {
if (start >= end) {
return;
}
int mid = start + (end - start) / 2;
mergeSort(nums, temp, start, mid);
mergeSort(nums, temp, mid + 1, end);
mergeTwoSortedArray(nums, temp, start, mid, end);
}
private void mergeTwoSortedArray(int[] nums, int[] temp, int start, int mid, int end) {
// merge two sorted array
int index = start;
int first = start;
int second = mid + 1;
while (first <= mid && second <= end) {
if (nums[first] < nums[second]) {
temp[index++] = nums[first++];
} else {
temp[index++] = nums[second++];
}
}
// remaining
while (first <= mid) {
temp[index++] = nums[first++];
}
while (second <= end) {
temp[index++] = nums[second++];
}
// copy
for (int i = start; i <= end; i++) {
nums[i] = temp[i];
}
}
}
快速排序
- 核心想法 => 分治法(Divide and Conquer) => 通过划分调整大小关系
- 时间复杂度
- Best => O(nlogn) => 划分数组对半分 => T(n) = 2T(n/2) + O(n) => O(nlogn)
- Average => O(nlogn) => 平衡划分，任何以常数比例的划分都会产生深度为 O(logn) 的递归树，其中每一层的代价都是 O(n) -> T(n) = T(kn) + T((1-k)n) + O(n)，其中 0 < k < 1 -> O(nlogn)
- Worse => O(n^2) => 划分两个数组分别为有 n - 1 个元素与0个元素 => T(n) = T(n - 1) + T(0) + O(n) -> O(n^2)
- 空间复杂度：O(1)
模板
import java.util.Arrays;
public class QuickSort {
public void sort(int[] nums) {
// check input
if (nums == null || nums.length == 0) {
return;
}
quickSort(nums, 0, nums.length - 1);
}
private void quickSort(int[] nums, int start, int end) {
if (start >= end) {
return;
}
int pivot = partitionTwo(nums, start, end);
quickSort(nums, start, pivot - 1);
quickSort(nums, pivot + 1, end);
}
private int partitionTwo(int[] nums, int start, int end) {
int pivot = start;
int pivotValue = nums[pivot];
while (start < end) {
while (start < end && nums[end] >= pivotValue) {
end--;
}
// find the first element that smaller than pivotValue
nums[start] = nums[end];
while (start < end && nums[start] <= pivotValue) {
start++;
}
// find the first element that bigger than pivotValue
nums[end] = nums[start];
}
nums[start] = pivotValue;
return start;
}
private int partition(int[] nums, int start, int end) {
int pivotValue = nums[end];
// j 是第一个小于 pivotValue 的位置
int j = start - 1;
for (int i = start; i < end; i++) {
if (nums[i] <= pivotValue) {
j++;
// 说明i之前一定有元素大于 pivotValue，需要交换
if (i != j) {
swap(nums, i, j);
}
}
}
swap(nums, j + 1, end);
return j + 1;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
分治法
- 分解 => 将数组划分为两个(可能为空)子数组，使得前一个子数组中的每个元素都小于或等于 nums[pivot]，后一个都大于 nums[pivot]
- 解决 => 递归的对两个子数组分别排序
- 合并 => 由于子数组都是原地排序不需要合并
循环不变式
对于每一轮迭代开始时对于任意数组下标i都有：
- 若 start <= i <= pivot，则 nums[i] <= nums[pivot]
- 若 i == pivot，则 nums[i] == nums[pivot]
- 若 pivot < i <= end，则 nums[pivot] < nums[i]
期望为线性时间的快速选择算法 Quick Select
求数组 nums 中第 k 小的元素
- 将数组划分为两个(可能为空)子数组，是的前一个子数组中的每个元素都小于或等于 nums[index]，后一个都大于 nums[index]
- 检查 nums[index] 是否为第 k 小的元素
- index == k => 返回 nums[index]
- index > k => 第 k 小的元素落在低区
- index < k => 第 k 小的元素落在高区，并且已经知道有 index 个元素比 nums[index] 小
public class QuickSelect {
public int getKthSmallerElement(int[] nums, int k) {
// check input
if (nums == null || nums.length == 0 || k > nums.length) {
return -1;
}
return quickSelect(nums, 0, nums.length - 1, k);
}
private int quickSelect(int[] nums, int start, int end, int k) {
if (start == end) {
return nums[start];
}
int pivot = partition(nums, start, end);
if (pivot == k - 1) {
return nums[pivot];
}
if (pivot < k - 1) {
// 高区
return quickSelect(nums, pivot + 1, end, k);
}
// 低区
return quickSelect(nums, start, pivot - 1, k);
}
private int partition(int[] nums, int start, int end) {
int pivotValue = nums[end];
int j = start - 1;
for (int i = start; i < end; i++) {
if (nums[i] <= pivotValue) {
j++;
if (i != j) {
swap(nums, i, j);
}
}
}
swap(nums, j + 1, end);
return j + 1;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
知识点
- 稳定 => 相同值元素的相对位置 =>
index1 < index2 && nums[index1] == nums[index2]=> 排序后 index1 仍然在 index2 之前- case: 3 1(1) 2 4 1(2) 6
- 稳定 => 1(1) 1(2) 2 3 4 6
- 不稳定 => 1(2) 1(1) 2 3 4 6
网友评论