《算法与数据结构学习笔记》-时间复杂度O(n2)的几个排序法比较

首先分析一个算法的好坏要考虑以下几点：

1.算法的执行效率：
最好情况、最坏情况、平均情况时间复杂度
时间复杂度的系数、常量、低阶
比较次数和交换次数

2.排序算法的内存消耗:这里指的就是空间复杂度，空间复杂度为O(1)的算法叫做原地算法。

3.排序算法的稳定性：稳定性指的是排序后的等值元素是否是原有的先后顺序。这个是有很大实际意义的。

接下来分别看看几个时间复杂度为O(n2)的排序算法，最后我们说说他们各自的优劣

冒泡排序

只要学过编程语言的对这个都不会陌生，比较相邻元素的大小关系，如果不满足条件就交换位置。 冒泡排序1.jpg
冒泡排序2.jpg 冒泡排序3.jpg

c语言代码如下

void bubblingSort(int * a , int size){
    for (int i=0; i<size; i++){
        int flag = 0;
        for (int j=0; j<size-i; j++){
            if (a[j] > a[j+1]){
                int tmp = a[j];
                a[j] = a[j+1];
                a[j+1] = tmp;
                flag = 1;
            }
        }
        if (flag == 0){
            break;
        }
    }
}
int main(int argc, const char * argv[]) {
    // insert code here...
    int a[10] = {2,1,2,4,11,22,42,5,9,10};
    bubblingSort(a, 10);
    for (int i = 0; i<10; i++){
        printf("%d\n",a[I]);
    }
    return 0;
}

这里面做了一个优化，如果没有交换元素，就说明所有的位置已经排好，直接结束排序就可以。
回过头来用上面的几点分析一下冒泡排序。
它是原地排序算法吗？
很明显，整个过程只需要常量阶的临时空间，空间复杂度为O(1)，是原地排序算法。
它是稳定的排序算法吗
我们看交换元素的部分，当元素相等时并没有任何操作，所以是稳定的排序算法。
它的时间复杂度是多少
这里有两次循环，所以时间复杂度为O(n2),最好时间复杂度是O(n),最坏时间复杂度为O(n2)

插入排序

举个形象的栗子🌰，插入排序就像我们抓扑克牌，抓到一张会把它插到适当的位置，它的前面比它小，后面比它大。

插入排序.jpg

代码如下：

void insertSort(int * a, int size){
    for (int i=1; i<size; i++){
        for (int j=0; j<i; j++){
            if (a[j] > a[I]){
                int tmp = a[j];
                a[j] = a[I];
                a[i] = tmp;
            }
        }
    }
}
int main(int argc, const char * argv[]) {
    // insert code here...
    int a[10] = {2,1,2,4,11,22,42,5,9,10};
    insertSort(a, 10);
    for (int i = 0; i<10; i++){
        printf("%d\n",a[I]);
    }
    return 0;
}

是原地排序算法吗
插入排序不需要额外的存储空间，空间复杂度为O(1)，是原地排序算法。
是稳定的排序算法吗
对于相同值得元素可以选择将后出现的元素插入到前面出现的元素后面，所以是稳定的。
插入排序的时间复杂度是多少
最好时间复杂度为O(n),最坏时间复杂度为O(n2),平均时间复杂度为O(n2)

选择排序

选择排序类似于插入排序，也分排序区间和未排序区间，每次选出未排序区间中的最小值插入排序区间。

选择排序.jpg

代码如下

void selectionSort(int *a, int size){
    for (int i=0; i<size; i++){
        int minIndex = i;
        int minElement = a[i];
        for (int j=i; j<size; j++){
            if (a[j]<minElement){
                minIndex = j;
                minElement = a[j];
            }
        }
        if (i != minIndex){
            int tmp = a[i];
            a[i] = a[minIndex];
            a[minIndex] = tmp;
        }
    }
}
int main(int argc, const char * argv[]) {
    // insert code here...
    int a[10] = {2,1,2,4,11,22,42,5,9,10};
    selectionSort(a, 10);
    for (int i = 0; i<10; i++){
        printf("%d\n",a[i]);
    }
    return 0;
}

是原地排序算法吗
插入排序不需要额外的存储空间，空间复杂度为O(1)，是原地排序算法。
是稳定的排序算法吗
选择排序会从未排序范围内取最小值，与前面的元素交换，这样就破坏了稳定性。
插入排序的时间复杂度是多少
最好时间复杂度为O(n),最坏时间复杂度为O(n2),平均时间复杂度为O(n2)