手寫常見排序算法
1.交換函數(shù)（異或運(yùn)算寫法）
因?yàn)橐獙懗Ｓ门判蚴蚕妫钥隙〞玫浇粨Q函數(shù)长赞，下面就是交換函數(shù)的一種位運(yùn)算寫法（給新手小白的說明，老手勿看）
public class Algorithm {
public static void swap(int[] arr, int i, int j){
if (i != j){ //防止交換地址相同的數(shù)據(jù) （地址相同的數(shù)據(jù) 在進(jìn)行異或運(yùn)算時(shí) 會變成0）
//異或運(yùn)算 實(shí)現(xiàn)交換（不用開辟額外空間闽撤，位運(yùn)算速度較快）
//可以這么理解 已知 a = arr[i] b = arr[j],
//因?yàn)?是異或操作所以
//有這些結(jié)論 ：a ^ a =0 , a ^ 0 = a , b ^ b = 0 ,b ^ 0 = b
arr[i] = arr[i] ^ arr[j]; //相當(dāng)于 a = a^b
arr[j] = arr[i] ^ arr[j]; //相當(dāng)于 b = (a^b) ^ b 因?yàn)? 異或操作滿足結(jié)合律得哆，所以:b = a^(b^b) ;
// 又因?yàn)?b^b = 0; 所以：b = a ^ 0;又因?yàn)椋篴 ^ 0 = a 所以：b = a;
arr[i] = arr[i] ^ arr[j]; //相當(dāng)于 a = (a^b) ^ ( (a^b)^b ) 所以這也就相當(dāng)于 a = (a^b) ^ a;
// 同理因?yàn)? 異或操作滿足交換律 所以：a = (b^a) ^ a ;
//又因?yàn)?異或操作滿足結(jié)合律 ，所以：a = b ^(a^a);
//又因?yàn)?a^a = 0; 所以 a= b^ 0哟旗；又因?yàn)椋篵^0 =b 所以： a = b;
//以上就是交換函數(shù)原理
}
}
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);
}
//交換函數(shù)
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];
}
}
//測試主函數(shù)
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);
}
}
}
