Chapter2: 时间复杂度分析、递归、查找与排序

6. 冒泡排序、插入排序、选择排序

0. 时间复杂度

这三大经典排序算法的时间复杂度都是 O() , 在数据规模大的时候时间代价差别不大，在数据规模小的时候，会发现冒泡排序所耗费的时间大概是其他O() 算法的两倍,是因为冒泡排序交换了两次数,所以要乘个2

1. 冒泡排序

基本思想

元素两两比较，将最大/最小元素交换到队尾

从无序序列头部开始，进行两两比较，根据大小交换位置，直到最后将最大（小）的数据元素交换到了无序队列的队尾，从而成为有序序列的一部分；下一次继续这个过程，直到所有数据元素都排好序。

代码

/*冒泡排序
结果：从小到大排列数组
参数：输入数组地址arr,数组长度arrLen 
*/
void bubbleSort(int* arr,int arrLen){
    for(int i=0;i<arrLen;i++){//从第1个元素开始 
        for(int j=0;j<arrLen-i-1;j++){//从第2个元素开始，直至无序序列队尾
             if(arr[j]>arr[j+1]){
                int tmp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=tmp;
             } 
        }   
    }
}

冒泡排序的优化

上述代码还可以进行优化,比如当数组是{1 2 3 4 5}时已经是有序了,可上述代码还是会执行n(n-1)/2次,可以添加一个是否排序的标志进行判断

/*冒泡排序优化：添加是否已排序的标志
结果：从小到大排列数组
参数：输入数组地址arr,数组长度arrLen 
*/
void bubbleSort(int* arr,int arrLen){
    bool isSort=true;
    for(int i=0;isSort && i<arrLen;i++){//从第1个元素开始 
        isSort=false;
        for(int j=0;j<arrLen-i-1;j++){//从第2个元素开始，直至无序序列队尾
             if(arr[j]>arr[j+1]){
                int tmp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=tmp;
                isSort=true;
             } 
        }   
    }
}

2. 插入排序

基本思想

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤 3，直到找到小于或等于新元素的已排序的元素
5. 将新元素插入到该元素的位置后
6. 重复步骤 2~5

插入排序原理示意

代码

/*插入排序
结果：从小到大排列数组
参数：输入数组地址arr,数组长度arrLen
*/
void insSort(int* arr,int arrLen){
    for(int i=1;i<arrLen;i++){//遍历无无序部分 
        int tmp = arr[i];
        int j=i-1;
        while(tmp<arr[j] && j>0){//从后往前遍历有序部分
            arr[j+1]=arr[j];
            j--;
        }
        arr[j+1]=tmp;       
    } 
}

3. 选择排序

基本思想

将待排序序列分为两部分，一部分为有序序列，另一部分为无序序列。

第一趟：从a[0]到a[n-1]中找到最小的数a[i]，然后将a[i]与a[0]交换，

第二趟：从a[1]到a[n-1]中找到最小的数a[j]，然后将a[j]与a[1]交换

第三趟：从a[2]到a[n-1]中找到最小的数a[k],然后将a[k]与a[2]交换 ……

代码

/*选择排序
结果：从小到大排列数组
参数：输入数组地址arr,数组长度arrLen 
*/
void selectSort(int* arr,int arrLen){
    for(int i=0;i<arrLen;i++){
        int min=arr[i];
        for(int j=i+1;j<arrLen;j++){
            if(min>arr[j]){
                int tmp=min;
                min=arr[j];
                arr[j]=tmp;
            }
        }
        arr[i]=min;
    }
}

4. 参考资料

[1] 冒泡排序

[2] 选择排序

[3] 插入排序步骤讲解与实例分析

[4] 插入排序图文讲解

[5] 冒泡排序的优化