排序算法

2022-08-07 09:21:36

基础排序算法

前置方法:数组元素交换方法

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

//位运算的数组元素交换
//使用前提：确保交换的俩个元素的位置不同，如果相同，会异或成0
public void swap2(int i,int j,int[] arr){ //以甲，乙作为值进行解释 a=甲，b=乙
    arr[i] = arr[i]^arr[j]; //a= 甲^乙  b = 乙
    arr[j] = arr[i]^arr[j]; //a = 甲^乙  b = 乙 ^ a = 乙^甲^乙=甲
    arr[i] = arr[i]^arr[j]; //a = 甲 ^ b = 甲^乙^甲 = 乙  b = 甲
}

1、冒泡排序

算法逻辑：进行嵌套循环，循环比较，当遇到比当前值大/小的值时，交换数组元素位置。

代码：

public int[] bubbleSort(int[] arr){
    if(arr==null || arr.length<2) return arr;
    for(int i=0; i<arr.length; i++){
        for(int j=i; j<arr.length; j++)
            if(arr[i]>arr[j]) swap(i,j,arr);
    }
    return arr;
}

2、选择排序

算法逻辑：进行嵌套循环比较，每次比较，获取值最小的元素的位置，最后进行位置交换

代码：

public int[] selectSort(int[] arr){
    if(arr==null || arr.length<2) return arr;
    for(int i=0; i<arr.length; i++){
        int minIndex = 0;
        for(int j=0; j<arr.length; j++){
            minIndex = arr[i]<arr[j]?i:j;
        }
        swap(i,j,arr);
    }
    return arr;
}

3、插入排序

算法逻辑：数组元素逐个加入排序，将已放入的数组元素完成排序

代码:

public int[] insertSort(int[] arr){
    if(arr == null|| arr.length<2) return arr;
    for(inti=0; i<arr,length; i++){
        for(int j=i-1; j>0; j--){
            if(arr[j]>arr[j+1]) swap(j,j-1,arr);
        }
    }
}

4、归并排序

算法逻辑：将数组分为俩个部分，在俩个部分分别完成排序，再将俩个部分进行合并

代码：

public int[] megreSort(int[] arr){
    if(arr==null||arr.length<2)return arr;
    arr = process(arr,0,arr.length-1);
    return arr;
}
//使用递归将数组分为俩个部分
public int[] process(int[] arr,int L,int R){
    if(L==R) return arr;
    int mid = L+((R-L)>>1); //求中位数
    arr = process(arr,L,mid);
    arr = process(arr,mid+1,R);
    arr = merge(arr,L,min,R);//合并排序
}
//将俩部分根据值大小进行合并
public int[] merge(int[] arr,int L,int Mid,int R){
    int[] tmp = new int[R-L+1];
    int index = 0,p1 = L,p2 = mid+1;
    while(p1<=mid&&p2<=R) tmp[index++] = arr[p1]<arr[p2]?arr[p1++]:arr[p2++];
    while(p1<=mid) tmp[index++] = arr[p1++];
    while(p2<=R) tmp[index++] = arr[p2++];
    for(int i=0; i<tmp.length; i++) arr[L+i] = tmp[i];
    return arr;
}

5、快速排序

算法逻辑：随机取数组中的一个数，将数组氛围，大于区，小于区和等于区，完成分区后，在大于区和小于区，递归重复执行，直至完成排序。

代码：

public int[] quickSort(int[] arr,int L,int R){
    if(L<R){
        swap(L+(int)(Math.random()*(R-L+1)),R,arr); //随机选择一个数作为参考数，交换至最后
        int[] subScript = partition(arr,L,R);
        quickSort(arr,L,subScript[0]-1);
        quickSort(arr,subScript[1]+1,R);
    }
    return arr;
}
//区分大小区域
public int[] partition(int[] arr,int L,int R){
    int less = -1;
    int more = R; //以最后一个数作为参考数区分大小区
    while(L<more){
        //当前数小参考数，小于区域的的下一个值交换位置，将当前的下标+1，进行下一个数的比较
        if(arr[L]<arr[R]) swap(++lese,L++,arr);
        //当前数大于参考数数，大于区域的上一个位置交换位置，由于交换过去的数需要继续比较，所以下标不变
        else if(arr[L]>arr[R]) swap(--more,L,arr);
        else L++;
    }
    swap(morem,R,arr); //将参考数交换回中间等于区域
    return new int[]{less+1,more} //返回大小区域的区间值
}

6、堆排序(相比于堆排序，堆结构更为重要)

算法逻辑：将数组形成大根堆，此时根节点为最大值，取出这个元素，其余元素重新形成大根堆，重复执行，直至排序完成;

代码：

//堆排序
public int[] heapSort(int[] arr){
    if(arr==null||arr.length<2) return arr;
    //写法一：逐个加入数组元素形成大根堆
    //for(int i=0; i<arr.length; i++) heapInsert(arr,i);
    //写法二：整个数组加入形成大根堆
    for(int i = arr.length-1; i>=0; i--) heapIfy(arr,i,arr.length);
    int heapSize = arr.lenght;
    swap(0.--heapSize,arr); //形成大根堆，根节点为最大，不需要参加下来的排序
    while(heapSize>0){ //循环执行形成大根堆和取出根节点
        heapIfy(arr,0,heapSize);
        swap(arr,0,--heapSize)
    }
    return arr;
}
//逐个加入元素，形成大根堆
public void heapInsert(int[] arr,int index){
    //新进来的数组元素，要与其父节点进行比较，若大于新元素，交换位置，再继续与其新节点比较，直至比父节点小
    while(arr[index]>arr[(index-1)/2]){
        swap(index,(index-1)/2,arr);
        index = (index-1);
    }
}
//从指定位置开始形成大根堆
public void heapIfy(int[] arr,int index,int heapSize){
    int leftIndex = index*2+1;//左孩子的位置
    while(leftIndex<heapSize){
        //判断是否有右节点
        //将左右节点中较大的节点拿取出来
        int lagrest = leftIndex+1<heapSize && arr[leftIndex]>arr[leftIndex+1]:leftIndex:leftIndex+1;
        lagrest = arr[lagrest]>arr[index]?lagrest:index;
        if(lagres==index) break; //父节点已经是最大了
        swap(lagres,index,arr);
        index = lagrest;
        leftIndex = index*2-1;
    }
}

7、桶排序

算法逻辑：依照元素的位数进行进桶和出桶

代码：

//桶排序
public int[] bucketSort(int[] arr){
    int digit = getMaxDigit(arr);
    arr = rediSort(arr,0,arr.length-1,digit);
    return arr;
}
public void reidSort(int[] arr,int L,int R,int digit){
    int radix = 10; //初始化桶的数量
    int i=0,j=0;
    int[] bucket = new int[R-L+1];
    for(int d=1; d<=digit; d++){ //最大的数有多少位数，就得进桶多少次
        int count = new int[radix]; //辅助数组
        for(i=L; i<=R; i++){ //统计位数上一个数出现的次数
            j = getDigit(arr[i],d);
            count[j]++;
        }
        for(i=1; i<radix; i++) count[i] = count[i]+count[i-1]; //进桶
        for(i=R; i>=L; i--){ //出桶
            j = getDigit(arr[i],d);
            bucket[count[j]-1] = arr[i];
            count[j]--;
        }
        for(i=L,j=0; i<=R; i++,j++) arr[i] = bucket[i]; //根据出桶顺序调整数组顺序
    }
    return arr;
}
//获取最多位数的位数大小
public int getMaxDigit(int[] arr){
    int max = Integer.MIN_VALUE;
    for(int number:arr) max = max>number?max:number;
    int res = 0;
    while(max!=0){
        res++;
        max/=10;
    }
}
//获取位数上的数
public int getDigit(int x,int d)[
    return ((x/(int)(Math.pow(10,d-1)))%10);
]

码农公寓