排序算法 part 1(冒泡排序、快速排序、简单选择排序)

[TOC]
1、排序的概念

2、交换排序
2.1、冒泡排序及其优化
2.1.1 冒泡排序的思想
2.1.2 冒泡排序的三种优化思路

2.2、快速排序
2.2.1 快速排序的思想
2.2.2 由快速排序时间复杂度计算引申出来的问题

3、选择排序
3.1 简单选择排序
3.1.1 简单选择排序算法
3.1.2 选择排序的优化

1、排序的概念

根据排序过程中,待排序的数据是否全部被放在内存中,分为两大类:内部排序和外部排序。内部排序:指的是待排序的数据存放在计算机内存中进行的排序过程。外部排序:指的是排序过程中要对外存储器进行访问的排序过程。
其中,内部排序是排序的基础。在内部排序中,可以根据排序过程中所依据的原则将排序算法分为5类:交换排序、插入排序、选择排序、归并排序。
根据排序过程的时间复杂度来分,可以分为简单排序和先进排序。冒泡排序、简单选择排序、直接插入排序就是简单排序算法。
评价排序算法的优劣标准主要是两条:一个是算法的运算量,这主要通过记录的比较次数和移动次数来反应;另一个是执行算法所需要的附加存储单元的多少。这两个也就是老生常谈的时间复杂度和空间复杂度。
image.png

2、交换排序

2.1、冒泡排序及其优化

2.1.1 冒泡排序

冒泡排序是一种简单的排序算法。由于在排序过程中总是小数往前方,大叔往后放,相当于气泡往上升,所以称作为冒泡排序。

算法规则:
1、比较相邻的元素。如果前者比后者大,就交换它们两个。
2、每一轮都是从前往后,按照第一条规则进行,知道求出本轮最大元素,放到上一轮最大元素的前一位。
3、执行1和2,直到排序完毕。

示例:
image.png

代码实现

//用宏定义声明SWAP ,利用异或运算来实现操作
#define SWAP(a,b) {a^=b;b^=a;a^=b;}

void bubbleSort(int a[],int n)
{
    //k代表当前循环要确定的index上的值
    //最大数的第一个位置index是n-1
    k=n-1;
    //n个元素排序,一共需要进行n-1次循环
    for(i=0;i<n-1;i++)
    {
        //每次选出最大的一个数,把它放到k处 
        for(j=0;j<k-1;j++)
        {
            if(a[j]>a[j+1])
                SWAP(a[j],a[j+1]);
        }
        k--;  
    }
}

算法性能分析:
1、时间复杂度
冒泡排序有两层循环嵌套,第一层是n的函数。第二层是k的函数,而k又是n的函数,第二层也是n的函数。所以冒泡排序的时间复杂度是O(n*n)。
2、空间复杂度
冒泡排序中除了声明一些变量之外,再没有使用和n相关的内存了,所以空间复杂度是O(1)。
3、排序稳定性
冒泡排序是一个稳定的排序算法。

2.1.2 冒泡排序的三种优化思路

第一种优化思路:

假设我们现在排序 a[]={1,2,3,4,5,6,7,8,10,9}这组数据,首先我们分析这组数的特点,是前面的数大部分有序,后面小部分无序。如果我们按照冒泡排序的思想,在第一次循环遍历的时候,就将10和9进行了交换,这个时候数组已经变成有序了,但是依旧会循环遍历8次,接下来的8次是多余的,什么也没做。所以我们可以在交换的地方加一个标记,如果某一趟排序没有交换元素,说明这组数据已经有序了。

//a为数组,n为数组元素个数
void bubbleSortOptimize_1(int a[],int n)
{   
    //flag用来标记是否进行过交换,0为没交换,1为交换了
    int flag;
    //k用来标记当前循环要确定的index下标,初始下标是数组最后一位
    int k=n-1;
    //n个元素,需要进行n-1次遍历
    for(i=0;i<n-1;i++)
    {
        flag=0;
        for(j=0;j<k-1;j++)
        {
            if(a[j]>a[j+1])
            {
                //条件成立,需要执行交换动作
                SWAP(a[j],a[j+1]);
                flag=1;
            }     
        }
        //如果内层for循环一次,一次交换都没有发生,则意味着数组有序
        if(flag==0) 
            return;
        
        k--;
    
    }

}

第二种优化思路:

第一种优化思路仅适用于前面大部分有序后面小部分无序的数据(例如:1,2,3,4,7,6,5),但是对于前面大部分是无序而后面小部分有序的数据(例如:1,2,5,7,4,3,6,8,9,10)的排序效率也不可观。
对于前面大部分无序后面小部分有序这种类型的数据,我们可以继续优化,即我们可以记录下最后一次交换的位置,后面没有交换,必然是有序的,然后下一次排序从第一个比较到上次记录的位置结束即可。

void bubbleSortOptimize_2(int a[],int n)
{
    //k用来表示在一次内层循环中,最大值需要放置的位置index
    int k=n-1;
    //flag来自于优化思路1
    int flag;
    //利用pos来记录最后一次交换的位置
    int pos;
    
    for(i=0;i<n-1;i++)
    {
        pos=0;
        flag=0;
        for(j=0;j<k-1;j++)
        {
            if(a[j]>a[j+1])
            {
                SWAP(a[j],a[j+1]);
                flag=1;
                pos=j;
            }
        }
        if(flag==0)
            return;
        k=pos; //下一次比较到记录位置即可
 
    }

}

第三种优化思路
第二种优化思路的效率有了很大的提升,还有一种优化方法可以继续提高效率。大致思想就是一次排序可以确定两个数的位置,正向扫描找到最大值交换到最后,反向扫描找到最小值交换到最前面。例如:排序数据1,2,3,4,5,6,0。


void bubbleSortOptimize_3(int a[],int n)
{
    int maxPos=n-1;//记录最大值的下标
    int minPos=0; //记录最小值的下标
    
    int flag; //来源于优化思路一
    int swapPos; //来源于优化思路二
    
    //首先确定外层循环次数,一次确定2个数,则进行n/2次循环即可
    for(int i=0;i<n/2;j++)
    {
        flag=0;
        swapPos=0;
        //正向寻找最大值
        for(j=0;j<maxPos;j++)
        {
            if(a[j]>a[j+1])
            {
                SWAP(a[j],a[j+1]);
                flag=1; //发生交换
                swapPos=j;//记录最后一次交换的为知
            }
        }
        if(flag==0)//如果没有交换过元素,则已经有序
            return;
        maxPos=swapPos; //下一次比较到记录位置即可
        //反向寻找最小值
        for(j=maxPos;j>minPos;j--)
        {
            if(a[j]<a[j-1])
            {
                SWAP(a[j],a[j-1]);
            }
        }
        
        minPos++;
    }

}

2.2、快速排序

2.2.1 快速排序的思想

快速排序是由东尼霍尔所发明的一种排序算法,它采用分治的思想,首先在要排序的序列中选取一个基准数(一般选取序列的第一个),将序列分成两部分,其中基准数的左边都是小于基准数的数,基准数的右边都是大于或等于基准数的数。这样,基准数的位置在序列中的位置就固定了,然后将基准数两遍的序列进行相同的处理,直到最后一个序列只有一个数字,这样算法就完成了。

算法规则:
1、从数列中挑出一个元素,称为基准;
2、所有元素比基准值小的摆在基准值的左边,比基准值大的摆在基准值的右边(相同的可以在任意一边);
3、把小于基准值的子序列和大于基准值的子序列按上述规则递归排序。

举例:
image.png

代码实现:

void QuickSort(int a[],int begin,int end)
{
    if(begin>=end) return;
    
    //把这个当做基准,一般选择数组第一个元素
    int baselineValue=a[begin]; 
    int baselineIndex=begin;
    int i=begin;
    int j=end;
    while(i<j)
    {
        //从右到左寻找第一个小于基准的数
        while(i<j && a[j]>=baselineValue)
            j--;
        if(i<j) //则是a[j]<baselineValue   
        {
            a[i]=a[j];
            i++;
        }
        //从左到右寻找第一个大于基准的数
        while(i<j && a[i]<=baselineValue)
            i++;
        if(i<j) //则是a[i]>baselineValue
        {
            a[j]=a[i];
            j--;
        }
    }
    //跳出while循环的条件是i=j,此时就是基准应该放的位置
    a[i]=baselineValue;
    baselineIndex=i;
    
    //递归调用,基准左右两边的子序列分别进行排序
    QuickSort(a,begin,baselineIndex-1);
    QuichSort(a,baselineIndex+1,end);

}

算法性能分析:
1、时间复杂度

快速排序的最坏时间复杂度是O(n*n),最坏情况是序列逆向有序,这样每次基准的位置都是在最边上,两个子序列其中有一个子序列为空。

快速排序的平均时间复杂度是O(n*logn)。这个平均时间复杂度是怎么计算出来的?
首先我们知道快速排序是一个递归算法,而递归算法的时间复杂度=递归次数*每次递归遍历的次数。
我们可以把快速排序近似想象成一个完全二叉树

一个数组的容量是n,第一层遍历的次数是n,因为数组里每个数字都需要和key比较,那么接下来遍历分出来的两个区间,总的遍历次数还是会近似是N,以此类推,直到分为最后一个,也就是说每次递归的遍历次数是N。
而树的高度是logn,也就是递归次数是logn,所以总的时间复杂度是n*logn。

2、空间复杂度
在对序列的操作过程中只需要花费常数级别的空间,空间复杂度为S(1)。但需要注意递归调用需要花费最少S(logn),最多S(n)的空间。
最少的情况是:每次基准的位置都能将序列对半分。
最多的情况是:每次基准的位置都在边缘,这样的话,子序列就只有一个。这样递归调用是一个链式,链上有n个节点。
3、排序稳定性
快速排序是一种不稳定的排序算法

2.2.2 由快速排序时间复杂度计算引申出来的问题

有100万个无序数字,请找出位置排在第10万的数字。
这个问题,首先不是大数据的问题,内存是可以放下的,这是快速排序的变形问题。位置在第10万,其实就是让我们找基准下标在第10万。

int PartSort(int a[],int begin,int end)
{

    int div=begin; //基准下标
    int divValue=a[begin]; //基准的值
    int i=begin;
    int j=end;
    
    while(i<j)
    {
        //从右往左找小于基准的数
        while(i<j&&a[j]>divValue)
            j--;
        if(i<j) //a[i]<divValue
        {
            a[i]=a[j]
            i++;
        }
        //从左往右找大于基准的数
        while(i<j&&a[i]<divValue)
            i++;
        if(i<j) //a[i]>divValue
        {
            a[j]=a[i]
            j--;
        }  
    }
    //跳出循环i=j
    a[i]=divValue;
    div=i;
    return div; //返回基准此刻的下标
}
//快速排序
void QuickSort(int a[],int begin,int end)
{
    if(begin>=end)
        return;
    int div=PartSort(a,begin,end);
    QuickSort(a,begin,div-1);
    QuickSort(a,div+1,end);
}


//快速排序变种问题的求解
int find_10wan_from_100wan(int a[],int begin,int end)
{
    if(begin>=end)
        return;
        
    int div=PartSort(a,begin,end);
    if(div==100000)
        return a[div];
    else if(div>100000)
        find_10wan_from_100wan(a,begin,div-1);
    else
        find_10wan_from_100wan(a,div+1,end);
}

变种问题的时间复杂度分析(这块暂定,不是很懂)
这个代码的时间复杂度是多少呢?我们可以用树形结合的方法,这个算法相当于一直走树的一个枝,另外一个枝没有走,我们假定走的是左枝,这其实就相当于变成了单链表,那遍历单链表的时间复杂度其实就是O(n),所以,这个算法的时间复杂度是O(n)。

3、选择排序

3.1 简单选择排序

3.1.1 简单选择排序算法

选择排序是一种简单的排序算法。算法的思想主要是:
1、初始状态,将一个数组元素分为无序区和有序区,有序区为空,无序区初始为a[0...n-1].
2、第1趟排序:在无序区a[0...n-1]中选出关键字最小的元素a[k],将它和无序区的第一个元素a[0]交换,使得有序区变成a[0],无序区缩减为a[1...n-1]。
3、第i趟排序:经过i趟排序,此时有序区为a[0... i-1],无序区变成a[i...n-1]。
4、第i+1趟排序:经过前面i趟排序,此时有序区为a[0... i-1],无序区变成a[i...n-1]。从无序区a[i...n-1]中选出关键字最小的记录a[k],与无序区第一个元素a[i]进行交换,使得有序区变成a[0...i],无序区缩减变成a[i+1....n-1]。
这样,数组长度为n,直接选择排序经过n-1趟排序可以得到有序结果。

image.png

代码实现

void SelectSort(int a[],int n)
{
    int min;
    //确定循环次数,n个数,只需要选n-1次即可
    for(int i=0;i<n-1;i++)
    {
        min=i;
        //从无序区a[i...n-1]中选出最小的数,放到a[i]处
        //使得有序区变成a[0..i],无序区变成a[i+1...n]
        for(int j=i+1;j<n;j++)//这个for循环用来选出最小数
        {
            if(a[j]<min)
                min=j;
        }
        if(a[i]>a[j])
            SWAP(a[i],a[j]);
    
    }
    
}

算法性能分析
1、时间复杂度
选择排序的时间复杂度是O(n*n),但是选择排序的性能要优于冒泡排序。
2、空间复杂度是O(1)
3、排序稳定性
选择排序是一个不稳定的排序算法

3.1.2 选择排序的优化

简单的选择排序是一次确定一个元素的位置,而选择排序的优化则是一次确定两个元素的位置,比如说升序排列,每次将最小值放到起始位置,将最大值放到末尾位置。

评论

暂无评论