什么叫对数器呢？
我们可以通过一个事例来了解它，我们在学算法时，一般来说，会学到常见的排序算法（后面也会涉及到），我们在写完排序代码后需要对代码进行验证其正确性，比较常用的做法就是我们自己定义一个数组，然后运行我们的代码，然后我们逐一看结果是否按序排好，这种方式缺点就是不能将所有可能的情况全都覆盖，可能看起来我们的输出的结果没问题，其实在特殊情况下，可能会存在问题。对数器就是生成一个随机数组（数组大小，数组元素范围完全随机），然后将随机数组进行复制，一个数组用我们来进行排序，另一个数组我们一个绝对正确的排序算法来进行排序，将两组数据进行比较，一般来说我们会生成多个数组来进行排序，最终所有的数组排序正确才返回正确，由于数组是随机且大小、元素值都不唯一，而且数组是多组，因此如果再这种情况下返回正确的结果，那么我们就认为我们的算法是正确的。
下面给出排序算法的对数器实现：
首先，我们定义随机数组（统计学中我们可以叫做随机样本）的的实现：
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;
}然后我们定义复制数组的函数：
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;
}这个简单的实现我们可以使用java的系统函数来解决也可以：
public static int[] copyArray(int[] arr) {
if (arr == null) {
return null;
}
return Arrays.copyOf(arr,arr.length);
}下面来定义对数器的比较算法，这个也比较简单，也是调用java的系统方法：
public static void comparator(int[] arr) {
Arrays.sort(arr);
}下面定义对数器的比较算法,传入的参数就是我们已经排过序的两个数组：
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;
}同时我们需要定义我们的自己的排序实现，比如叫sort()方法
public void sort(int[] arr){
//实现逻辑
}下面定义主函数：
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);
sort(arr1);
comparator(arr2);
if (!isEqual(arr1, arr2)) {
succeed = false;
break;
}
}
System.out.println(succeed ? "Yes!" : "No!");
}
上面的主函数的意思是，我们生成随机数组的元素大小为(-100，100)之间，数组大小在[0,100），我们比较的组数是500000，如果所有结果都正确就打印输出Yes!,如果有一组不满足就直接输出No!
时间复杂度比较简单的定义，一个算法流程中，常数操作数量的指标，这个指标叫做O，big O。具体为，如果常数操作数量的表达式中， 只要高阶项，不要低阶项，也不要高阶项系数之后，剩下的部 分记为f(N)，那么该算法的时间复杂度为O(f(N))。
额外空间复杂度:是程序运行所以需要的额外消耗存储空间，比如我们申请的几个变量,我们的空间复杂度就是O(1) ,再比如，一般的递归算法就要有o(n)的空间复杂度了,简单说就是递归集算时通常是反复调用同一个方法，递归n次，就需要n个空间。
我们再来看一看稳定性：我们可以用排序简单的理解稳定性：
比如我们有如下数组：
方框里代表元素的值，底下代表元素的索引值
如果我们算法是稳定的，我们排完序的结果：
如果我们算法是不稳定的，我们排完序的结果：
我们很容易的得到定义：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。
我们需要注意的是，我们不能仅仅通代码中套了几个for(假设为m个for)循环就直接推出时间复杂度是O(N^m)。
时间复杂度O(N^2)，额外空间复杂度O(1)，实现可以做到稳定性。
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int end = arr.length - 1; end > 0; end--) {
for (int i = 0; i < end; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
}
}
}
}
/**
* 不需要申请变量（省空间）
* 位运算速度非常快
* i和j不能是一个变量，要不然最后为0
*/
public static void swap(int[] arr, int i, int j) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}时间复杂度O(N^2)，额外空间复杂度O(1)，实现可以做到稳定性
public static void insertionSort(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);
}
}
}
public static void swap(int[] arr, int i, int j) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}时间复杂度O(N^2)，额外空间复杂度O(1)，实现可以做到稳定性
public static void selectionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
}
swap(arr, i, minIndex);
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}荷兰国旗有三横条块构成，自上到下的三条块颜色依次为红、白、蓝。现有若干由红、白、蓝三种颜色的条块序列，要将它们重新排列使所有相同颜色的条块在一起。本问题要求将等于p的放在中间，小于P的放在左边，大于p的放在右边,最后返回中间位置的左边索引和右边索引。假设数组的元素只有0,1,2
public class NetherlandsFlag {
public static int[] partition(int[] arr, int l, int r, int p) {
int less = l - 1;
int more = r + 1;
while (l < more) {
if (arr[l] < p) {
swap(arr, ++less, l++);
} else if (arr[l] > p) {
swap(arr, --more, l);
} else {
l++;
}
}
return new int[] { less + 1, more - 1 };
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static int[] generateArray() {
int[] arr = new int[10];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * 3);
}
return arr;
}
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[] test = generateArray();
printArray(test);
int[] res = partition(test, 0, test.length - 1, 1);
printArray(test);
System.out.println(res[0]);
System.out.println(res[1]);
}
}运行结果：
0 2 0 2 0 0 2 1 0 1
0 0 0 0 0 1 1 2 2 2
5
6
时间复杂度O(N*logN)，额外空间复杂度O(logN)，常规实现做不到稳定 性。 注意： 1，快速排序中，额外空间复杂度最低为O(logN) 2，快速排序，可以做到稳定性的实现，但是非常难，不需要掌握 3，荷兰国旗问题的实现，和快速排序中的改进
随机快排的意义在于，我们可能选的划分值可能选择了比较大的值或者比较小的值，这就导致了时间复杂度可能达到O(N^2)
public static void quickSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int[] arr, int l, int r) {
if (l < r) {
//随机快速排序
swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
int[] p = partition(arr, l, r);
quickSort(arr, l, p[0] - 1);
quickSort(arr, p[1] + 1, r);
}
}
public static int[] partition(int[] arr, int l, int r) {
int less = l - 1;
int more = r;
while (l < more) {
if (arr[l] < arr[r]) {
swap(arr, ++less, l++);
} else if (arr[l] > arr[r]) {
swap(arr, --more, l);
} else {
l++;
}
}
swap(arr, more, r);
return new int[] { less + 1, more };
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}一个数组记为A，有序；另一个数组记为B，无序； 请打印B中的所有不在A中的数；A数组长度为N，B数组长度为M； 我们的实现时间复杂度O(M*logN) 估计一个算法流程的复杂度，需要对流程的细节彻底知晓，但是对于递 归函数，有一个重要内容：这是一个估计递归行为复杂度的公式，但是 要求递归行为中，每次递归的规模是固定的。
如何使用master公式？ T(N) = aT(N/b) + N^d
如果 1，log(b,a) > d -> T(N) 的复杂度为 N^(log(b,a)) 2，log(b,a) == d -> T(N) 的复杂度为 N^d * logN 3，log(b,a) < d -> T(N) 的复杂度为 N^d
我们上面的随机快排就可以用Master公式来进行求解时间复杂度： 我们可以很轻松的得到：T(n) = 2T(n/2)+O(n) 所以a=2,b=2,d=1 所以满足第二种，T(n)=n^dlogn=nlogn
补充阅读：http://www.gocalf.com/blog/algorithm-complexity-and-master-theorem.html
堆排序的核心是堆的建立（大根堆）和堆的调整
时间复杂度O(N*logN)，额外空间复杂度O(1)，实现不能做到稳定性 关键步骤：heapInsert, heapify，堆的扩大和缩小操作 注意： 1，堆排序中，建立堆的操作O(N),堆调整的操作时间复杂度为O(log(N)) 2，堆排序的核心数据结构：堆，也可以说是优先级队列
public static void heapSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length; i++) {
heapInsert(arr, i);
}
int size = arr.length;
swap(arr, 0, --size);
while (size > 0) {
heapify(arr, 0, size);
swap(arr, 0, --size);
}
}
public static void heapInsert(int[] arr, int index) {
while (arr[index] > arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
public static void heapify(int[] arr, int index, int size) {
int left = index * 2 + 1;
while (left < size) {
int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
largest = arr[largest] > arr[index] ? largest : index;
if (largest == index) {
break;
}
swap(arr, largest, index);
index = largest;
left = index * 2 + 1;
}
}时间复杂度O(N*logN)，额外空间复杂度O(N)，实现可以做到稳定性 注意： 1，库函数中排序的实现是综合排序，比如插入+快速；比如为了稳定性， 排序算法往往是快排+堆排序 2，归并排序和快速排序，都一定存在非递归的实现 3，归并排序，存在额外空间复杂度O(1)的实现，但是非常难，你不需要 掌握 4，归并排序的扩展，小和问题，逆序对
public static void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
mergeSort(arr, 0, arr.length - 1);
}
public static void mergeSort(int[] arr, int l, int r) {
if (l == r) {
return;
}
int mid = l + ((r - l) >> 1);
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
merge(arr, l, mid, r);
}
public static void merge(int[] arr, int l, int mid, int r) {
int[] help = new int[r - l + 1];
int s1 = l;
int e1 = mid;
int s2 = mid + 1;
int e2 = r;
int index = 0;
while (s1 <= e1 && s2 <= e2) {
help[index++] = arr[s1] > arr[s2] ? arr[s2++] : arr[s1++];
}
while (s1 <= e1) {
help[index++] = arr[s1++];
}
while (s2 <= e2) {
help[index++] = arr[s2++];
}
for (int i = 0; i < help.length; i++) {
arr[i + l] = help[i];
}
}二分查找的时间复杂度为O(logn)
public class BiSearch {
public static int biSearch(int[] arr ,int p){
int l = 0;
int r = arr.length-1;
if (arr[l]==p){
return l;
}else if (arr[r] == p){
return r;
}
while (l<r){
int mid = l+((r-l)>>1);
if (arr[mid]==p){
return mid;
}else if (arr[mid]<p){
l = mid+1;
}else {
r = mid-1;
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = {1,2,5,7,12,14,53,100};
System.out.println(biSearch(arr,2));
System.out.println(biSearch(arr,53));
System.out.println(biSearch(arr,10));
}
}运行结果：
1
6
-1