查找与排序-交换排序

交换排序是基于“比较”和“交换”两种操作来实现的排序方法 。

由于选择“比较”的基准元素不同，可将交换排序分为以下两种：

• 冒泡排序
• 快速排序

一、冒泡排序 

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[j+1].key <= self.data[j].key:             self.data[j], self.data[j + 1] = self.data[j + 1], self.data[j]                flag = Falseif flag:break

flag的作用：

• 冒泡算法的每一轮都是相邻元素a[0]与a[1], a[1]与a[2], ……比较，若为逆序则交换
• 只要某一轮发生了元素交换，则flag=False，说明此时整个数组还是无序状态，需要进行下一轮的相邻元素比较与交换
• 若某一轮相邻元素比较下来没有交换发生，则flag=True，说明此时整个序列已经有序了，以后轮次的比较就不再需要了
• 最好情况下，序列本身有序，则只需进行一轮比较，无交换

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号位置开始的待处理区域。初始时，i=low+1，A和B区域的长度都为0。 
•  为了维持不变式，如果i号记录大于等于pivot，则i加1，即B区域长度增加1；否则，则将i号记录与B区域的最左记录进行交换。
• 为了方便交换，记录A、B区域的分界点last_small，设last_small为A区域的最右端位置。交换时，将last_small加1，i号记录与last_small位置记录交换，接着i加1。

 

当i超出high的范围，说明除了pivot之外的所有记录都已归入A区域或B区域，如图所示，此时，只需将pivot与last_small所指记录进行交换，即可达成一趟划分的目标。

 2.快速排序算法举例

例：设待排数据元素序列为{26，67，67，9，6，43，82，10，54}，请给出快速排序法进行排序的过程。

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_small

def 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,(low+high)//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[(low+high)//2].key进行相互比较，然后取关键字值“三者之中”的记录为枢轴记录。 

    当基准元素选择得当的时候（每次都选择中间元素为基准），每一趟排序都能将元素均匀地分割成两个长度相等的子序列，达到快速排序的最好情况，此时分割次数等于完全二叉树的深度log2n，另外，无论序列如何划分，全部比较次数都接近于n-1次，所以时间复杂度为O(nlog2n)。一般情况下，基准元素是随机分布的，序列分割次数接近于log2n，所以快速排序的平均时间复杂度为O(nlog2n)。

（3）其他方面：在所有同数量级的排序方法中，依平均时间复杂度，尤其是初始序列无序性强，数据元素比较多的时候，快速排序是目前性能最好的内部排序方法。在排序过程中需要序列的上下边界，所以不适合链式存储结构排序。由于数据元素移动的时候是不按顺序的，所以快速排序是一种不稳定的排序方法。