简单排序算法
异或运算及异或运算实现的swap方法
^(异或): ^运算是计算机中的位运算，运算规则为相同为0，不同为1（也被称为无进位相加）。位运算处理效率比常规运算符效率更高。
异或运算遵循的法则：
- 0^N = N N^N =0
- 异或运算遵循 结合律与交换律
也就是说：a^a^b=b
swap方法的两种实现
常规交换（推荐）
public void swap(int[] arr,int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}^交换(前提要求是，arr[i]与arr[j]内存地址不同)
public 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];
} 异或常见题
1.在一个数组中有一种数是奇数次，其他数都是偶数次如何找出奇数次这种数[1,2,2,1,1,1,3,3,3]，奇数次数为3
思路：1.因为异或操作满足交换律所以数组可以写为 [1,1,1,1,2,2,3,3,3]
2.异或的特性 1^1 = 0 ;1^0=1 所以偶数项就消掉了，只剩下一个奇数项了
public void problem1(int[] arr){
int eor = 0; // 0^i = i;
for(int i:arr){
eor ^= i;
}
System.out.println("奇数项的数为："+eor);
}2.在一个数组中有两种数是奇数次，其他数都是偶数次如何找出奇数次这种[1,2,2,1,4,4,1,4,1,3,3,3] 奇数次数为3，4
思路：1.数组所有数异或出来的结果肯定是 a^b 其中 a b必定是奇数项
2.因为a与b又不相等，所以a^b的结果在2进制上某一位也比不相等(值称为rightOne，rightOne 二进制表达为 0000 0100这种有规律的结构)
3.将数组划分为两个空间，^rightOne的值被分为a所在区间或者b所在区间(根据结果等于1或者0判断)，但是在这个区间里面只有a或者b 不存在a，b同时存在的情况。
4.找到a 又知道a^b 所以 a^a^b = b a、b两个结果都被求解出来了
public void problem2(int[] arr){
int eor = 0;
for(int i:arr){
eor ^=i;
}
int rightOne = eor & (~eor + 1);//a^b 源码与补码进行 &操作 结果为 最右边二进制不相等的位次
int resultA = 0;
for(int i:arr){
if(i^rightOne = 1){//区间划分
resultA ^=i;
}
}
int resultB = eor^resultA;
System.out.println("{"+resultA +","+resultB +"}");
}选择排序
public int[] selectSort(int[] arr){
for(int i = 0;i < arr.length-1;i++){ //该for循环保证在第i个位置上是[i,N]位置上的最小数
int minIndex = i;
for(int j = i+1;j < arr.length-1;j++){//保证当前位置为整个数组最小值
minIndex = arr[i] > arr[j] ? j : minIndex;
}
swap(arr,i,minIndex);
}
}
//交换方法
public void swap(int[] arr,int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}冒泡排序
public int[] bubbleSort(int[] arr){
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);
}
}
}
return arr;
}插入排序
public int[] insertSort(int[] arr){
for(int i = 1;i < arr.length;i++){//0-i位置上有序
//向左判断数组大小，如果当前位置小于前一个位置进行交换
for((int j = i-1;j >= 0 && arr[j] > arr[j+1];j--){
swap(arr,j,j+1);
}
}
}对数器
什么是对数器，对数器指的是在没有OJ平台（在线程序测评系统）时自测的一种方式。实现原理就是生成随机数据。例如：数组长度随机，数据随机的数组。将两套算法结果进行对比，如果全部相同说明算法正确。（其中一种算法是否正确未知，另一种算法为暴力解法这种容易想并且不会错的座位对比项）
package com.example.math;
import java.util.Arrays;
/**
* @author geekYang
* @version 1.0
* @since 1.0
*/
public class 对数器 {
public static void main(String[] args) {
int maxSize = 100;
int maxValue = 100;
int testTotal = 50000;//测试次数
boolean succed = true;
for (int i = 0; i < testTotal; i++) {
int[] arr1 = generateRandomArr(maxSize, maxValue);
int[] arr2 = Arrays.copyOf(arr1, arr1.length);
comparator(arr1);
insertSort(arr2);
if (!Arrays.equals(arr1, arr2)) {
succed = false;
break;
}
}
System.out.println(succed ? "Nice" : "Fucking fucked!");
}
//生成随机数组方法
public static int[] generateRandomArr(int maxSize, int maxValue) {
//(int) ((maxSize + 1) * Math.random()) 生成随机[0,maxSize]范围的数
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i : arr) {
arr[i] = (int) ((maxSize + 1) * Math.random()) - (int) ((maxSize + 1) * Math.random());
}
return arr;
}
//对比方法
public static int[] comparator(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length - 1; j++) {
minIndex = arr[i] > arr[j] ? j : minIndex;
swap(arr, j, minIndex);
}
}
return arr;
}
//测试方法
public static int[] insertSort(int[] arr) {
for (int i = 1; i < arr.length - 1; i++) {
for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
swap(arr, j, j + 1);
}
}
return arr;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
本文章根据左程云老师课程进行总结反思