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

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();
 }
}

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