python选择排序时间复杂度

╰+哭是因爲堅強的太久メ 2023-10-07 17:49 50阅读 0赞

选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，  
冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。  
排序算法不稳定的含义是:在排序之前,有两个数相等. 但是在排序结束之后,它们两个有可能改变顺序.

##### 1 前言 #####

给定一个整数序列，按照从小到大的顺序（确切地说，是非递减的顺序）排列序列中的整数

选择排序的思想：选出最小的一个和第一个位置交换，选出其次小的和第二个位置交换 ……  
直到从第N个和第N-1个元素中选出最小的放在第N-1个位置。

##### 2 选择排序写法一 #####

def select_sort(li):
        li_new = []
        for i in range(len(li)):
            # 选出数组li中的最小值
            min_val = min(li)
            print("i %d %d" % (i, min_val))
            # 向临时数组中添加最小元素
            li_new.append(min_val)
            # 移除原数组中的最小元素
            li.remove(min_val)
            
            print(li)
    
        return li_new

执行

li = [3, 2, 4, 7, 1, 2]
    # 排序前
    print(li)
    print("-----------")
    # 执行排序
    netList = select_sort(li)
    print("-----------")
    # 排序后
    print(netList)

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5pep6LW355qE5bm06L275Lq6_size_20_color_FFFFFF_t_70_g_se_x_16]

##### 3 选择排序写法二 #####

def select_sort2(li):
        for i in range(len(li) - 1):
            # 记录最小值的角标
            min_index = i
            for j in range(i + 1, len(li)):
                # 如果当前值小于 min_index 角标下的值 
                if li[j] < li[min_index]:
                    # 就进行值替换 目的是将最小的值放在最左侧
                    li[i], li[min_index] = li[min_index], li[i]
                    print(li)

执行

li = [3, 2, 4, 7, 1, 2]
    # 排序前
    print(li)
    print("-----------")
    # 执行排序
    select_sort2(li)
    print("-----------")
    # 排序后
    print(li)

执行结果  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5pep6LW355qE5bm06L275Lq6_size_20_color_FFFFFF_t_70_g_se_x_16 1]

##### 4 时间复杂度 #####

第一次内循环比较N - 1次，然后是N-2次，N-3次，……，最后一次内循环比较1次。  
共比较的次数是 (N - 1) + (N - 2) + … + 1，求等差数列和，得 (N - 1 + 1)\* N / 2 = N^2 / 2。  
舍去最高项系数，其时间复杂度为 O(N^2)。

虽然选择排序和冒泡排序的时间复杂度一样，但实际上，选择排序进行的交换操作很少，最多会发生 N - 1次交换。  
而冒泡排序最坏的情况下要发生N^2 /2交换操作。从这个意义上讲，交换排序的性能略优于冒泡排序。而且，交换排序比冒泡排序的思想更加直观。

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5pep6LW355qE5bm06L275Lq6_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/7d0cea4b46974bd4a2adb4047a18a39a.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5pep6LW355qE5bm06L275Lq6,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5pep6LW355qE5bm06L275Lq6_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/41ff87bc8e3d460cb03cced61a51f584.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5pep6LW355qE5bm06L275Lq6,size_20,color_FFFFFF,t_70,g_se,x_16