手写常见排序算法
1.交换函数（异或运算写法）
因为要写常用排序，所以肯定会用到交换函数，下面就是交换函数的一种位运算写法（给新手小白的说明，老手勿看）
对应的贴图版本：手写常见排序算法(冒泡排序，选择排序，插入排序，快速排序) 贴图板
public class Algorithm {
public static void swap(int[] arr, int i, int j){
if (i != j){ //防止交换地址相同的数据 （地址相同的数据 在进行异或运算时 会变成0）
//异或运算 实现交换（不用开辟额外空间，位运算速度较快）
//可以这么理解 已知 a = arr[i] b = arr[j] ,因为 是异或操作所以有这些结论 ：a ^ a =0 , a ^ 0 = a , b ^ b = 0 ,b ^ 0 = b
arr[i] = arr[i] ^ arr[j]; //相当于 a = a^b
arr[j] = arr[i] ^ arr[j]; //相当于 b = (a^b) ^ b 因为: 异或操作满足结合律，所以:b = a^(b^b) ;又因为 b^b = 0; 所以：b = a ^ 0;又因为：a ^ 0 = a 所以：b = a;
arr[i] = arr[i] ^ arr[j] //相当于 a = (a^b) ^ ( (a^b)^b ) 所以这也就相当于 a = (a^b) ^ a; 同理因为: 异或操作满足交换律 所以：a = (b^a) ^ a ;又因为 异或操作满足结合律 ，所以：a = b ^(a^a);又因为 a^a = 0; 所以 a= b^ 0；又因为：b^0 =b 所以： a = b;
以上就是交换函数原理
}
}
2.冒泡排序，选择排序，插入排序，快速排序的写法
public class algorithm {
//冒泡排序
public static void bubblingSort(int[] arr){
for(int i = 1; i < arr.length; i++){
for(int j = 0; j < arr.length - i; j++){
if(arr[j] > arr[j+1]){
swap(arr,j,j+1);
}
}
}
}
//选择排序
public static void selectSort(int[] arr){
for(int i = 1; i < arr.length; i++){
int maxIndex = arr.length-i;
for (int j = 0; j < arr.length - i; j++){
maxIndex = arr[j] > arr[maxIndex] ? j : maxIndex;
}
swap(arr,maxIndex,arr.length-i);
}
}
//插入排序
public static void insertSort(int[] arr){
for(int i = 1; i < arr.length; i++){
for(int j = i; j > 0 && arr[j] < arr[j-1]; j--){
swap(arr,j,j-1);
}
}
}
//快速排序
public static void quickly(int[] arr, int leftIndex, int rightIndex){
if(leftIndex >= rightIndex){
return;
}
int left = leftIndex;
int right = rightIndex;
int norm = arr[right];
while(left < right){
while (left < right && arr[left] <= norm){
left++;
}
arr[right] = arr[left];
while (right < left && arr[right] >= norm){
right--;
}
arr[left] = arr[right];
}
arr[right] = norm;
quickly(arr,right + 1, rightIndex);
quickly(arr, leftIndex, left - 1);
}
//交换函数
public static void swap(int[] arr, int i, int j){
if(i != j){
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
}
//测试主函数
public static void main(String[] args){
int[] arr = {0,1,1,5,24,25,56,85,647,8536,7445,89,644,0};
//bubblingSort(arr);
//quickly(arr,0,arr.length - 1);
//insertSort(arr);
selectSort(arr);
for (int i : arr){
System.out.println("i = " + i);
}
}
}
