简单排序算法

异或运算及异或运算实现的swap方法

^(异或): ^运算是计算机中的位运算，运算规则为相同为0，不同为1（也被称为无进位相加）。位运算处理效率比常规运算符效率更高。

异或运算遵循的法则：

1.    0^N = N        N^N =0
2.    异或运算遵循 结合律与交换律     

也就是说：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;}
}

本文章根据左程云老师课程进行总结反思