[数据结构与算法]数据结构与算法-八大经典排序算法 | 尚硅谷韩顺平学习笔记

一、排序算法简介

常见的排序算法

时间复杂度

事后统计法（要实际运行，而且硬件参数有影响，要求同一台计算机相同状态运行）

事前估算法，通过分析看哪个时间复杂度更优

时间频度：一个算法花费的时间与算法中语句的执行次数成正比，一个算法中语句执行的次数成为语句频度或时间频度 T(n）

统计时间频度的时候 常数项可以忽略

当有高次项的时候，低次项可以忽略

O(n)为算法的渐进时间复杂度，简称时间复杂度?

常见的时间复杂度

1、常数阶O(1)

无论执行了多少行，只要没有循环等复杂结构，那时间复杂度就是O(1)，及时有几十万行

2、对数阶O(logxn)

while循环里面i乘以2 i会以2的x方的速度接近于n?

int i = 1;
while(i<n){
   i=i*2;
}

3、线性阶O(n)

单层for循环

4、线性对数阶O(nlogN)

把对数阶的代码执行n遍

5、平方阶O(n2）?

执行两边for循环，也可以是O(m*n)看循环条件

最坏时间复杂度

最坏的情况下的时间复杂度

空间复杂度

定义为算法在运算过程中临时占存储空间大小的度量

在算法分析的时候，主要讨论的是时间复杂度，从用户角度出发，更应该看重速度，缓存(redis、memcache)空间换时间

二、冒泡排序

从前向后（小标较小的开始）依次比较相邻的值，若发现逆序则交换，使值较大的往后

优化：各元素不断接近自己的位置，如果一趟比较下没有进行过交换，就说明序列有序，因此要在排序中标志一个flag判断是否交换过，从而减少不必要比较（可以在冒泡写完后再优化）

优化，如果我们发现某趟排序中，没有发生过一次交换，可以提前结束冒泡排序

代码实现

public class BubbleSort {
    public static void main(String[] args) {
        int arr[] = {3,9,-1,10,-2};
        //为了理解 把过程打印出来
        //第一趟排序就是将最大的数排在最后
        int temp = 0;//用来交换
        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]){
                    temp = arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
            System.out.println("第"+(i+1)+"次排序的数组"+ Arrays.toString(arr));
        }
    }
}

优化

设置一个boolean来判断是否有进入if，进入说明交换了，整个排序没交换过说明排好了

public class BubbleSort {
    public static void main(String[] args) {
        int arr[] = {3,9,-1,120};
        boolean flag = false;
        //为了理解 把过程打印出来
        //第一趟排序就是将最大的数排在最后
        int temp = 0;//用来交换
        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;
                }
            }
            System.out.println("第"+(i+1)+"次排序的数组"+ Arrays.toString(arr));
            if (flag==false){//一次都没有交换过
                break;
            }else {
                flag = false; //重置flag进行下次判断
            }
        }
    }
}

三、选择排序

选择排序思想：第一次遍历选个最小值，与arr[0]交换，第二次从arr[1]后选最小的与arr[1]交换，以此类推，得到一个从小到大的有序序列

?代码实现

public static void selectSort(int[] arr){

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

            //将做小值放到arr[0] 交换
            if (minIndex != i) {
                arr[minIndex] = arr[i];
                arr[i] = min;
            }

            System.out.println(Arrays.toString(arr));
        }
    }

同样是O(n2)? 嵌套循环，但是速度比冒泡要快，交换少

四、插入排序

插入排序介绍：对预排序的元素以插入的方式寻求该元素的适当位置

基本思想：把n个带排序的元素看成一个有序表和一个无序表，开始有序表只有一个元素，无序表中有n-1个元素，排序过程中每次从无序表取出第一个元素，把他插入有序表中适当位置，成为新的有序表?

理解下这个图，这个图很形象了?

?代码实现

   public static void insertSort(int[] arr){

        for (int i=1;i<arr.length;i++){
            //定义待插入的数
            int insertVal = arr[i];
            int insertIndex = i-1;

            //给insertVal找到插入的位置
            while (insertIndex>=0 && insertVal<arr[insertIndex]){
                arr[insertIndex+1] = arr[insertIndex];
                insertIndex--;
            }
            //当退出while循环，说明插入的位置找到，insertIndex+1
            arr[insertIndex+1] = insertVal;
            System.out.println("第"+i+"轮"+Arrays.toString(arr));
        }
    }

可以优化，如果满足条件说明就是原本的位置不用变化

if (insertIndex + 1 ==i){
   arr[insertIndex+1] = insertVal;
}

最后测试比选择慢，跟冒泡差不多

五、希尔排序

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

基本思想：把记录按下标的一定增量分组，对每组使用直接插入排序算法排序，随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法终止

?用length除2就是步长，根据步长分组交换

代码实现?

 public static void shellSort(int[] arr){
        //希尔排序第一轮
        int temp = 0;
        for (int gap = arr.length/2 ; gap>0 ; gap /=2 ){
            for (int i = gap;i<arr.length;i++){
                //遍历各组所有的元素(共5组每组2元素)步长5
                for (int j = i-gap ; j>=0 ; j-=gap){
                    if (arr[j] > arr[j+gap]){
                        temp = arr[j];
                        arr[j] = arr[j+gap];
                        arr[j+gap] = temp;
                    }
                }
            }
        }
        System.out.println("希尔排序后="+ Arrays.toString(arr));
    }

感觉开始有点难了，需要时间理解了QAQ

• 最外面循环是用来分组的,gap就代表间隔，这个间隔非常影响我们的计算效率，科学家设计出来我们每次除以2来分组，所有我们没循环一遍除2
• 中间层循环是用来 从第一个可以往前成员进行比较的数来比较，往后i++为了让后面每个数都有条件跟自己前面的比较（让分的每一组都排序）
• 最里面层是进行组内排序的，j-=gap就是第三个元素也能比到第一个，如果一组只有两个元素就进不来第二次for了?

运行玩之后我们进行测试，我们发现增强后居然比插入算法更慢了？那究竟是什么问题呢

我们发现是交换的时候出了问题 我们改成移位法 大概思路是和上面差不多的

public static void shellSort(int[] arr){
        //希尔排序第一轮
        int temp = 0;
        for (int gap = arr.length/2 ; gap>0 ; gap /=2 ){
            for (int i = gap;i<arr.length;i++){
                //遍历各组所有的元素(共5组每组2元素)步长5
                int j = i;
                temp = arr[j];
                while (j-gap>0 && temp<arr[j-gap]){
                    arr[j] = arr[j-gap];
                    j -= gap;
                }
                //当退出while后,就给temp找到插入的位置
                arr[j] = temp;
            }
        }
        System.out.println("希尔排序后="+ Arrays.toString(arr));
    }

这个时候发现效率比前面的冒泡快了几倍，希尔nb！（测80000数据）

网上了解：用已知最好的步长序列的希尔排序比直接插入排序要快，甚至在小数组中比快速排序和堆排序还快，但在涉及大量数据时希尔排序还是不如快排，我们接来下就是快排

六、快速排序

快排是对冒泡的改进

基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据小，然后再此方法对两部分数据分别进行快速排序，整个排序过程可以递归进行

（这里韩顺平的不好懂，我选择听其他老师的）视频地址如下：（这个老师通俗易懂）

【java快速排序讲解】https://www.bilibili.com/video/BV1it41167v2?vd_source=0ebec850c9ab1b23ee63d39fda25e5c2

?

代码实现

public static void quickSort(int[] arr,int left,int right){
        //判断如果左边索引比右边大 直接return
        if (left > right){
            return;
        }
        //定义变量保存基准
        int base = arr[left];
        //定义变量i指向最左边，j指向最后边
        int i=left;
        int j=right;
        while (i!=j){   //因为不知道什么时候能结束所以while
            //先由j从右往左检索比基准小的，如果检索到比基准小的就停下
            //检索到比基准数大的就继续
            while(arr[j] >= base && i<j){
                j--;    //j从右往左
            }
            while(arr[i] <= base && i<j){
                i++;    //i从左往右
            }
            //都停下了说明要交换了
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        //如果条件while循环不成立 跳出循环 说明i和j相遇
        //所以要把i和j的元素和基准交换
        arr[left] = arr[i];
        //把基准赋值给相遇位置
        arr[i] = base;

        //排基准左边的
        quickSort(arr, left, i-1);
        quickSort(arr,j+1,right);
    }

快排的速度要比希尔排序快，因为用到递归，开辟了栈的空间，属于是空间换时间的算法。

七、归并排序

归并排序是利用归并的思想实现排序的方法，采用分治的策略

?

?代码实现

//分解方法
    public static void mergeSort(int[] arr,int left,int right, int[] temp){
        if (left<right){
            int mid = (left+right)/2; //中间索引
            //向左递归
            mergeSort(arr,left,mid,temp);
            //向右递归
            mergeSort(arr,mid+1,right,temp);
            //合并
            merge(arr,left,mid,right,temp);
        }
    }

    //合并方法
    public static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i = left; //初始化i 左边有序序列的初始索引
        int j = mid+1; //初始化j 右边有序序列的初始索引
        int t = 0;

        //先把左右两边的数据按规则填充到temp数组
        //直到左右两边的有序序列，有一边处理完毕为止
        while (i<=mid && j<=right){
            if (arr[i]<=arr[j]){
                //如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素 左边往后扔
                temp[t] = arr[i];
                t += 1;
                i += 1;
            }else{
                //如果右边的小，那就把右边的往temp里面扔 右++temp++、
                temp[t] = arr[j];
                t += 1;
                j += 1;
            }
        }

        //把剩余的填充到temp
        while(i<=mid){
            temp[t] = arr[i];
            t+=1;
            i+=1;
        }
        while(j<=right){
            temp[t] = arr[j];
            t+=1;
            j+=1;
        }

        //并不是每次都拷贝所有
        t = 0;
        int tempLeft = left;
        while (tempLeft <= right){
            arr[tempLeft] = temp[t];
            t+=1;
            tempLeft+=1;
        }
    }

先分然后再合 分开的时候一层层递归分开（分开就是递归开，本质没干什么事）

合并的时候结束每个递归合并，合并的时候比大小方到另一个数组temp最后放回去

一个数组有n个数 只要排n-1次 所有速度还是可以的，冒泡要n2。也是空间换时间 跟快排差不多快

八、基数排序（桶排序）

基数排序属于分配式排序，通过键值的各个位的值，将要排序的元素分配到某些桶中，达到排序的作用。基数排序属于稳定排序（当原本数组有很多1时，排序后保证之前前面的1还在前面，后面的1在后面），基数排序是桶排序的扩展

基本思想：

将所有持有比较数值统一为同样的数位长度，数位较短的数前面补零。然后从低位开始，依次进行一次排序。这样从最低位一直到最高位排序完，数列就有序了

如图：

?

?

?代码实现

//基数排序方法
    public static void radixSort(int[] arr){

        //先得到数组最大的数觉得排多少轮
        int max = arr[0];
        for (int i=1;i< arr.length;i++){
            if (arr[i]>max){
                max = arr[i];
            }
        }
        //得到最大数为几位数
        int maxLength = (max+"").length();

        //每个元素个位进行排序
        //定义二维数组表示十个桶，每个桶是个一位数组
        int [][] bucket = new int[10][arr.length]; //为了防止数据溢出,每个桶大小为arr.length

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

        for (int i=0,n=1 ;i<maxLength;i++,n*=10){
            //第一次是个位循环 第二次十位 往下排
            for (int j = 0;j< arr.length;j++){
                //取出每个元素的对应位的值
                int digitOfElement = arr[j]/n % 10;
                //放入对应的桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++;
            }
            //按照桶的顺序(依次取出放回原来数组)
            int index= 0;
            //遍历每一个桶,并将桶中数据放入原数组
            for (int k=0; k< bucketElementCounts.length ;k++){
                //如果桶中有数据 我们才放入原数组
                if (bucketElementCounts[k]!=0){
                    //循环该桶 及第k个桶
                    for (int l=0;l<bucketElementCounts[k];l++){
                        //取出元素放入到arr中
                        arr[index++] = bucket[k][l];
                    }
                }
                //第i+1轮处理后我们要讲每个bucketElementCounts[k]置于0
                bucketElementCounts[k]=0;
            }
            System.out.println(Arrays.toString(arr));
        }
    }

基数排序是对传统排序的扩展，所以速度是非常快的，他也是空间换时间 而且如果数据大消耗的空间会非常大，可能出现OutOfMenmoryError的问题

如果有负数的数组，那么我们就不能用基数排序来进行排序了（不过也可以进行支持负数改进）

九、八大排序的对比