论文夹着春招是搞得我最近一段时间有些忙不过来，不过欣慰的是论文已经有大致思路了，在春招中也有幸看到了各路高手神仙打架，有些失落有些兴奋，希望有一天也能练就一身本领，过五关斩六将。
最近写了颇多笔试，下面归纳一下遇到过的经典排序算法
1、为了方便调试这些排序算法，这里设计了一个的简易测试框架
-
具体功能：当我们实现不同算法时，只需要关注方法本身的正确性和完整性，框架会自动化帮助我们完成对该方法的测试用例 -
实现方式：我们在外层调用封装好的框架，将对象传入框架中进行自我检查，使目标方法得以调用，并进行所有测试用例的检测。
package com.demo.sort.loader;
import com.demo.sort.annotation.Sort;
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import java.text.DecimalFormat;
/**
* Created with IDEA
* User: zzzz76
* Date: 2018-03-24
*/
public class TestLoader {
private static final DecimalFormat df = new DecimalFormat("0.00%");
/**
* 生成随机数组
*
* @param len
* @param range
* @return
*/
private static int[] generateArray(int len, int range) {
if (len < 1) {
return null;
}
int[] arr = new int[len];
for (int i = 0; i < len; i++) {
arr[i] = (int) (Math.random() * range);
}
return arr;
}
/**
* 输出数组
*
* @param arr
*/
private static void printArray(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
System.out.print(arr[0]);
for (int i = 1; i < arr.length; i++) {
System.out.print(", " + arr[i]);
}
System.out.println();
}
/**
* 检查是否排序
*
* @param arr
* @return
*/
private static boolean isSorted(int[] arr) {
if (arr == null || arr.length < 2) {
return true;
}
for (int i = 1; i < arr.length; i++) {
if (arr[i - 1] > arr[i]) {
return false;
}
}
return true;
}
/**
* 加载实例，完成测试
*
* @param object
*/
public static void load(Object object) {
try {
Class testClass = object.getClass();
Method[] methods = testClass.getDeclaredMethods();
for (Method method: methods) {
if (method.isAnnotationPresent(Sort.class)) {
Sort sort = method.getAnnotation(Sort.class);
System.out.println("Start test: " + sort.value());
//排序测试
int testFail = 0;
int testCount = 0;
int testPass = 0;
int len;
int range = 10;
for (int i = 0; i < 50000; ++i) {
len = (int) (Math.random() * (range + 1));
int[] arr = generateArray(len, range);
method.invoke(object, (Object) arr);
testCount++;
if (!isSorted(arr)) {
if (testFail == 0) {
System.out.println("Wrong case: ");
}
if (testFail < 5) {
printArray(arr);
}
if (testFail == 5) {
System.out.println("...");
}
testFail++;
} else {
testPass++;
}
}
System.out.println(testPass+ "/" + testCount + " " + df.format((double) testPass / testCount) + "passed
");
}
}
} catch (IllegalAccessException e) {
e.printStackTrace();
} catch (InvocationTargetException e) {
e.printStackTrace();
}
}
}
2、九大经典排序算法
冒泡排序、选择排序、插入排序
其中插入排序的时间受源数组顺序影响
package com.demo.sort;
import com.demo.sort.annotation.Sort;
import com.demo.sort.loader.TestLoader;
/**
* Created with IDEA
* User: zzzz76
* Date: 2018-03-24
*
* 题目：
* 比较排序算法A
* 时间复杂度：O(N^2)
* 空间复杂度：O(1)
*/
public class SortTestA {
public static void main(String[] args) {
TestLoader.load(new SortTestA());
}
private void swap(int[] arr, int index1, int index2) {
int tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
}
/**
* 冒泡排序
* 稳定的排序算法
*
* @param arr
*/
@Sort(value = "bubbleSort")
public void bubbleSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = arr.length - 1; i >= 0; i--) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}
/**
* 选择排序
* 不稳定的排序算法
*
* @param arr
*/
@Sort(value = "selectSort")
public void selectSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int mini = 0;
for (int i = 0; i < arr.length - 1; i++) {
mini = i;
for (int j = i + 1; j < arr.length; j++) {
mini = arr[mini] > arr[j] ? j : mini;
}
swap(arr, i, mini);
}
}
/**
* 插入排序
* 最优时间复杂度：O(N)
* 最差时间复杂度：O(N^2)
* 稳定的排序算法
*
* @param arr
*/
@Sort(value = "insertSort")
public void insertionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int index = 0;
for (int i = 1; i < arr.length; i++) {
index = i;
while (index > 0) {
if (arr[index - 1] > arr[index]) {
swap(arr, index - 1, index);
index--;
} else {
break;
}
}
}
}
}
归并排序、快速排序、堆排序、希尔排序
归并排序可以看做是后序遍历的过程，其中二叉树的叶子节点对应着数组的个数，所以归并的递归深度为logN
快速排序可以看做是前序遍历的过程，其中二叉树的总节点对应着数组的个数，递归深度为logN
堆排序建立的大/小根堆的总节点对应着数组的个数，大/小根堆的调整深度对应着二叉树的深度，递归深度为logN
package com.demo.sort;
import com.demo.sort.annotation.Sort;
import com.demo.sort.loader.TestLoader;
/**
* Created with IDEA
* User: zzzz76
* Date: 2018-03-25
*
* 题目：
* 比较排序算法B
* 时间复杂度：O(N*logN)
*/
public class SortTestB {
public static void main(String[] args) {
TestLoader.load(new SortTestB());
}
private void swap(int[] arr, int index1, int index2) {
int tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
}
private void merge(int[] arr, int left, int mid, int right) {
int[] help = new int[right - left + 1];
int l = left;
int r = mid + 1;
int index = 0;
while (l <= mid && r <= right) {
if (arr[l] <= arr[r]) {
help[index++] = arr[l++];
} else {
help[index++] = arr[r++];
}
}
while (l <= mid) {
help[index++] = arr[l++];
}
while (r <= right) {
help[index++] = arr[r++];
}
for (int i = 0; i < help.length; i++) {
arr[left + i] = help[i];
}
}
private void mergeProcess(int[] arr, int left, int right) {
if (left == right) {
return;
}
int mid = (left + right) / 2;
mergeProcess(arr, left, mid);
mergeProcess(arr, mid + 1, right);
merge(arr, left, mid, right);
}
/**
* 归并排序（后序遍历二叉树）
* 空间复杂度：O(N + logN)
* 稳定的排序算法
*
* @param arr
*/
@Sort(value = "mergeSort")
public void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
mergeProcess(arr, 0, arr.length - 1);
}
private int partition(int[] arr, int left, int right) {
int pivot = left - 1;
int index = left;
while (index <= right) {
if (arr[index] <= arr[right]) {
swap(arr, ++pivot, index);
}
index++;
}
return pivot;
}
private void quickProcess(int[] arr, int left, int right) {
if (left < right) {
int random = left + (int) (Math.random() * (right - left + 1));
swap(arr, random, right);
int mid = partition(arr, left, right);
quickProcess(arr, left, mid - 1);
quickProcess(arr, mid + 1, right);
}
}
/**
* 快速排序(前序遍历二叉树)
* 最优空间复杂度：O(logN)
* 最差空间复杂度：O(N)
* 最优时间复杂度：O(N*logN)
* 最差时间复杂度：O(N^2)
* 不稳定的排序算法
*
* @param arr
*/
@Sort(value = "quickSort")
public void quickSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
quickProcess(arr, 0, arr.length - 1);
}
private void heap(int[] arr, int head, int tail, int node) {
int leftNode = node *2+1;
int rightNode = node *2 + 2;
if (leftNode > tail) {
return;
}
int maxNode = leftNode;
if (rightNode <= tail) {
maxNode = arr[leftNode] > arr[rightNode]?leftNode:rightNode;
}
if (arr[node] < arr[maxNode]) {
swap(arr, node, maxNode);
heap(arr, head, tail, maxNode);
}
}
/**
* 堆排序
* 空间复杂度递归/迭代：O(logN)/O(1)
* 不稳定的排序算法
*
* @param arr
*/
@Sort(value = "heapSort")
public void heapSort(int[] arr) {
// write code here
// 构建最大堆
if (arr == null || arr.length < 2) {
return;
}
int n = arr.length;
for (int i = n/2 -1; i>=0;--i) {
heap(arr, 0, n-1, i);
}
for (int i = n-1; i > 0; --i) {
swap(arr, i, 0);
heap(arr, 0, i - 1, 0);
}
}
/**
* 希尔排序
* 空间复杂度：O(1)
* 不稳定的排序算法
* @param arr
*/
@Sort(value = "shellSort")
public void shellSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int feet = arr.length / 2;
int index = 0;
while (feet > 0) {
for (int i = feet; i < arr.length; i++) {
index = i;
while (index >= feet) {
if (arr[index - feet] > arr[index]) {
swap(arr, index - feet, index);
index -= feet;
} else {
break;
}
}
}
feet /= 2;
}
}
}
计数排序、基数排序
package com.demo.sort;
import com.demo.sort.annotation.Sort;
import com.demo.sort.loader.TestLoader;
/**
* Created with IDEA
* User: zzzz76
* Date: 2018-03-25
*
* 题目：
* 桶排序C
* 时间复杂度：O(N)
* 空间复杂度：O(M)
* 稳定的排序算法
*/
public class SortTestC {
public static void main(String[] args) {
TestLoader.load(new SortTestA());
}
private void swap(int[] arr, int index1, int index2) {
int tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
}
@Sort(value = "countSort")
public void countSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int min = arr[0];
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
min = Math.min(arr[i], min);
max = Math.max(arr[i], max);
}
int[] countArr = new int[max - min + 1];
for (int i = 0; i < arr.length; i++) {
countArr[arr[i] - min]++;
}
int index = 0;
for (int i = 0; i < countArr.length; i++) {
while (countArr[i]-- > 0) {
arr[index++] = i + min;
}
}
}
@Sort(value = "radixSort")
public void radixSort(int[] arr) {
// write code here
if (arr == null || arr.length < 2) {
return;
}
int n = arr.length;
int max = arr[0];
for (int i = 1; i <= n -1; ++i) {
if (max < arr[i]) {
max = arr[i];
}
}
int[] context = new int[n];
int index = 0;
for (int d = 1; max/d != 0; d *= 10) {
for (int i = 0; i <= 9; ++i) {
for (int j = 0; j <= n -1; ++j) {
if ((arr[j]/d)% 10 == i) {
context[index] = arr[j];
index ++;
}
}
}
index = 0;
for (int i = 0; i <= n - 1; ++i) {
arr[i] = context[i];
}
}
}
}