排序算法中的通用函数与对数器

0.排序相关辅助函数(重点:对数器)

1.简单排序的交换函数[位运算版]

(注意:位运算优先级较低,复合运算的时候需要加上小括号)

位运算一般较快.（但特殊情况自己与自己交换会变为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];
}

普通版：（辅助变量temp，适合所有场景，较慢）

public static void swap(int[] arr, int i, int j) {
   int temp = arr[i] ;
   arr[i] = arr[j];
   arr[j] = temp;
}

加减版：（适合所有场景，中等，可能越界）

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];
}

2.取两数的平均值,中间值mid

普通版:(相加除2)

mid=(left +right)/2;

优化版1:(减小了越界的可能性)

mid=left +(right-left)/2;

优化版2:(位运算)

//>>右移,带符号 >>>右移,无符号 右移一位相当于/2
//注意位移运算外面的小括号,因为位运算优先级低
//位运算相对较快
int mid = left + ((right - left) >> 1);
//heapInsert中直接使用位运算计算父节点，会出现负数-1，数组下边越界
//当index=0时，parent=(index-1)/2 ；【parent=0】 parrent=(index-1)>>1;【parent=-1】
//while(index>0&&a[index]>a[((index-1)>>1)]){ //此时需要加上index>0

3.复制数组

1.直接用java系统函数

<1>copyOf(int[], int))**(int[] original, int newLength)

复制指定的数组，截取或用 0 填充（如有必要），以使副本具有指定的长度。
<2>copyOfRange(int[] original, int from, int to)
将指定数组的指定范围复制到一个新数组。

2.自写copyArray（）

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;
}

4.打印数组

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();
}

5.对数器

什么是对数器?

意义:

更快确定自写函数的正确性,直接输出错误用例,方便调试

方法:

1.写一个比较器,比较自写函数与绝对正确函数对数组处理后的结果;

2.比较次数、范围自定义后,数组长度随机,内部值随机(为方便调试,长度较小,次数多)

3.如果不同,返回false并打印不同的那次原数组和自写函数排序后的数组

4.相同则返回true.因为次数足够多,样本量足够大,所以认为正确

对数器的概念和使用
0，有一个你想要测的方法a，
1，实现一个绝对正确但是复杂度不好的方法b，
2，实现一个随机样本产生器
3，实现比对的方法
4，把方法a和方法b比对很多次来验证方法a是否正确。
5，如果有一个样本使得比对出错，打印样本分析是哪个方法出错
6，当样本数量很多时比对测试依然正确，可以确定方法a已经正确。

比较器:比较两数组是否相等

<1>系统函数.equals

Arrays.equals(int[] a,int[] a2)

<2>自写比较

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;

生成器:生成随机数组

public static int[] generateRandomArray(int maxSize, int maxValue) {
    //长度在自定义范围内随机
   int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
    //数值在自定义范围内随机;可0,负数,正数
   for (int i = 0; i < arr.length; i++) {
      arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
   }
   return arr;
}

对数器使用:不同返回false和相应用例

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);
   bubbleSort(arr1);
   comparator(arr2);
   if (!isEqual(arr1, arr2)) {
      succeed = false;
      break;
   }
   if (succeed = false) {
      //原数组,出错测试数据
      printArray(arr3);
      //排错"后数组
      printArray(arr1);
      //"绝对正确"数组"
      printArray(arr2);
   }
}
System.out.println(succeed ? "Nice!" : "***ing ***ed!");