首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

如何在python中返回Selection Sort递归中交换次数的值

在Python中返回Selection Sort递归中交换次数的值,可以通过定义一个全局变量来记录交换次数,并在递归函数中进行累加。以下是一个示例代码:

代码语言:txt
复制
swap_count = 0  # 全局变量,用于记录交换次数

def selection_sort(arr):
    global swap_count  # 声明使用全局变量
    n = len(arr)
    
    for i in range(n-1):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
                swap_count += 1  # 每次交换时累加交换次数
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    
    return arr

# 测试示例
arr = [5, 3, 8, 2, 1]
sorted_arr = selection_sort(arr)
print("排序后的数组:", sorted_arr)
print("交换次数:", swap_count)

在上述代码中,我们使用了一个全局变量swap_count来记录交换次数。在每次交换时,通过swap_count += 1来累加交换次数。最后,我们可以通过打印swap_count来获取Selection Sort递归中交换次数的值。

请注意,这只是一个示例代码,实际应用中可能需要根据具体情况进行适当的修改和调整。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

python算法与数据结构-选择排序(33)

一、选择排序介绍   选择排序(Selection sort)是一种简单直观排序算法。...选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素排序方法,选择排序属于非常好一种。...四、选择排序总结 有N个数据,需要从未排序区挑选N-1次数据放在已排序区队尾 每次从未排序区挑选数据要放在已排序队尾 五、选择排序python代码实现 # 定义选择排序函数 def selection_sort...那么,在一趟选择,如果一个元素比当前元素小,而该小元素又出现在一个和当前元素相等元素后面,那么交换后稳定性就被破坏了。...比较拗口,举个例子,序列5 8 5 2 9,我们知道第一遍选择第1个元素5会和2交换,那么原序列两个5相对前后顺序就被破坏了,所以选择排序是一个不稳定排序算法。

37330

Python-排序-选择排序-优化

unsort = [3,4,2,1,5,6,7,8] print("selection_sort 结果",*selection_sort(unsort)) 运行结果如下: [3, 4, 2, 1,...}") return data_list 同样地执行一下,和未优化对比总循环次数和选择次数 unsort = [3,4,2,1,5,6,7,8] print("selection_sort2..., 5, 6, 7, 8] [1, 2, 3, 4, 5, 6, 7, 8] 总循环次数为 12 selection_sort2 结果 1 2 3 4 5 6 7 8 从结果可以看出比未优化版总循环次数少了...在实际应用,当数据量很大时,优化结果还是很可观。 性能分析 首先,选择排序只需要一个变量做为交换,因此空间复杂度是O(1),是一种原地排序算法。...其次,选择排序在未排序区间选择一个最小,与前面的元素交换,对于相同元素,因为交换会破坏他们相对公交车,因此它是一种不稳定排序算法。

74010
  • Python——关于排序算法(选择排序法)

    选择排序法(selection sort) 先来看一下百度百科定义: 选择排序法 是对 定位比较交换法(也就是冒泡排序法) 一种改进。...选择排序基本思想是:每一趟在n-i+1(i=1,2,…n-1)个记录中选取关键字最小记录作为有序序列第i个记录。基于此思想算法主要有简单选择排序、树型选择排序和堆排序。...简单选择排序基本思想:第1趟,在待排序记录r[1]~r[n]中选出最小记录,将它与r[1]交换;第2趟,在待排序记录r[2]~r[n]中选出最小记录,将它与r[2]交换;以此类推,第i趟在待排序记录...假设列表元素是刚好逆序:比如[6,5,4,3,2,1]那第一轮就要比较5次取得最小,第二轮4次……1次,总共次数就是1/2*5*(5+1)也就是1/2*(N-1)*N,时间复杂度是n平方。...,但是呢,python有自带内置语法,就是sorted(num:list)和num.sort(),显然这个内置算法是更更更快,平时如有用到排序,可别无聊到自己写一个低效哟。

    67430

    排序之简单排序

    需求: 排序前:{4,6,8,7,9,2,10,1} 排序后:{1,2,4,5,7,8,9,10} 排序原理: 1.每一次遍历过程,都假定第一个索引处元素是最小,和其他索引处依次进行比较,如果当前索引处大于其他某个索引处...,则假定其他某个索引出为最小,最后可以找到最小所在索引 2.交换第一个索引处和最小所在索引处 ?...选择排序API设计: 类名 Selection 构造方法 Selection():创建Selection对象 成员方法 1.public static void sort(Comparable[] a)...exch(Comparable[] a,int i,int j):交换a数组,索引i和索引j处 package cn.silentcow.comparable; /** * @author...,内层循环完成了数据比较,所以我们分别统计数据交换次数和数据比较次数: 数据比较次数: (N-1)+(N-2)+(N-3)+…+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2; 数据交换次数

    38920

    Java面试-基础篇

    A[M] 与待搜索 T 进行比较 ① A[M] == T 表示找到,返回中间索引 ② A[M] > T,中间右侧其它元素都大于 T,无需比较,中间索引左边去找,M - 1 设置为右边界,重新查找...48 结点时,查找成功需要比较次数 使用二分法在序列 1,4,6,7,15,33,39,50,64,78,75,81,89,96 查找元素 81 时,需要经过( )次比较 在拥有128...(需要一个索引指向最小) 重复以上步骤,直到整个数组有序 优化点:为减少交换次数,每一轮可以先找最小索引,在每轮最后再交换元素 算法实现 java C public static void...selection(int[] a) { for (int i = 0; i < a.length - 1; i++) { // i 代表每轮选择最小元素要交换目标索引...但如果集合有序度高,冒泡优于选择 冒泡属于稳定排序算法,而选择属于不稳定排序 稳定排序指,按对象不同字段进行多次排序,不会打乱同元素顺序 不稳定排序则反之 插入排序 算法描述 将数组分为两个区域

    63250

    十大经典排序算法介绍及实现

    冒泡排序可以在算法添加一个变量记录每轮迭代是否发生位置交换,如果某一轮发现没有任何位置交换,说明数组已经是有序,可以直接退出,无需再进行后续迭代了。...举个例子:对于数组[5,2,5,3,1],在第一轮迭代交换变成了[1,2,5,3,5],这样原本排在前面的5移动到了第2个5后面。...def selection_sort(nums: List[int]) -> List[int]: n=len(nums) for i in range(n): min=...由于使用了递归,每次递归中需声明一个pivot,所以总共需要占用 O(\log n) 栈空间。...计数排序 统计每个数值出现次数,用counter数组记录,counter下标j是具体数值counter[j]表示次数,枚举counter将次数大于0j依次填回到原数组。

    40120

    Leetcode 【524、767、1053、1079】

    如果答案不止一个,返回长度最长且字典序最小单词。如果答案不存在,返回空字符串。 双指针法。对于单词数组每个单词 word,字符串 s 和 word 逐字符比较向后滑动。...方法1(Sort): 以 S = "acbaa" 为例,先按照 S 每个字母出现次数从大到小排列,得到一个列表, A = ['a','a','a','b','c'],然后建立一个和 S 相同长度列表...first 是从右到左遍历第一个逆序对 A[i] > A[j] i 位置( [8,5,7,2,4] 从右到左遍历第一个逆序对为 7 > 2,则交换第一个位置就是 first = 2)。...第二个交换位置 second 是从 first 下一个位置开始,小于 A[first] 且最靠近 A[first] 最大索引位置( [1,9,4,6,10] ,first = 1,小于 A...[1] = 9 最大为 6,其对应索引 second = 3;再比如 [3,1,1,3] ,first = 0,小于 A[0] = 3 最大是 1,但是要选择最靠近 A[first] 1,

    70930

    经典递归问题--汉诺塔(java实现)

    经典递归问题–汉诺塔(java实现) 一、什么是递归 1.递归定义 程序调用自身编程技巧称为递归; 求阶乘: public static int fac(int n) {...2.递归过程详细解释 我们通常能够看懂简单递归代码,但是自己上手写时候却总是想不到思路,这是因为我们对递归理解不够深入; 下面是对递归深入理解: 递归是一个整体动作 递归中 和 归...分别是两个独立过程 --> 开辟函数栈帧, 归 --> 销毁函数栈帧 程序执行递归过程 是先后归过程, 也是不断开辟函数栈帧把参数传递过去 ;同时不断返回数值,然后销毁函数栈帧过程...(关于什么是函数栈帧可以看我相关博客:http://t.csdnimg.cn/opIPf 最后部分内容 ) 下面是图例解释: 我们在上述图片可以看到: 红色箭头所指部分均是...A->C B->C C->A A->C B->A B->C A->C 2.过程分析 从上述过程我们知道,随机盘数增加,其移动次数成指数式增长,代码也会变得复杂; 为了缩减代码复杂度,我们使用 递归方法来解决问题

    14110

    golang刷leetcode各种排序算法

    void selection_sort (int a[], int n) { int i,j,pos,tmp; for (i=0; i<n-1; i++) {      //寻找最小下标...,这样会在递归中消耗大量空间。...这种增量选择方法好处是可以使数组整体均匀有序,尽可能减少比较和移动次数,二分法即使前一半数据有序,后一半如果有比较小数据,还是会造成大量比较和移动,因此这种增量方法和插入排序配合更佳。...,即累加数组中最小到a之间每个数字出现次数(未出现则为0),而每个数字出现次数可以通过扫描一遍数组获得。...计数排序步骤: 找出待排序数组中最大和最小元素(计数数组C长度为max-min+1,其中位置0存放min,依次填充到最后一个位置存放max) 统计数组每个为i元素出现次数,存入数组C

    26510

    面试专题-基础篇

    (3、4两步) 获取中间索引 M = Floor((L+R) /2) 中间索引 A[M] 与待搜索 T 进行比较 ① A[M] == T 表示找到,返回中间索引 ② A[M] >...48 结点时,查找成功需要比较次数 使用二分法在序列 1,4,6,7,15,33,39,50,64,78,75,81,89,96 查找元素 81 时,需要经过( )次比较 在拥有128...重复以上步骤,直到整个数组有序 更形象描述请参考:selection_sort.html 算法实现 public static void selection(int[] a) {...演示了空穴法改进双边快排,比较次数更少 day01.sort.QuickSortHoare 演示了霍尔分区实现 day01.sort.LomutoVsHoare 对四种分区实现移动次数比较 7....,更新时间复杂度是 O(1),而红黑树查找,更新时间复杂度是 O(log_2⁡n ),TreeNode 占用空间也比普通 Node 大,非必要,尽量还是使用链表 hash 如果足够随机,则在

    58830

    超全递归技巧整理,这次一起拿下递归

    为了避免重复计算,可以使用一个数据结构(比如散列表)来保存已经求解过 f(k) 。当递归到 k 时候判断,f(k) 是否已经求解过了,如果求解过了,那么直接返回,不需要重复计算。...上述过程可以画出如下递归树。第一层有 n 个交换操作,第二层有 n 个节点,每个节点分解需要 n-1 次交换,所以第二层所需要进行交换次数是 n(n-1)。...依次类推,第三层所需要交换次数是 n(n-1)(n-2),第 k 层所需要交换次数是 n(n-1)...(n-k+1),最后一层交换次数是 n(n-1)...2。 ?...最终每一层交换次数之和就是总交换次数之和。最后一层交换次数是 n! 次,而其他层交换次数肯定小于 n! 次,因此最终时间复杂度肯定是大于 O(n!),但小于 O(n*n!)。...那么,递归树从根节点到树任意节点路径,都对应着某个时刻函数调用链组成堆栈。递归越深节点月靠近栈顶,也就越早返回

    1.2K20

    算法和数据结构:快速排序

    ]比a[lo]小,a[i]比a[lo]大,所以将基准元素与a[j]交换 Swap(array, lo, j); //返回扫描相遇位置点 return j; } 划分前后,元素在序列分布如下图...三分区快速排序示意图如下: ? Dijkstra三分区快速排序虽然在快速排序发现不久后就提出来了,但是对于序列重复不多情况下,它比传统2分区快速排序需要更多交换次数。...在划分过程,i遇到与v相等元素交换到最左边,j遇到与v相等元素交换到最右边,i与j相遇后再把数组两端与v相等元素交换到中间 ?...这个方法不能完全满足只扫描一次要求,但它有两个好处:首先,如果数据没有重复,那么该方法几乎没有额外开销;其次,如果有重复,那么这些重复不会参与下一趟排序,减少了无用划分。...五 .NET 中元素排序内部实现 快速排序作为一种优秀排序算法,在很多编程语言元素内部排序均有实现,比如Java对基本数据类型(primitive type)排序,C++,Matlab,Python

    30740

    排序算法python实现

    当下 ║ 2018.12.12 人生苦短,我们都要用Python,不定期更新Python相关知识点 知识点 所谓排序,就是使一串记录,按照其中某个或某些关键字大小,递增或递减排列起来操作。...选择排序(Selection sort)是一种简单直观排序算法。...此外,与选择排序不同是,需要考虑到如果第i轮里,恰好第i个数就是最大时,先交换minindex和i之后,最大下标变成了minindex,这时候应该交换minindex和n-i-1,而不是maxindex...4、冒泡排序法改进 在最好情况下,冒泡排序法依然会执行每个循环但不进行任何操作,可以设定一个标记判断冒泡排序法在一次内层循环中是否进行了交换,如果没有,说明算法已经使排好序,就可以直接返回,不过这种方法只是对最好情况进行了改进...在第一部分排序完成后,再将这个最后元素插入到已排好序第一部分。 插入排序基本思想是:每步将一个待排序记录,按其关键码大小插入前面已经排序文件适当位置上,直到全部插入完为止。

    47330

    数据结构与算法 - 排序与搜索排序与搜索

    持续每次对越来越少元素重复上面的步骤,直到没有任何一对数字需要比较。 冒泡排序分析 交换过程图示(第一次): ? 那么我们需要进行n-1次冒泡过程,每次对应比较次数如下图所示: ?...def bubble_sort(alist): for j in range(len(alist)-1,0,-1): # j表示每次遍历需要比较次数,是逐渐减小...最坏时间复杂度:O(n2) 稳定性:稳定 冒泡排序演示 效果: ? 2.选择排序 选择排序(Selection sort)是一种简单直观排序算法。它工作原理如下。...选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素排序方法,选择排序属于非常好一种。...步骤为: 1.从数列挑出一个元素,称为"基准"(pivot), 2.重新排序数列,所有元素比基准摆放在基准前面,所有元素比基准摆在基准后面(相同数可以到任一边)。

    80830

    Python算法——选择排序

    选择排序(Selection Sort)是一种简单排序算法,它基本思想是在未排序部分中选择最小(或最大)元素,然后将其放在已排序部分末尾。...选择排序不同于冒泡排序,它不需要反复交换元素,因此在某些情况下可能比冒泡排序更快。本文将详细介绍选择排序工作原理和Python实现。...22, 25, 64] 第五轮选择,最小元素为 64,交换位置后数组不变:[11, 12, 22, 25, 64] Python实现选择排序 下面是Python选择排序实现: def selection_sort...示例代码 下面是一个使用Python进行选择排序示例代码: def selection_sort(arr): n = len(arr) for i in range(n):...min_index = j arr[i], arr[min_index] = arr[min_index], arr[i] # 测试排序 arr = [64, 25, 12, 22, 11] selection_sort

    20310

    🛰️ 递归思想

    递归理解:在程序可以调用函数来完成任务,为了完成相同任务可以调用同一个函数。如果在函数调用函数本身,那么改函数就被称为递归函数。...无限递归(而不归、死递归),栈溢出(函数调用有时间和空间开销,一个程序同时调用函数个数是有限)。...图片递归函数分为两类:在过程解决问题在归来过程解决问题举例说明:图片去过程解决问题:前面人手中子弹总数加上自己手上,告诉下一个人,最后把子弹总数回传给上一个人。...图片归来过程解决问题:把消息传递下去,让最后的人把手中子弹数告诉前一个人,前一个人加上后一个人告知数量,继续向前传递。图片递归函数参数在每次调用时应该是不同!...----循环和递归:递归函数调用有时间和空间开销,而且递归次数受到堆栈大小限制。循环没有函数调用和返回参数传递和返回额外开销,更快。如何在递归和循环之间选择?

    795161

    各种排序算法分析及java&python实现

    二分插入排序比较次数与待排序记录初始状态无关,仅依赖于记录个数。当n较大时,比直接插入排序最大比较次数少得多。但大于直接插入排序最小比较次数。...2.1 直接选择排序 基本思想 在要排序一组数,选出最小一个数与第一个位置交换;然后在剩下数当中再找最小与第二个位置交换,如此循环到倒数第二个数和最后一个数比较为止。 图示 ?...一是建堆渗透函数,二是反复调用渗透函数实现排序函数。 图示 建堆 ? 交换,从堆踢出最大数 ?...有关堆排序知识,可以参照另一篇帖子:https://www.jianshu.com/p/541d166ce6c2 3、交换排序 3.1 冒泡排序 基本思想 在要排序一组数,对当前还未排好序范围内全部数...若文件初状为正序,则一趟起泡就可完成排序,排序码比较次数为n-1,且没有记录移动,时间复杂度是O(n) 若文件初态为逆序,则需要n-1趟起泡,每趟进行n-i次排序码比较,且每次比较都移动三次,比较和移动次数均达到最大

    92970
    领券