[数据结构与算法]1基本排序算法

1、复杂度

1.1时间复杂度

时间复杂度是指执行某个算法所需要的计算工作量，写作T(n)=O(f(n)),当f(n)相等时，需要在相同的情况下计算具体的运行时间来比较两个算法的优劣，常见的有：

• 常数时间复杂度
• 对数时间复杂度
• 次方时间复杂度
• 线性时间复杂度
• 线性对数时间复杂度
• 质数时间复杂度

1.2空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，写作S(n)=O(f(n))。

2、异或运算

异或运算可以理解为一种无进位相加，常用规则有：

• 0 ^ N = N ; N ^ N = 0
• 交换律结合律：a ^ b = b ^ a ; (a ^ b) ^ c = a ^ (b ^ c)
• 同一组数异或结果与顺序无关

例一：一组数中，已知有一种数的出现次数为奇数，其他类型的数出现的次数为偶数，求出现次数为奇数的数。

public static int test1(int[] arr, int n) {
    int temp=0;//临时变量，用来储存异或结果
    
    for (int i=0; i<n; i++) {
        //N ^ N = 0
        temp = temp ^ arr[i];
    }

    return  temp;
}

例二：一组数中，已知有两种数的出现次数为奇数，其他类型的数出现的次数为偶数，求出现次数为奇数的两个数。

public static void test2(int[] arr, int n) {
    int temp=0;//临时变量，用来储存异或结果
    int i=0;//循环变量
    int a=0,b=0;//两个奇数

    for (i=0; i<n; i++) {
        //N ^ N = 0
        temp = temp ^ arr[i];//temp = a ^ b;
    }

    //取最左边的1
    int left = temp & ( ~temp + 1);
    //与该位为1的数相异或得到其中一个数
    for (i=0; i<n; i++) {
        if((arr[i] & left) == 1) {
            a ^= arr[i];
        }
    }
    b = a ^temp;

    System.out.println("a = "+a+"\nb = "+b);
}

3、基本排序算法

3.1选择排序

时间复杂度O(n^2)，空间复杂度O(1)，稳定排序。

	//选择排序
	public static int[] selectSort(int[] arr) {
        int n = arr.length;//数组长度
        int i,j;//循环变量
        int min;//局部最小值

        for(i = 1; i<n; i++) {
            min = i-1;
            for(j=i; j<n; j++) {
                if(arr[j]<arr[min]) {
                    min = j;
                }
            }
            if(min!=(i-1)) {
                //相加后减交换法
                arr[i-1] = arr[i-1] + arr[min];
                arr[min] = arr[i-1] - arr[min];
                arr[i-1] = arr[i-1] - arr[min];
            }
        }

        return arr;
    }

3.2冒泡排序

时间复杂度O(n^2)，空间复杂度O(1)，稳定排序。

	//冒泡排序
    public static int[] bubblingSort(int[] arr) {
        int n = arr.length;//数组长度
        int i,j;//循环变量

        for(i=0; i<n-1; i++) {
            for (j=0; j<n-i-1; j++) {
                if(arr[j]>arr[j+1]) {
                    //异或交换法
                    arr[j] = arr[j] ^ arr[j+1];
                    arr[j+1] = arr[j] ^ arr[j+1];
                    arr[j] = arr[j] ^ arr[j+1];
                }
            }
        }

        return arr;
    }

3.3插入排序

时间复杂度O(n^2)，空间复杂度O(1)，稳定排序。

	//插入排序
    public static int[] insertSort(int[] arr) {
        int n = arr.length;//数组长度
        int i,j;//循环变量
        int temp;//临时变量

        for(i=1;i<n;i++) {
            j = i;
            while(j>0&&(arr[j-1]>arr[j])) {
                temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
                j--;
            }
        }

        return arr;
    }

            arr[j] = arr[j-1];
            arr[j-1] = temp;
            j--;
        }
    }

    return arr;
}