排序算法

简介

排序算法分为内部排序和外部排序

  • 内部排序:将需要处理的所有数据都加载到内部存储器中进行排序
  • 外部排序:数据量过大,无法全部加载到内存中,需要解除外部存储进行排序

常见的排序算法

  • 插入排序
  • 希尔排序
  • 选择排序
  • 堆排序
  • 冒泡排序
  • 快速排序
  • 归并排序

冒泡排序

Bubble Sorting 冒泡排序基本思想是:通过对待排序序列从前向后(从下标较小的元素开始),一次比较相邻元素的值,若发现逆序啧交换,使值较大的元素主键从前移向后部,就像水泡一样逐渐向上冒

优化思路:

因为排序过程中,各元素不断接近自己的位置,如果比较下来,没有进行过交换,就说明序列有序,因此在排序过程中设置一个标志来判断元素是否进行过交换,从而减少不必要的比较

package sort;

import java.util.Arrays;

/**
 * @Author: tongck
 * @Date: 2022/11/2 13:18
 */
public class Sort {
    public static void main(String[] args) {
        int a[]={3,6,8,9,5,7,4,2,1,0};
        System.out.println(Arrays.toString(bubbleSort(a)));
    }
    public static int[] bubbleSort(int [] array){
        int length = array.length;
        for (int i=0;i<length-1;i++){
            for (int i2=0;i2<length-i-1;i2++){
                if (array[i2]>array[i2+1]){
                    int s=array[i2];
                    array[i2]=array[i2+1];
                    array[i2+1]=s;
                }
            }
        }
        return array;
    }   
}

优化思路,如果有一次冒泡排序没有发生任何交换,就说明数组是有序的可以直接return

package sort;

import java.util.Arrays;

/**
 * @Author: tongck
 * @Date: 2022/11/2 13:18
 */
public class Sort {
    public static void main(String[] args) {
        int a[]={3,6,8,9,5,7,4,2,1,0};
        System.out.println(Arrays.toString(bubbleSort(a)));
    }
    public static int[] bubbleSort(int [] array){
        int length = array.length;
        boolean f=false;
        for (int i=0;i<length-1;i++){
            f=false;
            for (int i2=0;i2<length-i-1;i2++){

                if (array[i2]>array[i2+1]){
                    f=true;
                    int s=array[i2];
                    array[i2]=array[i2+1];
                    array[i2+1]=s;
                }
            }
            if (!f){
                System.out.println("已经完成了!");
                break;
            }
        }
        return array;
    }


}

选择排序

选择排序是一种简单的排序方法,第一次从arr[0]-arr[n-1]中选取最小值,与arr[0]交换,第二次从arr[1] arr[n-1]中选取最小值,与arr[1]交换以此类推,得到最后的有序序列

public static int[] selectSort(int [] array){
        for (int i=0;i<array.length-1;i++){
            int minIndex=i;
            for (int i2=i+1;i2<array.length;i2++){
                if (array[i2]<array[minIndex]){
                    minIndex=i2;
                }
            }
            int temp=array[minIndex];
            array[minIndex]=array[i];
            array[i]=temp;
        }
        return array;
    }
  1. 选择一共有数组大小-1轮排序
  2. 先假定前面这个是最小数
  3. 然后和后面的每个数进行比较,如果发现有比当前更小的数,就重新确定最小数,并得到下标
  4. 当遍历到数组的最后时,就得到本轮最小数和下标
  5. 交换

选择排序是不稳定排序

插入排序

public static int[] insertSort(int [] array){
        int len=array.length;
        for (int i=1;i<len;i++){
            int i2,temp=array[i];
            for (i2=i;i2>0&&array[i2-1]>temp;i2--){
                array[i2]=array[i2-1];
            }
            array[i2]=temp;
        }
        return array;
    }

特点:从i个元素开始,把后面的元素当成已经有序的,然后找到适合的位置插入(其他元素向后移)

插入排序是普通排序里效率最高的排序算法,在数据趋于有序的情况下,插入排序的效率是最高的

问题:插入是较小的数时,后移的次数明显增多,对效率有影响

希尔排序

希尔排序也是一种插入排序的变种,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序

采用的是分治的思想,是不稳定排序

这是希尔排序的交换法

public static int[] shellSort(int [] array){
    int len=array.length;
    //确定交换有多少组,同时gap也是步长
    for (int gap=len/2;gap>0;gap=gap/2){
        //这是要进行交换的数据量
        for (int i=gap;i<len;i++){
            //遍历各组中的所有元素
            for (int j=i-gap;j>=0;j=j-gap){
                //当前元素+步长就是需要比较和交换的元素了
                if (array[j]>array[j+gap]){
                    int temp=array[j];
                    array[j]=array[j+gap];
                    array[j+gap]=temp;
                }
            }
        }
    }
    return array;
}

这是希尔排序的位移法,采用的是插入排序的思想,速度会快一些

public static int[] shellSortInsert(int [] array){
    int len=array.length;
    //确定交换有多少组,同时gap也是步长
    for (int gap=len/2;gap>0;gap=gap/2){
        //这是要进行操作的数据量
        for (int i=gap;i<len;i++){
            int j=i;
            int temp=array[j];
            if (array[j]<array[j-gap]){
                while (j-gap>=0&&temp<array[j-gap]){
                    //按照步长进行移动
                    array[j]=array[j-gap];
                    j=j-gap;
                }
                //退出while代表找到了temp需要的位置
                array[j]=temp;
            }
        }
    }
    return array;
}

此外，希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏的情况下执行的效率会非常差。

归并排序

归并排序(Merge-sort)是利用归并的思想实现的排序方法,改算法采用经典的分治(divide-and-conquer)策略

public static int[] mergeSort(int [] array){
        int len=array.length;
        int []temp=new int[len];
        mergeSort(array,0,len-1,temp);
        return array;
    }

    public static void mergeSort(int [] array,int left,int right,int[] temp){
        //如果left和right一样或者超过时就停止
        if (left<right){
            int mid=(left+right)/2;
            //左半边
            mergeSort(array,left,mid,temp);
            //右半边
            mergeSort(array,mid+1,right,temp);
            //进行排序逻辑
            merge(array,left,mid,right,temp);
        }
    }
    public static void merge(int[] array,int left,int mid,int right,int[] temp){
        int leftFirst=left,t=0,rightFirst=mid+1;
        //有点类似双指针,比较俩边的大小,把小的放到temp里,然后索引向后移动
        while (leftFirst<=mid&&rightFirst<=right){
            if (array[leftFirst]<=array[rightFirst]){
                temp[t++]=array[leftFirst++];
            }else {
                temp[t++]=array[rightFirst++];
            }
        }
        //放入左边剩余元素
        while (leftFirst<=mid){
            temp[t++]=array[leftFirst++];
        }
        //放入右边剩余元素
        while (rightFirst<=right){
            temp[t++]=array[rightFirst++];
        }
        //把整个temp排好序的数据覆盖回array中
        t=0;
        while (left<=right){
            array[left++]=temp[t++];
        }
    }

快速排序

quickSort是对冒泡排序的一种改进,他的基本思想是通过一趟排序将要排序的数据分割成独立的俩分,其中一部分数据比另外一部分的所有数据都要小,然后再按此方法对这俩部分数据分别进行快速排序,整个排序过程可以递归进行,一次达到整个数据变成有序序列

也是基于分治的思想

 public static int[] quickSort(int [] array) {

        quickSort(array,0,array.length-1);
        return array;
    }
    public static void quickSort(int [] array,int start,int end) {
        //递归出口
        if (start>=end){
            return;
        }
        //startValue可以为随机数,是用来和开始于结束的数据进行比较的
        int startIndex=start,endIndex=end,startValue=array[start];
        while (startIndex<endIndex){
            //先从右边开始
            while (startIndex<endIndex&&array[endIndex]>=startValue){
                endIndex--;
            }
            //再从左边开始
            while (startIndex<endIndex&&array[startIndex]<=startValue){
                startIndex++;
            }
            //到这里一定满足了 array[startIndex]>=startValue>=array[endIndex]
            //所以交换前后的顺序
            int temp=array[startIndex];
            array[startIndex]=array[endIndex];
            array[endIndex]=temp;
            //循环结束后startIndex会等于endIndex
        }
        //这里也是做了一次交换,把之前开始位置的值和现在的做交换
        array[start]=array[startIndex];
        array[startIndex]=startValue;
        quickSort(array,start,startIndex-1);
        quickSort(array,startIndex+1,end);
    }

主义一定要先从右往左,再从左往右开始

如图所示,如果先从左边开始,i会和j在9会面,此时进行交换就变成了[9,1,2,5,4,3,6,7,10,8]

无法保证左边一定比右边小

Arrays.sort(array):默认数组排序就是快速排序

如果Comparator为null，则进入sort方法

看是否设置了LegacyMergeSort.userRequested为true 如果设置了则使用归并排序,如果未设置则使用TimSort（优化归并排序）

Last modification：November 4, 2022
© Allow specification reprint
如果觉得我的文章对你有用，请随意赞赏