nas做网站服务器,旅游网站首页图片,南通网站建设果尔,大型购物网站设计交换排序是基于“比较”和“交换”两种操作来实现的排序方法 。
由于选择“比较”的基准元素不同#xff0c;可将交换排序分为以下两种#xff1a;
冒泡排序快速排序
一、冒泡排序
1.冒泡排序基本思想
因为其实现与气泡从水中往上冒的过程类似而得名。
每一趟的…交换排序是基于“比较”和“交换”两种操作来实现的排序方法 。
由于选择“比较”的基准元素不同可将交换排序分为以下两种
冒泡排序快速排序
一、冒泡排序
1.冒泡排序基本思想
因为其实现与气泡从水中往上冒的过程类似而得名。
每一趟的过程都是相邻两个元素比较若为逆序则交换两个元素使关键字较小的元素如气泡一般逐渐往上“漂移”直至最后冒出“水面”。直到某一趟排序过程中没有交换发生说明序列已完全有序排序完成。
2.算法步骤
假设待排序的n个数据元素存放在数组a中
1首先将第一个元素与第二个元素进行比较若为逆序a[0]a[1]则将两个元素交换然后比较第二个元素和第三个元素。依次类推直到第n-1个元素完成比较为止。上述过程称为第一次冒泡排序过程其结果使得最大的记录被放在了最后一个记录的位置上。
2然后进行第二次冒泡排序过程对前n-1个记录进行同样的操作将次大的记录放在第n-1个记录的位置上。
3依此类推直到某一次冒泡排序过程不再有交换发生算法结束。
3.冒泡排序算法示例
例设待排元素序列为{56,25,70,99,82,10,15,56}请给出冒泡排序法进行排序的过程。 4.算法代码
def bubble_sort2(self):data_len len(self.data)for i in range(data_len-1, 0, -1): # 获得i号位置的正确值flag Truefor j in range(0, i):if self.data[j1].key self.data[j].key: self.data[j], self.data[j 1] self.data[j 1], self.data[j] flag Falseif flag:breakflag的作用
冒泡算法的每一轮都是相邻元素a[0]与a[1], a[1]与a[2], ……比较若为逆序则交换只要某一轮发生了元素交换则flagFalse说明此时整个数组还是无序状态需要进行下一轮的相邻元素比较与交换若某一轮相邻元素比较下来没有交换发生则flagTrue说明此时整个序列已经有序了以后轮次的比较就不再需要了最好情况下序列本身有序则只需进行一轮比较无交换
5.算法分析
1空间复杂度在进行元素交换时冒泡排序需要一个辅助空间临时存放元素其空间复杂度为O(1)。
2时间复杂度最好的情况下序列本身是有序的。此时只需要一趟遍历进行n-1次相邻元素比较无需交换操作。 最坏的情况下初始序列为逆序此时需要n-1趟遍历第i趟遍历需要比较n-i次总共比较n(n-1)/2次。每次比较都需要移动因为每次移动都要通过辅助空间来进行故每次移动次数都为3总共移动次数3n(n-1)/2。所以综合考虑冒泡排序算法的时间复杂度为O(n2)。
3其他方面冒泡排序也可用于链式存储结构的序列排序如果初始序列无序性强数据元素多则移动次数较多此时不宜采用冒泡排序。
由于冒泡排序是顺次移动元素所以不会破坏数值相同元素的初始次序是一种稳定的排序方法。
二、快速排序
1.快速排序划分交换排序算法思想
1从数列中挑出一个元素称为“基准”。
2重新排序数列所有比基准值小的元素摆放在基准前面所有大于或者等于基准值的元素摆在基准的后面这个称为划分操作。在这个划分结束之后该基准就处于数列的中间位置。 3递归地把小于基准值元素的子数列和大于基准值元素的子数列排序进行上述划分过程。
快速排序基本思想
将序列中的某一记录设置为枢轴pivot一趟排序将枢轴交换到其最终位置所有小于枢轴的记录交换到枢轴的左边所有大于等于枢轴的记录交换到枢轴的右边这个过程称为一趟划分partition。接下来对左子序列和右子序列分别快速排序直至被排序子序列长度小于等于1为止。分而治之思想对整个序列的排序分解为对左子序列和右子序列的排序是一种递归排序。 一趟划分方法
对数组data中low~high范围内的元素进行一趟划分。一般选取data[low]作为枢轴pivot。在划分过程中始终保持下图所示的不变式即pivot之后为小于pivot的区域A紧接着是大于等于pivot的区域B后面是i号位置开始的待处理区域。初始时ilow1A和B区域的长度都为0。 为了维持不变式如果i号记录大于等于pivot则i加1即B区域长度增加1否则则将i号记录与B区域的最左记录进行交换。为了方便交换记录A、B区域的分界点last_small设last_small为A区域的最右端位置。交换时将last_small加1i号记录与last_small位置记录交换接着i加1。 当i超出high的范围说明除了pivot之外的所有记录都已归入A区域或B区域如图所示此时只需将pivot与last_small所指记录进行交换即可达成一趟划分的目标。 2.快速排序算法举例
例设待排数据元素序列为{2667679643821054}请给出快速排序法进行排序的过程。 3.快速排序代码 一趟划分交换的代码
def partition(self, low, high):last_small lowfor i in range(low 1, high 1):if self.data[i] self.data[low]:last_small last_small 1self.swap(last_small, i)self.swap(low, last_small)return last_smalldef swap(self, i, j): # 将i号和j号位置的记录交换self.data[i], self.data[j] self.data[j], self.data[i]
递归算法和接口方法
def recursive_quickSort(self, low, high):if low high:self.swap(low,(lowhigh)//2)pivot_position self.partition(low, high)self.recursive_quickSort(low, pivot_position - 1)self.recursive_quickSort(pivot_position 1, high)def quick_sort(self):self.recursive_quickSort(0, len(self.data) - 1)4.算法分析
1空间复杂度快速排序是递归程序每层递归调用过程需要一个栈来存放指针与参数而快速排序最大递归调用的次数与递归树的深度一致因此最好的情况下空间复杂度为O(log2n)最坏的情况下为O(n)。
2时间复杂度平均情况O(n log2n) 最坏情况即每次划分过程产生的两个区间分别包含n-1个元素和1个元素的情况比如待排序列已经有序的时候其递归树为单分支树这样必须进行n-1趟才能将所有元素定位快速排序已经蜕化为简单排序的水平其时间复杂度为O(n2)。 当对较大量数据构成的递增序列进行快速排序且采用首元素为枢轴可能发生递归调用栈溢出的错误。 为避免出现极端情况可在进行一次划分之前进行“预处理”即先对data[low].key、data[high].key和data[(lowhigh)//2].key进行相互比较然后取关键字值“三者之中”的记录为枢轴记录。 当基准元素选择得当的时候每次都选择中间元素为基准每一趟排序都能将元素均匀地分割成两个长度相等的子序列达到快速排序的最好情况此时分割次数等于完全二叉树的深度log2n另外无论序列如何划分全部比较次数都接近于n-1次所以时间复杂度为O(nlog2n)。一般情况下基准元素是随机分布的序列分割次数接近于log2n所以快速排序的平均时间复杂度为O(nlog2n)。
3其他方面在所有同数量级的排序方法中依平均时间复杂度尤其是初始序列无序性强数据元素比较多的时候快速排序是目前性能最好的内部排序方法。在排序过程中需要序列的上下边界所以不适合链式存储结构排序。由于数据元素移动的时候是不按顺序的所以快速排序是一种不稳定的排序方法。
