/**
* 题目地址：https://leetcode-cn.com/problems/squares-of-a-sorted-array/
* 参考博客：https://www.cnblogs.com/onepixel/articles/7674659.html
*/
public class T977 {
public static void main(String[] args) {
System.out.println(new T977().sortedSquares(new int[]{-7, -3, 2, 3, 11}));
}
public int[] sortedSquares(int[] A) {
for (int i = 0; i < A.length; i++) {
A[i] *= A[i];
}
return QuickSort(A, 0, A.length - 1);
}
/**
* 快排：
* 复杂度 O(n*log2n)
* 稳定排序：是
*/
public int[] QuickSort(int[] A, int p, int r) {
if (p < r) {
int q = partition(A, p, r);
QuickSort(A, p, q - 1);
QuickSort(A, q + 1, r);
}
return A;
}
private int partition(int[] A, int p, int r) {
int x = A[p];
int j = r;
for (int i = p + 1; i <= r; i++) {
if (i > j) {
break;
}
if (A[i] > x) {
while (j >= i && A[j] > x) {
j--;
}
if (j >= i) {
A[i] = A[j] ^ A[i];
A[j] = A[j] ^ A[i];
A[i] = A[j] ^ A[i];
} else {
break;
}
}
}
if (p != j) {
A[p] = A[j] ^ A[p];
A[j] = A[j] ^ A[p];
A[p] = A[j] ^ A[p];
}
return j;
}
/**
* 归并排序： 二分递归拆分数组，由于左右两部分各自有序，在合并时比较队首大小，将笑的先放入辅助数组中
* 复杂度 O(n*log2n)
* 稳定排序：是
*/
public int[] MergeSort(int[] A) {
if (A.length == 1) {
return A;
}
int[] left = MergeSort(Arrays.copyOfRange(A, 0, A.length / 2));
int[] right = MergeSort(Arrays.copyOfRange(A, A.length / 2, A.length));
int[] B = new int[A.length];
for (int i = 0, j = 0, k = 0; i < left.length || j < right.length; k++) {
if (i < left.length && j < right.length) {
if (left[i] < right[j]) {
B[k] = left[i];
i++;
} else {
B[k] = right[j];
j++;
}
} else if (i < left.length) {
B[k] = left[i];
i++;
} else if (j < right.length) {
B[k] = right[j];
j++;
}
}
return B;
}
/**
* 插入排序：当前数据小于前一个，向前遍历，直到前一个数小于或等于当前数据，插入该数字之后
* 复杂度 O(n*n)
* 稳定排序：是
*/
public int[] InsertionSort(int[] A) {
for (int i = 1; i < A.length; i++) {
int t = A[i];
for (int j = i - 1; j >= 0; j--) {
if (A[j] > t) {
A[j + 1] = A[j];
if (j - 1 < 0 || t >= A[j - 1]) {
A[j] = t;
break;
}
} else {
break;
}
}
}
return A;
}
/**
* 希尔排序：基于插入排序的优化，解决插入排序一次只能向前移一步的问题(这个题希尔排序比插入排序快太多了)
* 复杂度 O(n^1.3)
* 稳定排序：否
*/
public int[] ShellSort(int[] A) {
int step = A.length;
while (step / 2 > 0) {
step = step / 2;
for (int i = step; i < A.length; i++) {
int t = A[i];
for (int j = i - step; j >= 0; j -= step) {
if (A[j] > t) {
A[j + step] = A[j];
if (j - step < 0 || t >= A[j - step]) {
A[j] = t;
break;
}
} else {
break;
}
}
}
}
return A;
}
/**
* 选择排序：遍历数列，找到最大的，置于最后
* 复杂度 O(n*n)
* 稳定排序：否（3,3,2 首位的3会排到最后，不能保证顺序）
*/
public int[] SelectionSort(int[] A) {
for (int i = 0; i < A.length - 1; i++) {
int pos = 0;
for (int j = 1; j < A.length - i; j++) {
if (A[j] > A[pos]) {
pos = j;
}
}
if (pos != A.length - i - 1) {
A[pos] = A[A.length - i - 1] ^ A[pos];
A[A.length - i - 1] = A[A.length - i - 1] ^ A[pos];
A[pos] = A[A.length - i - 1] ^ A[pos];
}
}
return A;
}
/**
* 冒泡排序:相邻的数比较大小，将较大的置换到后面，一次循环将最大的换到最后
* 复杂度 O(n*n)
* 稳定排序：是
*/
public int[] BubbleSort(int[] A) {
for (int i = 0; i < A.length; i++) {
for (int j = 1; j < A.length - i; j++) {
if (A[j] < A[j - 1]) {
// int t = A[j - 1];
// A[j - 1] = A[j];
// A[j] = t;
/**
* 使用位运算优化两个数字交换，节省临时变量
* 例 1，3
* 1的二进制为 01
* 3的二进制为 11
* 根据异或相同为0不同为1
* 第一次异或
* 0 1
* 1 1
* ---
* 1 0
* 值为2
* 覆盖1得2和3
* 第二次
* 1 0
* 1 1
* ---
* 0 1
* 覆盖3得2和1
* 第三次
* 1 0
* 0 1
* ---
* 1 1
* 覆盖2，交换完成
*/
A[j] = A[j - 1] ^ A[j];
A[j - 1] = A[j - 1] ^ A[j];
A[j] = A[j - 1] ^ A[j];
}
}
}
return A;
}
}
网友评论