位置：首页-资讯-后端开发

Java数据结构之基于比较的排序算法基本原理及具体实现

2024-04-02 19:55

短信预约 -IT技能 免费直播动态提醒

1. 七大基于比较的排序-总览

1.1常见基于比较的排序分类

在这里插入图片描述

1.2时间复杂度，空间复杂度以及稳定性。

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。

2.直接插入排序

2.1 直接插入排序的基本思想

直接插入排序的基本思想，就是每次选取一个待排序元素，按照一定规定插入到前面已经排好序的一组元素的适当位置。当每个元素都插入完毕，整个序列已经有序。

当插入第i(i >= 1)时，前面的V[0]，V[1]，……，V[i-1]已经排好序。这时，用V[I]的排序码与V[i-1]，V[i-2]，…的排序码顺序进行比较，找到插入位置即将V[i]插入，原来位置上的元素向后顺移。

2.2 直接插入排序动画演示

在这里插入图片描述

2.3 代码示例


public static void insertSort(int[] arr){
        for(int i=1;i<arr.length;i++){//从第二个元素开始，遍历整个数组
            int j=i-1;//i之前的序列 已经有序
            int temp=arr[i];
            for(;j>=0;j--){//此循环用于寻找插入位置
                if(arr[j]>temp){//此时逐个向后移动元素
                    arr[j+1]=arr[j];
                }else break;//找到插入位置 直接break
            }
            arr[j+1]=temp;//直接插入
        }
}

2.4 时间复杂度，空间复杂度以及稳定性

时间复杂度最坏情况：数组整体逆序O(n^2);
时间复杂度最好情况：数组已经有序O(n^2);
空间复杂度:O(1);
稳定性：稳定;

3. 希尔排序

3.1 算法思想

希尔排序是特殊的插入排序，直接插入排序每次插入前的遍历步长为1，而希尔排序是将待排序列分为若干个子序列，对这些子序列分别进行直接插入排序，当每个子序列长度为1时，再进行一次直接插入排序时，结果一定是有序的。常见的划分子序列的方法有：初始步长（两个子序列相应元素相差的距离）为要排的数的一半，之后每执行一次步长折半。

3.2 图片演示

3.3 代码示例


public static void hell(int[] arr,int gap){//当gap=1时 其实就是直接插入排序
        for(int i=gap;i<arr.length;i++){
            int j=i-gap;
            int temp=arr[i];
            for(;j>=0;j-=gap){
                if(arr[j]>temp){
                    arr[j+gap]=arr[j];
                }else break;
            }
            arr[j+gap]=temp;
        }
}
public static void hellSort(int[] arr){
        int gap=arr.length;
        while(gap>1){
            gap=gap/2+1;
            hell(arr,gap);
        }
    }

3.4 时间复杂度，空间复杂度以及稳定性

时间复杂度最好：O(n);
时间复杂度最坏：O(n^1.5);
时间复杂度平均：O(n^1.3);
空间复杂度：O(1);
稳定性：不稳定;

4.选择排序

4.1 算法思想

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

4.2 动画演示

4.3 代码示例


public static void selectSort(int[] arr){
        for(int i=0;i<arr.length;i++){
            for(int j=i+1;j<arr.length;j++){
                if(arr[j]<arr[i]){
                    int temp=arr[j];
                    arr[j]=arr[i];
                    arr[i]=temp;
                }
            }
      }
}

4.4 时间复杂度，空间复杂度以及稳定性

时间复杂度最好：O(n);
时间复杂度最坏：O(n^2;
时间复杂度平均：O(n^2);
空间复杂度：O(1);
稳定性：不稳定;

5.堆排序

5.1 算法思想

堆

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：

将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

5.2 动画演示

5.3 代码示例


public static void heapSort(int[] arr){//排序方法
        creatHeap(arr);
        int end=arr.length-1;
    //因为是大根堆，所以根节点值为最大值，根节点与最后一个节点值交换 输出并删除此时最后一个节点，然后向下调整根节点
        while(end>0){
            int temp=arr[0];
            arr[0]=arr[end];
            arr[end]=temp;
            shiftDown(arr,0,end);
            end--;
        }

    }
public static void creatHeap(int[] arr){//建堆
        for(int parent=(arr.length-1-1)/2;parent>=0;parent--){
            shiftDown(arr,parent,arr.length);
        }
    }
public static void shiftDown(int[]arr,int root,int len){//向下调整操作
        int parent=root;
        int child=parent*2+1;
        while(child<len){
            if(child+1<len&&arr[child]<arr[child+1]){//待调整节点右子树大于左子树
                child++;
            }
            if(arr[child]>arr[parent]){//由于是大根堆，如果儿子节点值大于父亲节点就交换
                int temp=arr[parent];
                arr[parent]=arr[child];
                arr[child]=temp;
                parent=child;//继续向下调整，防止调整后不满足大根堆的条件
                child=parent*2+1;
            }else break;
        }
    }

5.4 时间复杂度，空间复杂度以及稳定性

时间复杂度最好：O(nlogn);
时间复杂度最坏：O(nlogn);
时间复杂度平均：O(nlogn);
空间复杂度：O(1);
稳定性：不稳定;

6.冒泡排序

6.1 算法思想

比较两个相邻的元素，将值大的元素交换到右边

思路：依次比较相邻的两个数，将比较小的数放在前面，比较大的数放在后面。

1.第一次比较：首先比较第一和第二个数，将小数放在前面，将大数放在后面。
2.比较第2和第3个数，将小数放在前面，大数放在后面。
3.如此继续，知道比较到最后的两个数，将小数放在前面，大数放在后面，重复步骤，直至全部排序完成
4.在上面一趟比较完成后，最后一个数一定是数组中最大的一个数，所以在比较第二趟的时候，最后一个数是不参加比较的。
5.在第二趟比较完成后，倒数第二个数也一定是数组中倒数第二大数，所以在第三趟的比较中，最后两个数是不参与比较的。
6.依次类推，每一趟比较次数减少依次

6.2 动画演示

6.3 代码示例


public static void bubbleSort(int[] arr){
        for(int i=0;i<arr.length-1;i++){//外层循环控制趟数
            boolean flag=false;//一个标记进行优化
            for(int j=0;j<arr.length-1-i;j++){//内层循环控制比较次数
                if(arr[j]>arr[j+1]){
                    int temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                    flag=true;
                }
            }
            if(flag==false) break;//如果一趟循环走完没有交换，说明已经有序，直接break
        }
    }

6.4 时间复杂度，空间复杂度以及稳定性

时间复杂度最好：O(n);
时间复杂度最坏：O(n^2);
时间复杂度平均：O(n^2);
空间复杂度：O(1);
稳定性：稳定

7.快速排序（十分重要）

7.1 算法思想

我们从数组中选择一个元素，我们把这个元素称之为中轴元素吧，然后把数组中所有小于中轴元素的元素放在其左边，所有大于或等于中轴元素的元素放在其右边，显然，此时中轴元素所处的位置的是有序的。也就是说，我们无需再移动中轴元素的位置。

从中轴元素那里开始把大的数组切割成两个小的数组(两个数组都不包含中轴元素)，接着我们通过递归的方式，让中轴元素左边的数组和右边的数组也重复同样的操作，直到数组的大小为1，此时每个元素都处于有序的位置。

7.2 动画演示

7.3 代码示例


//该代码参考acwing创始人yxc的快排模板
public static void quickSort(int[] arr,int l,int r){
        if(l>=r) return;//每次判断传进来左右下标
        int i=l-1,j=r+1;//因为在循环中，要先i++，j--所以i，j定义为两边界偏移1
        int x=arr[(l+r)/2];//取x为数组中间位置数
        while(i<j){
            do i++;while(arr[i]<x);
            do j--;while(arr[j]>x);
            //此时i指向的数字大于中轴数字， j指向数字小于中轴数字 交换
            if(i<j){
                int temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
            }
        }
        quickSort(arr,l,j);//退出循环是i==j 递归排序
        quickSort(arr,j+1,r);
    }

7.4 时间复杂度，空间复杂度以及稳定性

时间复杂度最好：O(nlog2n);
时间复杂度最坏：O(n^2);
时间复杂度平均：O(nlog2n);
空间复杂度：O(nlog2n);
稳定性：不稳定;

8.归并排序

8.1 算法思想

将一个大的无序数组有序，我们可以把大的数组分成两个，然后对这两个数组分别进行排序，之后在把这两个数组合并成一个有序的数组。由于两个小的数组都是有序的，所以在合并的时候是很快的。

通过递归的方式将大的数组一直分割，直到数组的大小为 1，此时只有一个元素，那么该数组就是有序的了，之后再把两个数组大小为1的合并成一个大小为2的，再把两个大小为2的合并成4的 …… 直到全部小的数组合并起来。

8.2 动画演示

8.3 代码示例


public static void mergerSort(int[]arr){
        mergerSortInternal(arr,0,arr.length-1);
    }
public static void mergerSortInternal(int[]arr,int l,int r) {//
        if (l >= r) return;
        int mid = (l + r) / 2;//把数组分为两个
        mergerSortInternal(arr, l, mid);//对左边数组递归排序
        mergerSortInternal(arr, mid + 1, r);//对右边数组递归排序
        merge(arr,l,mid,r);//排序完成，进行合并
    }
 public static void merge(int[]arr,int low,int mid,int high){
        int s1=low;//mid左侧数组的头和尾
        int e1=mid;
        int s2=mid+1;//mid右侧数组的头和尾
        int e2=high;
        int[]temp=new int[high-low+1];//定义一个数字，用来合并他们
        int k=0;//指示数组下标
        while(s1<=e1&&s2<=e2){//选出两侧数组最小元素 插入temp数组
            if(arr[s1]<=arr[s2]) temp[k++]=arr[s1++];
            else temp[k++]=arr[s2++];
        }
        while(s1<=e1) temp[k++]=arr[s1++];//如果一侧数组插入完毕，另一侧还有剩余，则全部插入
        while(s2<=e2) temp[k++]=arr[s2++];
        for(int i=0;i<temp.length;i++){//返还到arr数组
            arr[i+low]=temp[i];
        }
    }
}