排序算法基础+冒泡排序+冒泡排序的小优化

排序算法

排序的分类:

1)内部排序:指将需要处理的所有数据都加载到内部存储器**(内存)**中进行排序。
2)外部排序法:数据量过大,无法全部加载到内存中,需要借助外部存储进行排序。

在这里插入图片描述

时间复杂度

事后统计的方法
这种方法可行,但是有两个问题:一是要想对设计的算法的运行性能进行评测,需要实际运行该程序;二是所得时间的统计量依赖于计算机的硬件、软件等环境因素,这种方式,要在同一台计算机的相同状态下运行,才能比较那个算法速度更快

事前估算的方法
通过分析某个算法的时间复杂度来判断哪个算法更优.

时间频度

时间频度:一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

例如:

int total = 0;
int end = 100;
//使用for循环计算
for(int i=1;i<=end;i++)			
{
    total += i;
}
T(n) = n+1;		//n代表程序规模,在这里也就是循环的次数100次 101
//直接计算
total = (1+end)*end/2;
T(n) = 1

结论:

一般是忽略常数项的

2n+20和2n随着n变大,执行曲线无限接近, 20可以忽略
3n+10和3n随着n变大,执行曲线无限接近, 10可以忽略

一般忽略低次项

2n2+3n+10和2n2随着n变大,执行曲线无限接近,可以忽略3n+10
n2+5n+20和n2随着n变大,执行曲线无限接近,可以忽略5n+20

忽略系数的情况呢?一般出现次数相差太大的情况下,系数可以忽略

计算时间复杂度

一般情况下,算法中的基本操作语句的重复执行次数是间题规模n的某个函数,用n)表示,若有某个辅助函数f(n),使得当n趋近于无穷天时,T(m) / f(n)的极限值为不等于零的常数,则称f(n)是T(n)的 同数量级函数。记作T(n)= 0(f(n)), 称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。比如我们上面的T(n)=n+1,假设f(n) = n,T(n)/f(n)无限趋近与1,那f(n)就是辅助函数

T(n)不同,但时间复杂度可能相同。如: T(n)=n^2+7n+6与 T(n)3n2+2n+2它们的T(n)不同,但时间复杂度相同,都为0(n2)。

用常数1代替运行时间中的所有加法常数T(n)=n^2+7n+6===>T(n) = n^2+7n+1
修改后的运行次数函数中,只保留最高阶项T(n)=n^2+7n+1 ===>T(n) = n^2
去除最高阶项的系数T(n) = n^2 = T(n) = n^2=>O(n) = n^2

常见的时间复杂度

1)常数阶0(1)
2)对数阶0(log2n)
3)线性阶0(n)
4)线性对数阶0(nlog2n)
5)平方阶0(n^2)
6)立方阶0(n^3)
7) k次方阶0(n^k)
8)指数阶0(2^n)

常见的算法时间复杂度由小到大依次为: 0(1)<0(log2n)<o(n)<o(nlog2n)<0(n2)<0(n3})< 0(n^k) <0(2^n),随着问题规模n的不断增大,上述时 间复杂度不断增大,算法的执行效率越低

所以我们尽可能要避免指数阶

例子

常数阶O(1)

int i = 1; 
int j = 1;
++1;
++j;
int m = i + j;	
上述代码在执行的时候,它消耗的时候并丕随着某个变量的增长而增长,那么无论这类代码有多长,即使有几万几十万行,都可以用0(1)采表示它的时间复杂度。

对数阶0(log2n)

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

说明:在while循环里面,每次都将i乘以2,乘完之后,i距离n就越来越近了。假设循环x次之后,i就大于2了,此时这个循环就退出了,也就是说2的x次方等于n,那么x=log2n也就是说当循环log2n次以后,这个代码就结束了。因此这个代码的时间复杂度为:O(log2n)。O(log2n) 的这个2时间上是根据代码变化的,i=i*3, 则是0(log;n)

举个简单的例子上面代码n=1024,程序执行几次?次数=log2n

n=9,i = i *3呢?次数是不是等于log3 9 = 2次,第一次是1X3,第二次是3X3

线性阶0(n)

for(int i=1;i<n;i++){
    j = 1;
    j++;
}

说明:这段代码,for循环里面的代码会执行n遍,因此它消耗的时间是随着n的变化而变化的,因此这类代码都可以用0(n)来表示它的时间复杂度

线性对数阶0(nlog2n)

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

这不就是结合嘛,for里面套一个while

平方阶0(n^2)

顾名思义,就是双重for循环啦

for(int i=1;i<n;i++){
    for(int i=1;i<n;i++){
    	j = i;
        j++
	}
}

举一反三,其他的时间复杂度就一一显现出来了

平均时间复杂度和最坏时间复杂度、

平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下,该算法的运行时间。

最坏情况下的时间复杂度称最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂
度。**这样做的原因是:**最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限,这就保证了算法的运行时间不会比最坏情况更长。

排序法平均时间最差情形稳定度额外空间备注
冒泡O(n 2 )O(n 2 )稳定O(1)n 小时较好
交换O(n 2 )O(n 2 )不稳定O(1)n 小时较好
选择O(n 2 )O(n 2 )不稳定O(1)n 小时较好
插入O(n 2 )O(n 2 )稳定O(1)大部分已排序时较好
基数O(log R B)O(log R B)稳定O(n)B 是真数 (0-9) ,R 是基数 ( 个十百 )
ShellO(nlogn)O(n^s ) 1<s<2不稳定O(1)s 是所选分组
快速O(nlogn)O(n^2 )不稳定O(nlogn)n 大时较好
归并O(nlogn)O(nlogn)稳定O(1)n 大时较好
O(nlogn)O(nlogn)不稳定O(1)n 大时较好

空间复杂度

类似王时间复杂度的过论,一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间,它也是问题规模n的函数。

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模n有关,它随着n的增大而增天,当n较大时,将占用较多的存储单元,例如快速排序和归并排序算法就属于这种情况

在做算法分析时,主要讨论的是时间复杂度。从用户使用体验上看,更看重的程序执行的速度。一些缓存产品(redis, memcache)和算法(基数排序)本质就是用空间换时间.

冒泡排序

基本介绍

冒泡排序(Bubble Sorting) 的基本思想是:

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

什么是逆序:就是你规定的策略,你让他从小到大,大的在前就是逆序了

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

冒泡排序图解

img

规则:

一共要进行的次数为数组大小n-1

每一趟排序的次数在逐渐减少

如果在某趟排序过程中,没有发生一次交换,我们可以提前结束排序(优化)

代码

/**
 * @author 王庆华
 * @version 1.0
 * @date 2020/12/20 21:54
 * @Description TODO
 * @pojectname 冒泡排序
 */
public class BubbleSort {
    public static void main(String[] args) {
        //给出我们需要排序的数组
        int[] array = {3,9,-1,10,-2};
        int temp = 0;//临时变量,交换的时候用
        for (int i = 0; i <array.length-1 ; i++) {
            for (int j = 0; j < array.length-1-i ; j++) {
                //如果前面的数比后面数大,交换
            if (array[j] > array[j+1]){
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
             }
            }
            System.out.println("第"+(i+1)+"次排序后的数组");
            System.out.println(Arrays.toString(array));
        }


//        //第一次排序,就是为了把最大的数,排在最后
//        int temp = 0;//临时变量,交换的时候用
//        for (int j=0;j<array.length-1;j++){
//            //如果前面的数比后面数大,交换
//            if (array[j] > array[j+1]){
//                temp = array[j];
//                array[j] = array[j+1];
//                array[j+1] = temp;
//            }
//        }
//        System.out.println("第一次排序后的数组");
//        System.out.println(Arrays.toString(array));
//
//        //第二趟排序,把第二大的数排在倒数第二位
//        for (int j=0;j<array.length-1-1;j++){
//            //如果前面的数比后面数大,交换
//            if (array[j] > array[j+1]){
//                temp = array[j];
//                array[j] = array[j+1];
//                array[j+1] = temp;
//            }
//        }
//        System.out.println("第二次排序后的数组");
//        System.out.println(Arrays.toString(array));
//
//        //第三趟排序,把第三大的数排在倒数第三位
//        for (int j=0;j<array.length-1-1-1;j++){
//            //如果前面的数比后面数大,交换
//            if (array[j] > array[j+1]){
//                temp = array[j];
//                array[j] = array[j+1];
//                array[j+1] = temp;
//            }
//        }
//        System.out.println("第三次排序后的数组");
//        System.out.println(Arrays.toString(array));
//        //第四趟排序,把第三大的数排在倒数第四位
//        for (int j=0;j<array.length-1-3;j++){
//            //如果前面的数比后面数大,交换
//            if (array[j] > array[j+1]){
//                temp = array[j];
//                array[j] = array[j+1];
//                array[j+1] = temp;
//            }
//        }
//        System.out.println("第四次排序后的数组");
//        System.out.println(Arrays.toString(array));
    }
}

我们做的注释是为了理解,我们不难发现规则,第一次排序的时候是array.length-1-0,,然后第二次是array.lenth-1-1,如此以来,我们不难发现for循环操作是一样的,只是每次循环的次数不一样,那我们可以外层套用一个一样的for循环,里面的for循环来控制每次排序的不同的次数

优化过后

/**
 * @author 王庆华
 * @version 1.0
 * @date 2020/12/20 21:54
 * @Description TODO
 * @pojectname 冒泡排序
 */
public class BubbleSort {
    public static void main(String[] args) {
        //给出我们需要排序的数组
        int[] array = {3,9,-1,10,20};
        bubbleSort(array);
        System.out.println("排序后的数组");
        System.out.println(Arrays.toString(array));
    }
    //将前面的排序算法疯转成一个方法
    public static void bubbleSort(int[] array){
        int temp = 0;//临时变量,交换的时候用
        boolean flag = false;//表示是否进行过交换
        for (int i = 0; i <array.length-1 ; i++) {
            for (int j = 0; j < array.length-1-i ; j++) {
                //如果前面的数比后面数大,交换
                if (array[j] > array[j+1]){
                    flag = true;//说明做出了交换,我不能终止排序
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
            if (flag == false){//一次循环,没有任何交换
                break;
            }
            else {
                flag = false;//重置我们的flag,下次交换还得用呢
            }
        }
    }
}

引入我们的flag是为了优化排序次数,有的数据特殊,我们的flag能提前结束排序的

有意思的是数组时int[8]的时候很快很快,但是int[80000]的时候就要20多秒了