简单的排序算法

一、异或运算

排序算法一般都涉及交换元素，所以这里首先介绍一下异或运算

核心

n ^ 0 = n;
n ^ n = 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];
}

根据核心解决两问题

1、一组数中只有一种数出现奇数次（其他数出现偶数次）,求这个数

基本思路

• 全部进行异或运算
• 出现偶数次的数异或之后结果为0，奇数次数异或后为该数本身
• 再与0异或，还是该数本身。

实现代码

public static int getOddTimesNum1(int[] arr){
    int eor = 0;
    for(int cur : arr){
        eor ^= cur;
    }
    return eor;
} 

2、一组数中只有两种数出现奇数次（其他数出现偶数次）,求这两个数

设两数为a、b，a!=b

基本思路

• 全部进行异或运算，出现偶数次的数异或之后结果为0，奇数次数异或后为该数本身
• 结果即为a ^ b，记为eor
• 则eor必定不为0，且eor的二进制位中，为1的这一位，表示a、b在这一位不同，记为rightOne
• 那么将数组中rightOne为1（或0）的这组数进行异或，就可得到a（或者b）
• 再与eor进行异或，即可得到另一个数

代码实现

public static void getOddTimesNum2(int[] arr){
    int eor = 0;
    for(int cur:arr){
        eor ^= cur;
    }
    //上面执行完后eor = a ^ b
    //获得eor二进制位最右边的1（其他位都为0）
    int rightOne = eor ^ (~eor + 1);//取反+1，再与自己异或
    int onlyOne = 0;
    for(int cur:arr){
        //与rightOne进行按位与结果不为0，说明这个数在rightOne的同一位置都为1
        if((rightOne & cur) != 0){
            //将这些数异或运算
            onlyOne ^= cur;
        }
    }
    System.out.println("其中一个数="+onlyOne);
    System.out.println("另一个数="+onlyOne ^ eor);
}

二、冒泡排序

时间复杂度

• 平均：O(n^2)
• 最好：O(n)
• 最差：O(n^2)

额外空间复杂度

O(1)

稳定性

稳定

基本思路

• 从前往后（或从后往前），比较前一个数和后一个数，满足交换条件则交换这两个数
• 这样一次遍历就可确定一个数的位置（当前区域最大值或最小值）
• 一次遍历后遍历的区域就减小1
• 直到遍历完或当前区域遍历完成后没有进行交换，排序完成。

实现代码

public static void bubbleSort(int[] arr){
    if(arr == null || arr.length < 2) return;
    
    for(int i = 0; i < arr.length; i++){
        //记录一次遍历中交换的次数
        int count = 0;
        for(int j = 0; j < arr.length-1-i; j++){
            if(arr[j] > arr[j+1]){
                swap(arr,j,j+1);
                count++;
            }
        }
        if(count == 0) return;
    }
}
public static void swap(int[] arr, int i, int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

三、选择排序

时间复杂度

• 平均：O(n^2)
• 最好：O(n^2)
• 最差：O(n^2)

额外空间复杂度

O(1)

稳定性

不稳定

基本思路

• 一次遍历找出当前区域最小值（或最大值）的位置，将此位置与当前区域的起始位置进行交换
• 则一次遍历确定了一个元素的位置，遍历区域减小1
• 直至遍历区域为0

实现代码

public static void selectionSort(int[] arr){
    if(arr == null || arr.length < 2) return;
    for(int i = 0; i < arr.length; i++){
        //记录当前区域最小值位置
        int minIndex = i;
        for(int j = i+1; j < arr.length; j++){
            minIndex = arr[j] < arr[min]?j:minIndex; 
        }
        swap(arr,i,minIndex);
    }
}
public static void swap(int[] arr, int i, int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

四、插入排序

时间复杂度

• 平均：O(n^2)
• 最好：O(n)
• 最差：O(n^2)

额外空间复杂度

O(1)

稳定性

稳定

基本思路

• i从1开始，到end结束
• 首先比较i和它前面位置的数，是否排好序，没有就交换这两位置的数
• 然后按上面规则往前比较，直至到达起始位置0，或者是没有发生交换
• 满足上述条件说明0到i位置已经排好序

代码实现

public static void insertionSort(int[] arr){
    if(arr == null || arr.length < 2) return;
    for(int i = 1; i<arr.length; i++){
        for(int j = i-1; j >= 0; j--){
            if(arr[j] > arr[j+1]){
                swap(arr,j,j+1);
            }else{
                break;
            }
        }
    }
}
public static void swap(int[] arr, int i, int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}