排序 - 交换排序(Swap Sort)详解

2021年3月26日

数据结构
常见排序算法

交换排序
Swap Sort
冒泡排序
Bubble Sort
快速排序
Quick Sort

大约 8 分钟

排序 - 交换排序(Swap Sort)详解

交换类排序主要是通过两两比较待排元素的关键字，若发现与排序要求相逆，则“交换”之。在这类排序方法中最常见的是起泡排序（冒泡排序）和快速排序，其中快速排序是一种在实际应用中具有很好表现的算法。

冒泡排序

冒泡排序（Bubble Sort） 即比较相邻两元素大小，如果反序，则交换，若按照升序排序，则每次应将数据元素序列中最大元素交换到最后位置，即两两相比较，大的元素向后移动，直至将最大的交换到最后的位置，就像水中气泡一样冒出去，得名冒泡排序。

冒泡算法

起泡排序又称为冒泡排序，起泡排序的思想：

首先，将n个元素中的第一个和第二个进行比较，如果两个元素的位置为逆序，则交换两个元素的位置；进而比较第二个和第三个元素关键字，如此类推，直到比较第n-1个元素和第n个元素为止；
上述过程描述了起泡排序的第一趟排序过程，在第一趟排序过程中，我们将关键字最大的元素通过交换操作放到了具有n个元素的序列的最一个位置上。
然后进行第二趟排序，在第二趟排序过程中对元素序列的前n-1个元素进行相同操作，其结果是将关键字次大的元素通过交换放到第n-1个位置上。
一般来说，第i趟排序是对元素序列的前n-i+1个元素进行排序，使得前n-i+1个元素中关键字最大的元素被放置到第n-i+1个位置上。排序共进行n-1趟，即可使得元素序列按关键字有序。

代码实现

//冒泡排序
public void main(String[] args){
	int[] arr = new int[]{-12,3,2,34,5,8,1};  
	//冒泡排序  
    for(int i = 0;i < arr.length-1;i++){  
        for(int j = 0;j <arr.length-1-i;j++){  
        if(arr[j] >arr[j+1]){  
            int temp = arr[j];  
            arr[j] = arr[j+1];  
            arr[j+1] = temp;  
        }}  
    }
}

冒泡分析

冒泡排序我们分析他的两种情况：

最好情况：数据序列排序，那么只进行一次冒泡，比较n此，时间复杂度为O(n).
最坏情况：数据反序排列或者随机排列，那么数据就会进行n-1此冒泡，因为我们最后一趟冒泡n已经排好，所以我们要进行n-1此冒泡，大家可以自行画图理解。比较次数和移动次数都是（n-1）+(n-2) +.....+2+1；最后可以得到其时间复杂度为O(n2)。那么我们的冒泡排序即在越接近有序的情况下，他的算法的时间效率就越高，反之，如果我的数据有成千上万个，且刚好反序，那么我的效率就十分的低了。因此，冒泡排序虽然稳定，但是也难免会造成效率低下。那么接下来我们就可以学习另一种高级一点的排序方式，快速排序。

空间效率： 仅使用一个辅存单元O(1)。

时间效率： 假设待排序的元素个数为 n，则总共要进行n-1趟排序，对j个元素的子序列进行一趟起泡排序需要进行 j-1 次关键字比较。由此，起泡排序的总比较次数为:

因此，起泡排序的时间复杂度为Ο(n^2)。

快速排序

快速排序（Quick Sort） 是将分治法运用到排序问题中的一个典型例子，快速排序的基本思想是：

通过一个枢轴（pivot）元素将n个元素的序列分为左、右两个子序列Ll和Lr，其中子序列Ll中的元素均比枢轴元素小，而子序列Lr中的元素均比枢轴元素大，
然后对左、右子序列分别进行快速排序，在将左、右子序列排好序后，则整个序列有序，而对左右子序列的排序过程直到子序列中只包含一个元素时结束，此时左、右子序列由于只包含一个元素则自然有序。

快排算法

用分治法的三个步骤来描述快速排序的过程如下：

划分步骤：通过枢轴元素 x 将序列一分为二，且左子序列的元素均小于x，右子序列的元素均大于x；
治理步骤：递归的对左、右子序列排序；
组合步骤：无

从上面快速排序算法的描述中我们看到，快速排序算法的实现依赖于按照枢轴元素x对待排序序列进行划分的过程。

对待排序序列进行划分的做法是：使用两个指针low和high分别指向待划分序列r的范围，取low所指元素为枢轴，即 pivot = r[low]。划分首先从 high 所指位置的元素起向前逐一搜索到第一个比pivot小的元素，并将其设置到low所指的位置；然后从low所指位置的元素起向后逐一搜索到第一个比pivot大的元素，并将其设置到high所指的位置；不断重复上述两步直到low = high为止，最后将pivot设置到low与high共同指向的位置。使用上述划分方法即可将待排序序列按枢轴元素 pivot 分成两个子序列，当然 pivot 的选择不一定必须是 r[low]，而可以是 r[low..high]之间的任何数据元素。

代码实现

public void main(String[] args){
	int [] a = {19,2,3,90,67,33,-7,24,3,56,34,5};
	quickSort(a,0,a.length-1);
}
//快速排序
private void quickSort(int[] a, int low, int high) {
	if(low<high){
		int middle = getMiddle(a,low,high);
		quickSort(a, 0, middle-1);
		quickSort(a,middle+1,high);
	}
}
//获取中间下标
private int getMiddle(int[] a, int low, int high) {
	int temp = a[low];//基准元素
	while(low<high){
		while(low<high&&a[high]>=temp){
			high--;
		}
		a[low] = a[high];
		while(low<high&&a[low]<=temp){
			low++;
		}
		a[high] = a[low];
	}
	a[low] = temp;//插入到排序后正确的位置
	return low;
}

快排分析

快速排序算法因为关键字的比较和交换是跳跃进行的，因此，快速排序算法是不稳定的。当待排序序列元素较多且数据元素随机排列时，快速排序是相当快速的；当待排序序列元素较多且基准值选择不合适时，快速排序则较慢。

时间效率： 快速排序算法的运行时间依赖于划分是否平衡，即根据枢轴元素 pivot 将序列划分为两个子序列中的元素个数，而划分是否平衡又依赖于所使用的枢轴元素。下面我们在不同的情况下来分析快速排序的渐进时间复杂度。

快速排序的最坏情况是每次进行划分时，在所得到的两个子序列中有一个子序列为空。此时，算法的时间复杂度T(n) = Tp(n) + T(n-1)，其中Tp(n)是对具有n个元素的序列进行划分所需的时间，由以上划分算法的过程可以得到Tp(n) = Θ(n)。由此，T(n) =Θ(n) + T(n-1) =Θ(n2)。在快速排序过程中，如果总是选择r[low]作为枢轴元素，则在待排序序列本身已经有序或逆向有序时，快速排序的时间复杂度为Ο(n2)，而在有序时插入排序的时间复杂度为Ο(n)。

快速排序的最好情况是在每次划分时，都将序列一分为二，正好在序列中间将序列分成长度相等的两个子序列。此时，算法的时间复杂度T(n) = Tp(n) + 2T(n/2)，由于Tp(n) = Θ(n)，所以T(n) = 2T(n/2) +Θ(n)，由master method知道T(n) = Θ(n log n)。在平均情况下，快速排序的时间复杂度 T(n) = kn ㏑ n，其中 k 为某个常数，经验证明，在所有同数量级的排序方法中，快速排序的常数因子 k 是最小的。因此就平均时间而言，快速排序被认为是目前最好的一种内部排序方法。

快速排序的平均性能最好，但是，若待排序序列初始时已按关键字有序或基本有序，则快速排序蜕化为起泡排序，其时间复杂度为Ο(n2)。为改进之，可以采取随机选择枢轴元素pivot的方法，具体做法是，在待划分的序列中随机选择一个元素然后与r[low]交换，再将r[low]作为枢轴元素，作如此改进之后将极大改进快速排序在序列有序或基本有序时的性能，在待排序元素个数n较大时，其运行过程中出现最坏情况的可能性可以认为不存在。

空间效率： 虽然从时间上看快速排序的效率优于前述算法，然而从空间上看，在前面讨论的算法中都只需要一个辅助空间，而快速排序需要一个堆栈来实现递归。若每次划分都将序列均匀分割为长度相近的两个子序列，则堆栈的最大深度为 log n，但是，在最坏的情况下，堆栈的最大深度为n。