目录
选择排序
public class Test {
public static void selectSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
//0 - n-1 位置有序
//1 - n-1 位置有序
//... - n-1 位置有序
for (int i = 0; i < arr.length - 1; i++) {
//i 位置后 最小值
int maxIndex = i;
for (int j = i + 1; j < arr.length; j++) {
maxIndex = arr[j] < arr[maxIndex] ? j : maxIndex;
}
swap(arr, i, maxIndex);
}
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
冒泡排序
public class Test {
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 0 ~ N-1
// 0 ~ N-2
// 0 ~ N-3
for (int e = arr.length - 1; e > 0; e--) { // 0 ~ e
for (int i = 0; i < e; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
}
}
}
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
插入排序
public class Test {
public static void insertSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 1; i < arr.length; i++) {
for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
swap(arr, j, j + 1);
}
}
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
归并排序
public class Test {
//递归实现 O(N * logN)
public static void mergeSort1(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
process(arr, 0, arr.length - 1);
}
//非递归实现 O(N * logN)
public static void mergeSort2(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int N = arr.length;
int step = 1;
while (step < N) {
int L = 0;
while (L < N) {
if (L + step >= N) {
break;
}
int mid = L + step - 1;
int R = Math.min(mid + step, N - 1);
merge(arr, L, mid, R);
L = R + 1;
}
//防止溢出
if (step > N / 2) {
break;
}
step <<= 1;
}
}
public static int[] copyArray(int[] arr) {
int[] newArr = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
newArr[i] = arr[i];
}
return newArr;
}
private static void process(int[] arr, int L, int R) {
if (L == R) {
return;
}
int mid = L + (R - L) / 2;
//左边有序
process(arr, 0, mid);
//右边有序
process(arr, mid + 1, R);
//两边都有序后 进行合并
merge(arr, L, mid, R);
}
private static void merge(int[] arr, int L, int mid, int R) {
int[] newArr = new int[R - L + 1];
int i = 0;
int p1 = L;
int p2 = mid + 1;
while (p1 <= mid && p2 <= R) {
newArr[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= mid) {
newArr[i++] = arr[p1++];
}
while (p2 <= R) {
newArr[i++] = arr[p2++];
}
for (int j = 0; j < newArr.length; j++) {
arr[L + j] = newArr[j];
}
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void main(String[] args) {
int[] arr = {1, 3, 8, 9, 5, 2, 4, 6, 7};
int[] arr2 = copyArray(arr);
mergeSort1(arr);
mergeSort2(arr2);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
for (int i = 0; i < arr2.length; i++) {
System.out.print(arr2[i] + " ");
}
}
}
1. 小和问题
在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和
public class Test {
public static int smallSum(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
return process(arr, 0, arr.length - 1);
}
private static int process(int[] arr, int L, int R) {
if (L == R) {
return 0;
}
int mid = L + (R - L) / 2;
return process(arr, L, mid) + process(arr, mid + 1, R) + merge(arr, L, mid, R);
}
private static int merge(int[] arr, int L, int mid, int R) {
int[] newArr = new int[R - L + 1];
int i = 0;
int p1 = L;
int p2 = mid + 1;
int res = 0;
while (p1 <= mid && p2 <= R) {
res += arr[p1] < arr[p2] ? (R - p2 + 1) * arr[p1] : 0;
newArr[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= mid) {
newArr[i++] = arr[p1++];
}
while (p2 <= R) {
newArr[i++] = arr[p2++];
}
for (i = 0; i < newArr.length; i++) {
arr[L + i] = newArr[i];
}
return res;
}
//for test
public static int comparator(int[] arr) {
int res = 0;
for (int i = 1; i < arr.length; i++) {
for (int j = 0; j < i; j++) {
res += arr[j] < arr[i] ? arr[j] : 0;
}
}
return res;
}
//for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}
// for test
public static int[] copyArray(int[] arr) {
if (arr == null) {
return null;
}
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = arr[i];
}
return res;
}
// for test
public static void printArray(int[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 100;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
if (smallSum(arr1) != comparator(arr2)) {
succeed = false;
printArray(arr1);
printArray(arr2);
break;
}
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
}
}
快速排序
public class Test {
// 快排 1.0版本
public static void quickSort1(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
process1(arr, 0, arr.length - 1);
}
private static void process1(int[] arr, int L, int R) {
if (L >= R) {
return;
}
int M = partition(arr, L, R);
process1(arr, L, M - 1);
process1(arr, M + 1, R);
}
// arr[L..R]上，以arr[R]位置的数做划分值
private static int partition(int[] arr, int L, int R) {
if (L > R) {
return -1;
}
if (L == R) {
return L;
}
int left = L - 1;
int index = L;
while (index < R) {
if (arr[index] <= arr[R]) {
swap(arr, index, left + 1);
left++;
}
index++;
}
swap(arr, ++left, R);
return left;
}
public static void quickSort2(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
process2(arr, 0, arr.length - 1);
}
// arr[L...R] 排有序，快排2.0方式
private static void process2(int[] arr, int L, int R) {
if (L >= R) {
return;
}
// [ equalArea[0] , equalArea[0]]
int[] equalArea = netherlandsFlag(arr, L, R);
process2(arr, L, equalArea[0] - 1);
process2(arr, equalArea[1] + 1, R);
}
// arr[L...R] 玩荷兰国旗问题的划分，以arr[R]做划分值
// <arr[R] ==arr[R] > arr[R]
private static int[] netherlandsFlag(int[] arr, int L, int R) {
if (L > R) { // L...R L>R
return new int[]{-1, -1};
}
if (L == R) {
return new int[]{L, R};
}
int less = L - 1; // < 区 右边界
int more = R; // > 区 左边界
int index = L;
while (index < more) { // 当前位置，不能和 >区的左边界撞上
if (arr[index] == arr[R]) {
index++;
} else if (arr[index] < arr[R]) {
// swap(arr, less + 1, index);
// less++;
// index++;
swap(arr, index++, ++less);
} else { // >
swap(arr, index, --more);
}
}
swap(arr, more, R); // <[R] =[R] >[R]
return new int[]{less + 1, more};
}
// 快排 3.0 最终版本
public static void quickSort3(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
process3(arr, 0, arr.length - 1);
}
public static void process3(int[] arr, int L, int R) {
if (L >= R) {
return;
}
swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
int[] equalArea = netherlandsFlag(arr, L, R);
process3(arr, L, equalArea[0] - 1);
process3(arr, equalArea[1] + 1, R);
}
// for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}
// for test
public static int[] copyArray(int[] arr) {
if (arr == null) {
return null;
}
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = arr[i];
}
return res;
}
// for test
public static boolean isEqual(int[] arr1, int[] arr2) {
if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
return false;
}
if (arr1 == null && arr2 == null) {
return true;
}
if (arr1.length != arr2.length) {
return false;
}
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
private static void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 100;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
int[] arr3 = copyArray(arr1);
quickSort1(arr1);
quickSort2(arr2);
quickSort3(arr3);
if (!isEqual(arr1, arr2) || !isEqual(arr2, arr3)) {
succeed = false;
break;
}
}
System.out.println(succeed ? "Nice!" : "Oops!");
}
}
堆排序
基数排序
public class Test {
// only for no-negative value
public static void radixSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
radixSort(arr, 0, arr.length - 1, maxbits(arr));
}
public static int maxbits(int[] arr) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
}
int res = 0;
while (max != 0) {
res++;
max /= 10;
}
return res;
}
// arr[L..R]排序 , 最大值的十进制位数digit
public static void radixSort(int[] arr, int L, int R, int digit) {
final int radix = 10;
int i = 0, j = 0;
// 有多少个数准备多少个辅助空间
int[] help = new int[R - L + 1];
for (int d = 1; d <= digit; d++) { // 有多少位就进出几次
// 10个空间
// count[0] 当前位(d位)是0的数字有多少个
// count[1] 当前位(d位)是(0和1)的数字有多少个
// count[2] 当前位(d位)是(0、1和2)的数字有多少个
// count[i] 当前位(d位)是(0~i)的数字有多少个
int[] count = new int[radix]; // count[0..9]
for (i = L; i <= R; i++) {
// 103 1 3
// 209 1 9
j = getDigit(arr[i], d);
count[j]++;
}
for (i = 1; i < radix; i++) {
count[i] = count[i] + count[i - 1];
}
for (i = R; i >= L; i--) {
j = getDigit(arr[i], d);
help[count[j] - 1] = arr[i];
count[j]--;
}
for (i = L, j = 0; i <= R; i++, j++) {
arr[i] = help[j];
}
}
}
public static int getDigit(int x, int d) {
return ((x / ((int) Math.pow(10, d - 1))) % 10);
}
// for test
public static void comparator(int[] arr) {
Arrays.sort(arr);
}
// for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random());
}
return arr;
}
// for test
public static int[] copyArray(int[] arr) {
if (arr == null) {
return null;
}
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = arr[i];
}
return res;
}
// for test
public static boolean isEqual(int[] arr1, int[] arr2) {
if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
return false;
}
if (arr1 == null && arr2 == null) {
return true;
}
if (arr1.length != arr2.length) {
return false;
}
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
// for test
public static void printArray(int[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// for test
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 100;
int maxValue = 100000;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
radixSort(arr1);
comparator(arr2);
if (!isEqual(arr1, arr2)) {
succeed = false;
printArray(arr1);
printArray(arr2);
break;
}
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
int[] arr = generateRandomArray(maxSize, maxValue);
printArray(arr);
radixSort(arr);
printArray(arr);
}
}