Question

请在这三种排序方式(直接插入排序,冒泡排序,快速排序)中任意选择一种,对集合{49,38,65,97,76,13,27}按由

请在这三种排序方式（直接插入排序，冒泡排序，快速排序）中任意选择一种，对集合{49，38，65，97，76，13，27}按由小到大进行排序，并分析所选排序方式的时间复杂度和空间复杂度。

Answer 1

改进型冒泡排序算法：

1. 时间复杂度为 O(n^2)： 非改进型没有最优情况

   最优情况是O(n)：整个序列已经有序

   最坏情况是O(n^2): 整个序列逆序 ，需要比较(1 + (n - 1)) * (n - 1) / 2次等于n*(n - 1)/2  

2.  空间复杂度是O(1)：使用了一个临时变量用于标识当前趟比较是否存在交换，非改进型其空间复杂度为0，无需借助外部空间，当然若增加一个交换时使用的临时变量的话其空间复杂度也是O(1)

void bubble(int array[], int length)
{
    bool exchanged = true;
    for (int i = length - 1; i > 0 && exchanged; i--)
    {
       exchanged = false;
       for (int j = 0; j < i; j++)
       {
            if (array[j] > array[j + 1])
            {
                array[j] = array[j] + array[j + 1];
                array[j + 1] = array[j] - array[j + 1];
                array[j] = array[j] - array[j + 1];
                exchanged = true;
            }
       }
    }
}

 

void main()

{

    int array[] = {49，38，65，97，76，13，27};

    int length = 7;

    bubble(array, length);

    for ( int i = 0; i < 7; i ++)

        printf("%d ", array[i]);

}

追问

改进型冒泡是快速排序吗？

追答

不是，还是冒泡排序。
只是在排序序列基本有序时会可以在更早的时刻结束整个排序过程。