侧边栏壁纸
  • 累计撰写 98 篇文章
  • 累计创建 20 个标签
  • 累计收到 3 条评论

经典排序算法--java代码实现

林贤钦
2020-05-12 / 0 评论 / 26 点赞 / 760 阅读 / 9,627 字
温馨提示:
本文最后更新于 2021-03-07,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

经典排序算法

排序也称排序算法(Sort Algorithm),排序是将一组数据,依指定的顺序进行排序的过程

排序的分类

按数据加载分类

  1. 内部排序:

    指将需要处理的所有数据都加载到内部存储器(内存)中进行排序

  2. 外部排序:

    数据量过大,无法全部加载到内存中,需要借助外部存储(文件等)进行排序。

  3. 常见的排序算法分类

按比较类排序分类

十种常见排序算法可以分为两大类:

  • 比较类排序:通过比较来决定元素间的相对次序

    由于其时间复杂度不能突破O(nlogn),因此也称为非线性时间比较类排序。

  • 非比较类排序:不通过比较来决定元素间的相对次序

    它可以突破基于比较排序的时间下界,以线性时间运行,因此也称为线性时间非比较类排序。

算法的时间复杂度

相关概念

  • 稳定

    如果a原本在b前面,而a=b,排序之后a仍然在b的前面。

  • 不稳定

    如果a原本在b的前面,而a=b,排序之后 a 可能会出现在 b 的后面。

  • 时间复杂度

    对排序数据的总的操作次数。反映当n变化时,操作次数呈现什么规律。

  • 空间复杂度:

    是指算法在计算机内执行时所需存储空间的度量,它也是数据规模n的函数。



图片名词解释:

  • n: 数据规模
  • k: “桶”的个数
  • In-place: 占用常数内存,不占用额外内存
  • Out-place: 占用额外内存

1、冒泡排序(Bubble Sort)

1.1、基本思想

通过对待排序序列从前向后(从下标较小的元素开始),依次比较相邻元素的值,若发现逆序则交换,使值较大的元素逐渐从前移向后部,就像水底气泡一样逐渐向上冒。

1.2、动图演示:

1.3、算法描述

步骤一:比较每对相邻的元素,如果前一个比后一个大,则交换他们

这样第一趟下来留在最后的就是最大的

步骤二:重复上面的动作,除了每次已排序好的数字,直到排序完成

步骤三: n-1趟结束,数组有序化了

1.4、优化

排序过程中,各元素不断接近自己的位置,如果一趟比较下来没有进行交换,就说明已经是有序了

在排序过程中设置一个标识flag 判断元素是否进行过交换,从而减少不必要的比较

1.5、代码实现

public static void bubbleSort(int arr[]) {
    int temp = 0;
    boolean flag = false; // 优化冒泡排序
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                flag = true;
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        if (!flag) {
            break;
        } else {
            flag = false;
        }
    }
}

1.6 、算法分析

  • 最佳情况:T(n) = O(n);最差情况:T(n) = O(n2);平均情况:T(n) = O(n2)

以八万数据测试

第一次 13秒434毫秒

第二次 12秒833毫秒

第三次 13秒387毫秒

2、选择排序(Selection Sort)

2.1、基本思想

每次从当前待排序的区间中选择出最小的元素,把该元素与该区间的第一个元素交换

2.2、动图演示:


2.3、算法描述

步骤一:初始状态,整个数组都是无序的

步骤二:第i躺排序,每次确定数组的第i个元素为有序的

每次从无序的数组中遍历得到一个最小值的下标,再将两个数据进行交换

步骤三: n-1趟结束,数组有序化了

2.4、代码实现

public static void selectSort(int[] arr){
    for(int i=0;i<arr.length-1;i++){
        int minIndex=i;
         //遍历未确定的数,获取最小数下标
        for(int j=i+1; j<arr.length;j++){
           //判断当前的最小数是否大于arr[j],如果大于,更新最小数
            if(arr[minIndex]> arr[j]){
                minIndex=j;//保存最小数的下标
            }
        }
        //将最小值放在arr[i]
        if(minIndex !=i){
            int min = arr[minIndex];
            arr[minIndex]=arr[i];
            arr[i]=min;
        }
    }
}

2.5、 算法分析

  • 最佳情况:T(n) = O(n2);最差情况:T(n) = O(n2);平均情况:T(n) = O(n2)

以八万数据测试

第一次 3秒581毫秒

第二次 3秒619毫秒

第三次 3秒975毫秒

3、插入排序(Insertion Sort)

3.1、基本思想

把n个待排序的元素堪称一个有序表和一个无序表,开始时有序表只包含一个元素,无序表中包含n-1个元素

排序过程中每次从无序表中取出一个元素,把它的排序码和有序表的排序码进行比较,将它插入有序表的适当位置,使之成为新的有序表

3.2、动图演示:

3.3、算法描述

步骤1:

从第一个元素开始,该元素可以认为已经被排序;

步骤2:

取出下一个元素,在已经排序的元素序列中从后向前扫描;

步骤3:

如果该元素(已排序)大于新元素,将该元素移到下一位置;

步骤4:

重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;

步骤5:

将新元素插入到该位置后;

步骤6:

重复步骤2~5。

3.4、代码实现

public static void insertSort(int[]arr){
    int insertVal =0;
    int insertIndex =0;
    for(int i=1;i<arr.length;i++){
        insertVal=arr[i];//待插入元素
        intsertIndex=i-1;//待插入位置的前一个,用于判断
        //如果待插入元素小于前一个位置的元素
        //前一个的位置的元素往后移,待判断插入的位置往前移
        while(insertIndex>=0&&insertVal<arr[insertIndex]){
            arr[insertIndex-1]=arr[insertIndex];//
            insertIndex--;//待判断插入的位置往前移
        }
        //如果待插入位置不和原始的待插入数据一样
        if(insertIndex!=i-1){
            //因为每次insertIndex是已确定的位置的前一个,还没判断
            //所以结束的时候需要insertIndex+1表示待插入位置
            arr[insertIndex+1]=insertVal;
        }
    }
}

3.5、 算法分析

  • 最佳情况:T(n) = O(n);最坏情况:T(n) = O(n2);平均情况:T(n) = O(n2)

以八万数据测试

第一次 0秒594毫秒

第二次 0秒686毫秒

第三次 0秒820毫秒

4、希尔排序(Shell Sort)

希尔排序是希尔(Donald Shell) 于1959年提出的一种排序算法。希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序,同时该算法是冲破O(n2)的第一批算法之一。

4.1、基本思想

希尔排序是把记录按下标的一定增量分组,对分组使用直接插入排序算法排序

随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终结

4.2、动图演示:

4.3、算法描述

我们来看下希尔排序的基本步骤,在此我们选择增量gap=length/2,缩小增量继续以gap = gap/2的方式,这种增量选择我们可以用一个序列来表示,{n/2,(n/2)/2…1},称为增量序列。

步骤1:

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序

步骤2:

选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;

步骤3:

每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。

仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。

4.4 、希尔排序演示过程

4.5 、代码实现

public static void shellSort(int[]arr){
    //增量gap,并逐步的缩小增量
    for (int gap = arr.length/2;gap>0;gap/=2){
        //从第gap个元素,逐个对其所在的组进行直接插入排序
        for (int i = gap; i < arr.length; i++) {
            int j=i;
            int current = arr[j];
            //与j的前gap个比较,如果小于前面那个,则交换
            while (j-gap>=0 && current<arr[j-gap]){
                //移动
                arr[j] =  arr[j-gap];
                j-=gap;
            }
            arr[j]=current;
        }
    }
}

4.6、算法分析

  • 最佳情况:T(n) = O(n);最坏情况:T(n) = O(n2);平均情况:T(n) = O(n2)

以八万数据测试

第一次 0秒276毫秒

第二次 0秒208毫秒

第三次 0秒257毫秒

5、快速排序(Quick Sort)

快速排序是冒泡排序的一种改进,基于分治思想

5.1、基本思想

通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

5.2、动图演示:

5.3、算法描述

快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下:
步骤1

从数列中挑出一个元素,称为 “基准”(pivot );

步骤2

重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;

步骤3

递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

5.4 、代码实现

public static void quickSort(int arr[]){
        quickSort(arr,0,arr.length-1);
    }
    public static void quickSort(int arr[],int low,int high){
        //如果指针在同一位置(只有一个数据时),退出
        if (low>=high){
            return;
        }
        //标记,从高指针开始,还是低指针(默认高指针)
        boolean flag = true;
        //记录指针的其实位置
        int start = low;
        int end = high;
        //默认中间值为低指针的第一个值
        int midValue = arr[low];
        while (true){
            //高指针移动
            if (flag){
                //如果列表右方的数据大于中间值,则向左移动
                if (arr[high]>midValue){
                   high--;
                }else {
                    //如果小于,则覆盖最开始的地址针值,并且移动低指针,标志位改成从地址针开始移动
                    arr[low] = arr[high];
                    low++;
                    flag=false;
                }
            }else{
                //如果低指针数据小于中间值,则低指针向右移动
                if (arr[low]<midValue) {
                    low++;
                }else {
                    //如果低指针的值大于中间值,则覆盖高指针停留时的数据,并向左移动高指针。切换为高指针移动
                    arr[high]=arr[low];
                    high--;
                    flag=true;
                }
            }
            //当两个指针的位置相同时,则找到了中间值的位置,并退出循环
            if (low==high){
                arr[low]= midValue;
                break;
            }
        }
        //然后出现有,中间值左边的小于中间值。右边的大于中间值。
        //然后在对左右两边的列表在进行快速排序
        quickSort(arr,start,low-1);
        quickSort(arr,low+1,end);
    }

5.5、 算法分析

  • 最佳情况:T(n) = O(nlogn) ;最坏情况:T(n) = O(n2) ;平均情况:T(n) = O(nlogn)

以八万数据测试

第一次 0秒87毫秒

第二次 0秒68毫秒

第三次 0秒56毫秒

6 、归并排序(Merge Sort)

归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

6.1、基本思想

将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。归并排序是一种稳定的排序方法。

6.2、动图演示

6.3、算法描述

a、将列表按照对等的方式进行拆分

b、拆分小最小快的时候,在将最小块按照原来的拆分,进行合并

c、合并的时候,通过左右两块的左边开始比较大小。小的数据放入新的块中

d、说明:简单一点就是先对半拆成最小单位,然后将两半数据合并成一个有序的列表。

代码实现的时候,如果你debug,会发现,分的时候,由于栈的先进后出,是一端分到底,才会分第二端

6.4、代码实现

public static void mergeSort(int[]arr,int start,int end){
    //判断拆分的是不是最小单位即start=end
    if (end-start>0){
        //再次拆分,折中分解,直到拆成一个一个的数据
        mergeSort(arr,start,(start+end)/2);//左拆分,【start,(start+end)/2】
        mergeSort(arr, (start+end)/2+1, end);//右拆分,【(start+end)/2+1,end】

        //记录开始/结束位置
        int left = start;
        int right = (start+end)/2+1;
        //记录每个最小单位的排序结果
        int index =0;
        //每次合并的数组大小
        int[] result = new int[end-start+1];
        //如果拆分后的两块数据,都还存在
        while (left<=(start+end)/2 && right<=end ){
            if (arr[left]<= arr[right]) {
                result[index] =arr[left];
                left++;
            }else {
                result[index]=arr[right];
                right++;
            }
            //拷贝单位记录下标++
            index++;
        }
        //当某一块数据不存在了时
        while (left<=(start+end)/2||right<=end){
            //直接赋值到记录下标
            if (left<=(start+end)/2){
                result[index] = arr[left];
                left++;
            }else{
                result[index]=arr[right];
                right++;
            }
            //拷贝单位记录下标++
            index++;
        }
        //最后将最新的数据赋值到原来的数组,并且是对应分块后的下标
        for (int i = start; i <=end; i++) {
            arr[i] = result[i-start];
        }
    }
}

7、基数排序(radix sort)

  • 基数排序 属于"分配式排序",又称“桶子法” 或bin sort,顾名思义,它是通过键值对的各个位的值,将要排序的元素分配至某些“桶”中,达到排序的作用
  • 基数排序法是属于稳定性的排序,基数排序法是高效的稳定性排序法
  • 基数排序(Radix Sort) 是桶排序的扩展
  • 基数排序是1887年赫尔·何乐礼发明的。它的实现是:将整数按位切割成不同的数字,然后按每个位数分别比较

7.1、基本思想

  • 将所有待比较数值同一位同样的数位长度,数位较短的数前面补零

  • 从最低为开始,一次进行一次排序

  • 这样从最低位排序一直到最高位排序完成后,数列就变成一个有序的序列

    简单来说就是每轮对特定的位数进行排序,第一轮个位数,第二轮十位数

7.2、动图演示

7.3、算法描述

  1. 取得数组中的最大数,并取得位数;
  2. 然后arr为原始数组,从最低位个位数开始取每个位组成radix数组;
  3. 对radix进行计数排序(利用计数排序适用于小范围数的特点);

7.4、代码实现

public static void radixSort(int[] arr){
    //得到数组中最大的数的位数
    int max =0;
    for (int i = 0; i < arr.length; i++) {
        if (arr[i]>max){
            max = arr[i];
        }
    }
    //得到最大数的几位数
    int maxLength = (max+"").length();

    //第一轮(针对每个元素的个位进行排序处理)
    //定义一个二维数组,表示10个捅,每个桶就是一个二维数组
    //1.二维数组包含10个一维数组
    //2.为了防止再放入数的时候,数据溢出,则每个一维数组大小设为arr.length
    //3.很明确,基数排序是使用空间换时间的经典算法
    int[][] bucket = new int[10][arr.length];

    //为了记录每个桶中,实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数
    int[] bucketElementCounts = new int[10];

    for (int  j= 0,n=1; j < maxLength; j++,n*=10) {
        //每轮(针对每个元素的个位进行排序处理)
        for (int i = 0; i < arr.length; i++) {
            //取出每个元素的个位的值
            int digitOfElement = arr[i]/n % 10;
            //放入相对于的捅
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] =arr[i];
            bucketElementCounts[digitOfElement]++;
        }
        //按照这个桶的顺序,(一维数组的下标一次取出,放入原来数组)
        int index =0;
        //遍历每个桶
        for (int i = 0; i < bucketElementCounts.length; i++) {
            //如果桶中有数据,才放入原数组
            if (bucketElementCounts[i]!=0){
                //循环该桶,即第k个桶(即第k个一维数组)放入
                for (int l=0;l<bucketElementCounts[i];l++){
                    //取出元素,放入arr
                    arr[index] = bucket[i][l];
                    index++;
                }
            }
            //第j+1轮处理后,需要将每个bucketElementCounts[k] =0;
            bucketElementCounts[i]=0;
        }
        //System.out.println("第"+(j+1)+"轮,arr = " + Arrays.toString(arr));
    }
}

7.5、算法分析

最佳情况:T(n) = O(n * k) 最差情况:T(n) = O(n * k) 平均情况:T(n) = O(n * k)

基数排序有两种方法:

MSD 从高位开始进行排序 LSD 从低位开始进行排序

8、堆排序

8.1、基本思想

堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。

堆是具有以下性质的完全二叉树

  • 每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆

    注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系。

  • 每个结点的值都小于或等于其左右孩子结点的值,称为小

8.2、动图演示

8.3、算法描述

  1. 将待排序序列构造成一个大顶堆

  2. 此时,整个序列的最大值就是堆顶的根节点。

  3. 将其与末尾元素进行交换,此时末尾就为最大值。

  4. 然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列了。

    可以看到在构建大顶堆的过程中,元素的个数逐渐减少,最后就得到一个有序序列了.

8.4、代码实现

public static void heapSort(int[]arr){
    int temp =0;
    System.out.println("堆排序开始");
    for (int i = arr.length/2-1; i >=0 ; i--) {
        //从第一个非叶子结点从下至上,从右至左调整结构
        adjustHeap(arr,i,arr.length);
    }
    for (int i = arr.length-1; i >0 ; i--) {
        //将堆顶元素与末尾元素进行交换
        temp=arr[i];
        arr[i]=arr[0];
        arr[0]=temp;
        //重新对堆进行调整
        adjustHeap(arr,0,i);
    }
}
public static void adjustHeap(int[]arr,int i,int length){
    int temp =arr[i];//先取出当前元素的值,保存在临时变量中
    for (int j = i*2+1; j < length; j=j*2+1) {
        // 如果有右孩子结点,并且右孩子结点的值大于左孩子结点,则选取右孩子结点
        if (j+1<length&&arr[j]<arr[j+1]){//说明左子结点的值小于右子结点的值
            j++;//j指向右子结点
        }
        if (arr[j]>temp){//如果子结点大于父结点
            // 把孩子结点的值赋给父结点
            arr[i]=arr[j];//较大的值赋给当前结点
            i=j;//TODO i指向j,继续循环比较
        }else {
            break;
        }
    }
    //当for循环结束后,我们已经将以i为父节点的树的最大值,放在了最顶(局部)
    arr[i]=temp;//将temp放在调整后的位置
}
26

评论区