Java知识总结

基础排序算法

Mr.LR2022年5月19日
大约 4 分钟

基础排序算法

本章主要介绍几种比较简答的排序算法

选择排序（Selection sort）

基本思想

首先在未排序的数列中找到最小(or最大)元素，然后将其存放到数列的起始位置；接着，再从剩余未排序的元素中继续寻找最小(or最大)元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

image-20220518215010883

代码实现

//简单的选择排序
public static <E extends Comparable > void select(E [] arr){
    for(int i=0;i<arr.length;i++){
        int minx = i;
        for(int j=i;j<arr.length;j++){
            if(arr[minx].compareTo(arr[j])>0){
                convert(arr,minx,j);//交换位置
            }
        }
    }
}
public static  <E> void convert(E arr[],int minx,int j){
    E ss = arr[minx];
    arr[minx] = arr[j];
    arr[j] = ss;
}

选择排序算法复杂度

选择排序的时间复杂度是O(N2)。

插入排序（Insertion Sort）

基本思想

把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。

image-20220518214511921

代码实现

//插入排序
public static <E extends Comparable> void selectByInsert(E[] arr){
    for(int i=0;i<arr.length;i++){
        for(int j=i;j>=1;j--){
            if(arr[j].compareTo(arr[j-1])<0){
                convert(arr,j,j-1);//交换位置
            }else {
                break;
            }
        }
    }
}

插入排序算法复杂度

选择排序的时间复杂度是O(n^2)。

但是有种特殊情况，当需要排序的数组，本身就是有序，则插入排序算法复杂度为O(n)，对比选择排序，即使数组本身有序，其复杂度仍然是O(n^2)

冒泡排序（Bubble Sort）

基本思想

它是一种较简单的排序算法。它会遍历若干次要排序的数列，每次遍历时，它都会从前往后依次的比较相邻两个数的大小；如果前者比后者大，则交换它们的位置。这样，一次遍历之后，最大的元素就在数列的末尾！ 采用相同的方法再次遍历时，第二大的元素就被排列在最大元素之前。重复此操作，直到整个数列都有序为止！

image-20220519215815612

从该图可推算出，j循环结束的条件 j<arr.length-i-1，因为每次子循环结束，末尾会多排好一位

image-20220519220047835

从该图可推算出，i循环结束条件i<arr.length-1，因为比较的是相邻两位，所以到倒数第二位即可

代码实现

public static <E extends Comparable<E>> void sort(E[] data) {
    for (int i = 0; i < data.length - 1; i++) {//因为是比较相邻两个元素，所以到 （data.length-1）即可
        //每次子循环结束，则末尾的处理结束
        for (int j = 0; j < data.length - i - 1; j++) {//
            if (data[j].compareTo(data[j + 1]) > 0) {
                swap(data,j,j+1);//交换位置
            }
        }
    }
}

冒泡排序算法复杂度

冒泡的时间复杂度是O(n^2)。

希尔排序（Shell Sort）

基本思想

希尔排序实质上是一种分组插入排序，即将一个大小为n的数组，为了加快速度改进了插入排序，交换不相邻的元素对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。

在此我们选择增量 gap=length/2，缩小增量以 gap = gap/2 的方式，用序列 {n/2,(n/2)/2...1} 来表示。

通俗讲：假设一个数组长度为n

  • 对元素间距为n/2的所有数组做插入排序

  • 对元素间距为n/4的所有数组做插入排序

  • 对元素间距为n/8的所有数组做插入排序

    ​ ..........

  • 对元素间距为1的所有数组做插入排序

第一趟

image-20220519223728863

第二趟

image-20220519224327832

第三趟即对整个数组进行插入排序

代码实现

public static <E extends Comparable<E>> void sort(E[] data){
    int h = data.length / 2;
    while(h >= 1){//最外层循环，gap依次减少
        // 对 data[start, start + h, start + 2h, start + 3h ...], 进行插入排序  即对间距为h进行插入排序
        for(int start = 0; start < h; start ++){//在一趟中将整个数组分为了几组，进行几次循环
            //如下方法就和插入排序方法类似，即对起始为start,间隔为h的数组做插入排序
            for(int i = start + h; i < data.length; i += h){//因为间距为h 所以 i = i+h
                E t = data[i];
                for(int j = i; j - h >= 0; j -= h){//这里注意 j 和前 面的 j-1比较 但是间隔是h 所以这里是 j - h >= 0; 即间隔为h的最左边的j
                    if(t.compareTo(data[j - h])<0){
                        swap(data,j,j-h);
                    }else {
                        break;
                    }
                }
            }
        }
        h /= 2;
    }
}

希尔排序算法复杂度

希尔排序算法复杂度为O(n^3/2)

参考