认识时间复杂度和简单的排序算法

1、选择排序：每次选择数组中的最小的数，第一轮放在数组下标为0的位置，第二轮放在数组下标为1的位置，
也就是拿数组0位置和0以后的位置比较，拿数组为1位置和1以后的位置比较，以此方法进行排序。
时间复杂度为O(n^2)

public static void selectSort(int arr[]){
        if(arr == null || arr.length < 2){
            return;
        }
        for (int i=0;i


2、冒泡排序：此排序每一次的遍历是将数组中最大的数放在数组的最后，直到所有的数排序完。

时间复杂度为O(n^2)
    //冒泡排序
    public static void bubbleSort(int arr[]){
        for(int i=0;iarr[j+1]){
                    swap(arr,j,j+1);
                }
            }
        }
    }

    public static void swap(int arr[],int i,int j){
        int temp = 0;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

3、异或运算的面试题目：
//在只有一种数为奇数的数组中，求出这个数
    public static void one(int arr[]){
        int onlyOne = 0;
        for (int ar : arr){
            onlyOne^=ar;
        }
        System.out.println(onlyOne);
    }

    //在有两种数为奇数的数组中，求出这两个数分别是什么
    public static void tow(int arr[]){
        int onlyTow = 0;
        for (int ar:arr){
            onlyTow^=ar;
        }

        int onlyTow2 = 0;
        //~按位去反运算符，此时为了求出两个奇数的第一位不同的位
        int err1 = onlyTow & (~onlyTow+1);

        for(int ar:arr){
            if((err1 & ar) ==0){
                onlyTow2^=ar;
            }
        }
        System.out.println(onlyTow2+":"+(onlyTow^onlyTow2));
    }

4、插入排序：从前往后，每次都是拿此数和它左边所有的数比较，如果小，则交换位置，再比较，直到左边没有比它小的数
public class ex {
	
	public static void insertSort(int arr[]) {
		for(int i=1;i0 && arr[j-1]>arr[j];j--) {
				sw(arr,j,j-1);
			}
		}
	}
	private static void sw(int[] arr, int j, int i) {
		arr[j] = arr[j]^arr[i];
		arr[i] = arr[j]^arr[i];
		arr[j] = arr[j]^arr[i];
	}
}

5、二分法：每次砍一半，直到直到找到对应的数

① 查找一个有序数组中的一个数：二分找到就返回
②查找一个有序数组中<=一个数的最左侧位置的数：二分到最后一个数
③对数器

认识时间复杂度和简单的排序算法

相关

标签