侧边栏壁纸
博主头像
一定会去到彩虹海的麦当

说什么呢?约定好的事就一定要做到啊!

  • 累计撰写 63 篇文章
  • 累计创建 16 个标签
  • 累计收到 3 条评论

目 录CONTENT

文章目录

经典排序算法总结

一定会去到彩虹海的麦当
2022-05-04 / 0 评论 / 0 点赞 / 56 阅读 / 5,996 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-17,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

1、冒泡排序

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢 “浮” 到数列的顶端。

1.1 算法描述

  • 比较相邻的元素。如果第一个比第二个大,就交换它们两个;
  • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
  • 针对所有的元素重复以上的步骤,除了最后一个;
  • 重复步骤 1~3,直到排序完成。

1.2 动图演示

1.3 代码实现

 //冒泡排序
    public static void  bubbleSort(int[] arr){

        for(int i = 0;i<arr.length;i++){
            for(int j = 0;j<arr.length-1-i;j++){
                if(arr[j]>arr[j+1]){
                    swap(arr,j,j+1);
                }
            }
        }

    }

这里的交换方法如下,后续不再重复介绍

private static void swap(int[] arr ,int i ,int j ){
    int temp = arr[j];
    arr[j]=arr[i];
    arr[i] = temp;
}

1.4 算法分析

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

2、选择排序(Selection Sort)

表现最稳定的排序算法之一,因为无论什么数据进去都是O(n2)的时间复杂度,所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲,选择排序可能也是平时排序一般人想到的最多的排序方法了吧。

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

2.1 算法描述

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下:

  • 初始状态:无序区为R[1…n],有序区为空;
  • 第i趟排序(i=1,2,3…n-1)开始时,当前有序区和无序区分别为R[1…i-1]和R(i…n)。该趟排序从当前无序区中-选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1…i]和R[i+1…n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区;
  • n-1趟结束,数组有序化了。

2.2 动图演示

2.3 代码实现

   //选择排序
    public static void selectionSort(int[] arr){
        for(int i =0;i<arr.length;i++){
            int minIndex = i;
            for(int j = i+1;j<arr.length;j++){
                if(arr[minIndex]>arr[j]){
                    minIndex = j;
                }
            }
            if(minIndex!=i){
                swap(arr,i,minIndex);
            }
        }
    }

2.4 算法分析

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

3、插入排序(Insertion Sort)

插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用 in-place 排序(即只需用到 O(1) 的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

3.1 算法描述

一般来说,插入排序都采用 in-place 在数组上实现。具体算法描述如下:

  • 从第一个元素开始,该元素可以认为已经被排序;
  • 取出下一个元素,在已经排序的元素序列中从后向前扫描;
  • 如果该元素(已排序)大于新元素,将该元素移到下一位置;
  • 重复步骤 3,直到找到已排序的元素小于或者等于新元素的位置;
  • 将新元素插入到该位置后;
  • 重复步骤 2~5。

3.2 动图演示

3.2 代码实现

  //插入排序
    public static void insertSor(int[] arr){
        for(int i =0;i<arr.length-1;i++){
            int temp = arr[i+1];
            int index = i;
            while (index>=0 && temp<arr[index]){
                //往后移,留出位置以便插入
                arr[index+1] = arr[index];
                index--;
            }
            //因为最后一次循环减1了,所以这里要加上才是其正确位置
            arr[index+1]=temp;
        }
    }

3.4 算法分析

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

4、希尔排序(Shell Sort)

希尔排序是希尔(Donald Shell)于 1959 年提出的一种排序算法。希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序,同时该算法是冲破 O(n2)的第一批算法之一。它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

希尔排序是把记录按下表的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至 1 时,整个文件恰被分成一组,算法便终止。

4.1 算法描述

我们来看下希尔排序的基本步骤,在此我们选择增量 gap=length/2,缩小增量继续以 gap = gap/2 的方式,这种增量选择我们可以用一个序列来表示,{n/2,(n/2)/2…1},称为增量序列。希尔排序的增量序列的选择与证明是个数学难题,我们选择的这个增量序列是比较常用的,也是希尔建议的增量,称为希尔增量,但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,具体算法描述:

  • 选择一个增量序列 t1,t2,…,tk,其中 ti>tj,tk=1;
  • 按增量序列个数 k,对序列进行 k 趟排序;
  • 每趟排序,根据对应的增量 ti,将待排序列分割成若干长度为 m 的子序列,分别对各子表进行直接插入排序。仅增量因子为 1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。

4.2 过程演示

4.3 代码实现

//希尔排序 其实是在插入排序的基础增加了增量分组
    public static void shellSort(int[] arr){
        int len = arr.length;
        //这个是最常用的增量值
        int gap = len/2;

        while (gap>0){
            //插入排序中的1都替换为了gap
            for(int i = gap;i<len;i++){
                int temp = arr[i];
                int index = i-gap;
                while(index>=0 && temp<arr[index]){
                    arr[index+gap]=arr[index];
                    index-=gap;
                }
                arr[index+gap]=temp;
            }
            gap/=2;
        }
    }

4.4 算法分析

时间复杂度跟选择的增量方式有关,一般为O(n^3/2)

希尔排序利用分组粗调的方式减少了直接插入排序的工作量,使得算法的平均时间复杂度低于O(n2)。但是在某些极端情况下,希尔排序的最坏时间复杂度仍然是O(n2),甚至比直接插入排序更慢。例如如下待排序数组:
image.png
如果仍然以上面的折半增量进行希尔排序,则每组内部的元素都没有任何交换。一直到增量缩减为1,数组才会按照直接插入排序的方式进行调整。每一轮希尔增量之间是等比的,这就导致了希尔增量存在盲区。为了避免这样的极端情况,科学家们发明了许多更为严谨的增量方式。
具有代表性的增量序列有:

  • Hibbard增量(1, 3, 7, 15…2^k-1) —— 最坏时间复杂度是O(n^(3/2))
  • Sedgewick增量(1, 5, 19, 41… 9*4k-9*2k+1或者4k-3*2k+1) —— 最坏时间复杂度是O(n^(4/3))
  • Knuth增量(1, 4, 13, 40…1/2(3^k-1)) —— 最坏时间复杂度是O(n^(3/2))

5、归并排序(Merge Sort)

和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是 O(n log n)的时间复杂度。代价是需要额外的内存空间(合并后的结果需要存储)

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为 2 - 路归并。

5.1 算法描述

  • 把长度为 n 的输入序列分成两个长度为 n/2 的子序列;
  • 对这两个子序列分别采用归并排序;
  • 将两个排序好的子序列合并成一个最终的排序序列。

5.2 动图演示

5.3 代码实现

 //归并排序
    //需要temp存储合并后的值,合并的时候会有点麻烦
    public static void mergeSort(int[] arr,int[] temp,int l,int r){
        //涉及左右边界问题时,一定要注意边界交叉问题
        if(l>=r) return;
        int mid = (l+r)/2;

        mergeSort(arr,temp,l,mid);

        mergeSort(arr,temp,mid+1,r);

        merge(arr,temp,l,r,mid);
    }

    private static void merge(int[] arr,int[] temp,int l ,int r,int mid ){
        int i = l;
        int j = mid+1;
        //一定要注意这里是从0开始的
        int index = 0;
        //一定要注意这里是"<="的关系
        while (i<=mid && j<=r){
            if(arr[i]>=arr[j]){
                temp[index++] = arr[j++];
            }else{
                temp[index++] = arr[i++];
            }
        }

        while (i<=mid){
            temp[index++] = arr[i++];
        }

        while (j<=r){
            temp[index++] = arr[j++];
        }
        index = 0;
        while (l<=r){
            arr[l++] = temp[index++];
        }
    }

5. 4 算法分析

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

时间复杂度分析:
归并排序每次会将数据规模一分为二。我们把归并排序画成递归树,就是下面这个样子:
img
因为每次分解都是一分为二,所以代价很低,我们把时间上的消耗记作常量 1。归并算法中比较耗时的是归并操作,也就是把两个子数组合并为大数组。从图中我们可以看出,每一层归并操作消耗的时间总和是一样的,跟要排序的数据规模有关。我们把每一层归并操作消耗的时间记作 n。

现在,我们只需要知道这棵树的高度 h,用高度 h 乘以每一层的时间消耗 n,就可以得到总的时间复杂度 O(n∗h)。

从归并排序的原理和递归树,可以看出来,归并排序递归树是一棵满二叉树。我们前两节中讲到,满二叉树的高度大约是 log2n,所以,归并排序递归实现的时间复杂度就是 O(nlogn)。

6、快速排序(Quick Sort)

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

快速排序之所比较快,因为相比冒泡排序,每次交换是跳跃式的。每次排序的时候设置一个基准点,将小于等于基准点的数全部放到基准点的左边,将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换,交换的距离就大的多了。因此总的比较和交换次数就少了,速度自然就提高了。当然在最坏的情况下,仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2),它的平均时间复杂度为O(NlogN)。其实快速排序是基于一种叫做“二分”的思想。

6.1 算法描述

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

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

6.2 图解

初始序列为:{6,1,7,10,3,8},基准选择最左边的6,我们需要用一个临时变量temp保存这个基准值

  1. 这里用R和L分别指向序列最右边和最左边。首先R开始向左移动,直到找到一个小于6的数停下来。

image.png
接着用R指向的数替换L指向的数。
image.png
替换后,数组为:{3,1,7,10,3,8}

  1. 然后L开始向右移动,直到找到一个大于6的数停下来

img
接着用L指向的数替换R指向的数。
img
替换后,数组为:{3,1,7,10,7,8}

  1. 然后R开始向左移动,遇到L时停止

img

  1. 将L指向的数字替换为基准值temp

img
5. 此时第一遍完成,然后把6左边的数和6右边的数再次进行快排

6.3 代码实现

//快排 考的概率很大,重点
    public static void sort(int[] arr,int l,int r){
        if (l>=r) return;
        //优化,当长度较短时,使用插入排序
//        if(r-l<4){
//         这里使用插入排序
//           return;
//       }
        int index = quickSort(arr, l, r);
        sort(arr,l,index);
        sort(arr,index+1,r);



    }

    public static int quickSort(int[] arr,int l,int r){
        int temp = arr[l];
        while (l<r){
            while (l<r && arr[r]>=temp){
                r--;
            }
            arr[l] = arr[r];
            while (l<r&&arr[l]<=temp){
                l++;
            }
            arr[r]=arr[l];
        }
        arr[l] = temp;
        return l;
    }

6.4 算法分析

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

参考链接:
十大经典排序算法总结(Java实现+动画)

0

评论区