简单排序算法

选择排序

思路

选择排序的实现思路大概是这样子的:

第1轮,我选出最大的值,把它放到数组末端

第2轮,选择第二大的数,把它放到倒数第二个位置

········依此类推

最后一轮,我把最小的数放在第一位,整个数组已经排好序了。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
void select_sort(int arr[],int n){
    //第一重循环代表选出第n大的数,也就是要走多少趟,最后一趟不用排了,所以n-1
    for(int i=n-1;i>0;i--){
        int maxindex=i;
        //第二重循环是找出第n大的数,前面已经排好了的i个数就不用管了,所以j=i-1开始
        for(int j=i-1;j>=0;j--){
            maxindex=arr[j]>arr[maxindex]?j:maxindex;
        }
        int temp=arr[i];
        arr[i]=arr[maxindex];
        arr[maxindex]=temp;
    }
}

时间复杂度分析

我们分析上面的代码,在选择排序中,我们会有什么样的常数时间操作呢?

首先,我们要查看arr[j]上的内容,这是一次操作

然后,我们还要比较arr[j]arr[maxindex]上的内容谁大谁小,这又是一次操作

再然后,我们要进行maxindex 的更新操作,又一次常数时间操作,

这样,我们找出一个第n大的值执行的常数时间操作是:3n,最后还要将第n大的值移到后面,这又是依次常数时间操作,+1

所以,整个算法流程下来,我们执行的常数时间操作次数为:(3n+1)+(3(n-1)+1)+(3(n-2)+1)+···+3(1+1)

也就是:3(n+n-1+n-2+···+1)+n 即成等差数列,也就可以表示为$an^2+bn+c$的形式,那由bigO表示法,舍去低阶项,舍去最高阶项的常数系数,然后选择排序的时间复杂度用bigO表示法表示就是: $$O(n^2)$$

冒泡排序

思路

冒泡排序的思想大概是这样子的:

对一个数组,依次对比相邻的两个数,大的就换到后面去

就这样比较1轮下来,最大的数已经排到数组的后面去了,那我接下来继续排第2轮,第3轮,···第n轮,这样就能把这个数组排好了。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
void bubble_sort(int arr[],int n){
     //第一层循环表示要执行多少趟,最后一趟不用执行,所以是n-1
	for(int i=0;i<n-1;i++){  
         //第二层循环表示冒泡排序,相邻两数比较,后面已经排好序的就不用再考虑了
        for(int j=0;j<n-i-1;j++){  //注意,数组不能越界
            if(arr[j]>arr[j+1]){
                int temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
    }
}

时间复杂度分析

基本常数时间操作:查看,比较,交换

那整个算法流程基本常数时间操作就是 $3n+3(n-1)+3(n-2)+···+3$ 也就是 $\frac{n^2}{2}+\frac{n}{2}$

用大O表示法就是:$O(n^2)$

也就是说,冒泡排序和选择排序的时间复杂度是一样的。

插入排序

思想

插入排序的大致思想是这样子的:

假设0~i上的数是有序的,我再加进来一个数,让新的数组有序,那么,我就拿新加的数和数组上的数(假设位置为j)从后往前比较,如果新加进来的数比j位置的数大,那新的数就加在i面,否则就把新的数加到j前面,也就是和j的数进行交换,一直进行到0的位置或者满足条件的时候为止。最后,新的数组也变得有序了。其实这个算法流程有点像打牌的时候,你新摸一张牌,然后该判断这张牌应该插到那个位置去,当然,前提是你有一个把牌排好序的习惯。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
void inserttion_sort(int arr[],int n){
    //0-0有序
    //下面是实现0-i有序
    for(int i=1;i<n;i++){
        for(int j=i;j-1>=0&&arr[j]<arr[j-1];j--){  //如果插入的数比当前数要小,就把插入的数放前面
            int temp=arr[j];
            arr[j]=arr[j-1];
            arr[j-1]=temp;
        }
    }
}

时间复杂度

基本常数时间操作:查,比,换

这里,具体的时间复杂度和数据的特点有关,当数据一开始就是升序排列,那么时间复杂度是$O(n-1)=O(1)$,如果本身是降序排列,情况最糟,为$$O(3(1+2+3+···+n-1+n))=O(n^2)$$ 我们说过,bigO表示法是按照最差的情况进行的,所以插入排序的时间复杂度也是$O(n^2)$.

总结

上面有三种排序算法,三种算法的时间复杂度都是$O(n^2)$ ,但是,要注意的是,冒泡排序和选择排序的时间复杂度和数据的特点是没有关系的,就算你刚开是就是给了一个升序的数组,它还是会原原本本的按照程序走那么多次。

但是,插入算法是和数据特点有关的,如果你给我一个升序的数组,我只要$O(1)$ 的时间就能走完了,相比于前两个是有优化的。

所以,算法优化的思路与两个方面:

1.数据状况

2.问题性质

0%