欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java基础—选择排序(选择排序,堆排序)

程序员文章站 2022-06-24 18:29:44
1.选择排序原理:每一次从无序区间选出最大(或最小)的一个元素,存放在无序区间的最后(或最前),直到全部待排序的数据元素排完 。稳定性(不稳定)​ 1.一个稳定的排序可以变成不稳定的排序;​ 2.一个本身就不稳定的是不可能变成稳定的;空间复杂度:O(1)时间复杂度:O(O(n^2))public static void selectsort(int[] arr){ for (int i =0;i < arr.length;i++...

1.选择排序

  • 原理:每一次从无序区间选出最大(或最小)的一个元素,存放在无序区间的最后(或最前),直到全部待排序的数据元素排完 。

  • 稳定性(不稳定)
    ​ 1.一个稳定的排序可以变成不稳定的排序;
    ​ 2.一个本身就不稳定的是不可能变成稳定的;

  • 空间复杂度:O(1)

  • 时间复杂度:O(O(n^2))

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[i] > arr[j]){
                    int tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
    }

2.堆排序

  • 稳定性(不稳定)
    ​ 1.一个稳定的排序可以变成不稳定的排序;
    ​ 2.一个本身就不稳定的是不可能变成稳定的;

  • 空间复杂度:O(1)

  • 时间复杂度:O(n*logn)

public static void heapsort(int[] arr){
        //首先将数组元素放入一个堆
        createheap(arr);

        int end = arr.length-1;//因为后面要将堆头和最后一个元素交换位置
        while(end > 0){
            int tmp = arr[0];
            arr[0] = arr[end];
            arr[end] = tmp;
            adjustDown(arr,0,end);//调用向下调整方法重新构造大根堆
            end--;//构造完之后,将最后一个元素去掉
        }
    }
    //构造一个堆
    public static void createheap(int[] arr){
        for(int i =(arr.length-1-1)/2;i >= 0;i--){
            adjustDown(arr,i,arr.length);
        }
    }
    //向下调整方法
    public static void adjustDown(int[] arr,int parent,int len){
        //计算左孩子节点下标
        int child = 2*parent+1;
        while(child < len){
            //左右孩子选择最大的
            if(child+1 < len && arr[child] < arr[child+1]){
                child++;
            }
            //到了这一步,已经找到最大的孩子,和双亲进行比较
            if (arr[child] > arr[parent]){
                int tmp = arr[child];
                arr[child] = arr[parent];
                arr[parent] = tmp;
                parent = child;
                child = 2*parent+1;
            }else{
                break;
            }
        }
    }

3.俩个代码结果测试

public class TestSort {
//选择排序
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[i] > arr[j]){
                    int tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
    }
//堆排序
public static void heapsort(int[] arr){
        //首先将数组元素放入一个堆
        createheap(arr);

        int end = arr.length-1;//因为后面要将堆头和最后一个元素交换位置
        while(end > 0){
            int tmp = arr[0];
            arr[0] = arr[end];
            arr[end] = tmp;
            adjustDown(arr,0,end);//调用向下调整方法重新构造大根堆
            end--;//构造完之后,将最后一个元素去掉
        }
    }
    //构造一个堆
    public static void createheap(int[] arr){
        for(int i =(arr.length-1-1)/2;i >= 0;i--){
            adjustDown(arr,i,arr.length);
        }
    }
    //向下调整方法
    public static void adjustDown(int[] arr,int parent,int len){
        //计算左孩子节点下标
        int child = 2*parent+1;
        while(child < len){
            //左右孩子选择最大的
            if(child+1 < len && arr[child] < arr[child+1]){
                child++;
            }
            //到了这一步,已经找到最大的孩子,和双亲进行比较
            if (arr[child] > arr[parent]){
                int tmp = arr[child];
                arr[child] = arr[parent];
                arr[parent] = tmp;
                parent = child;
                child = 2*parent+1;
            }else{
                break;
            }
        }
    }

//主函数main用来测试
 public static void main(String[] args) {
 //选择排序
        int[] arr2 = {7,4,9,34,0,8,5,22,55,6,12,33,56,89,77};
        selectsort(arr2);
        System.out.print("选择排序结果: ");
        for (int i = 0;i < arr2.length;i++){
            System.out.print(arr2[i]+" ");
        }
        System.out.println();
       //堆排序
        int[] arr4 = {7,4,9,34,0,8,5,22,55,6,12,33,56,89,77};
        heapsort(arr4);
        System.out.print("堆排序结果: ");
        for (int i = 0;i < arr4.length;i++){
            System.out.print(arr4[i]+" ");
        }
        System.out.println();
 }
}

Java基础—选择排序(选择排序,堆排序)

本文地址:https://blog.csdn.net/qq_45665172/article/details/109648173