交换排序主要有冒泡排序和快速排序
冒泡排序
对于一组包含n个数据的一组记录，最坏的情况下，冒泡排序需要进行n-1趟比较。
第1趟：依次比较0和1、1和2、2和3……n-2和n-1索引的元素，如果发现第一个数据大于后一个数据，交换它们。经过第1趟，最大的元素排到了最后。
第2趟：依次比较0和1、1和2、2和3……n-3和n-2索引的元素，如果发现第一个数据大于后一个数据，交换它们。经过第2趟，第2大的元素排到了倒数第2位。
……
第n-1趟：依次比较0和1元素，如果发现第一个数据大于后一个数据，交换它们。经过第n-1趟，第2小（第n-1大）的元素排到了第2位。
实际上，冒泡排序的每趟交换结束后，不仅能将当前最大值挤出最后面位置，还能部分理顺前面其他元素；一旦某趟没有交换发生，即可提前结束排序。
public class BubbleSort {
public static void bubbleSort(DataWrap[] data) {
System.out.println("开始排序");
int arrayLength = data.length;
for (int i = 0; i < arrayLength - 1; i++) {
boolean flag = false;
for (int j = 0; j < arrayLength - 1 - i; j++) {
//如果索引j处的元素大于j+1处的元素
if (data[j].compareTo(data[j + 1]) > 0) {
DataWrap tmp = data[j + 1];
data[j+1] = data[j];
data[j] = tmp;
flag=true;
}
}
System.out.println("第"+i+"趟:"+ Arrays.toString(data));
//如果某趟没有发生交换，表名已经处于有序状态
if (!flag) {
break;
}
}
}
public static void main(String[] args) {
DataWrap[] data = new DataWrap[]{
new DataWrap(9, ""),
new DataWrap(16, ""),
new DataWrap(21, "*"),
new DataWrap(23, ""),
new DataWrap(30, ""),
new DataWrap(49, ""),
new DataWrap(21, ""),
new DataWrap(30, "*")
};
System.out.println("排序前：" + Arrays.toString(data));
bubbleSort(data);
System.out.println("排序后：" + Arrays.toString(data));
}
}
总结
冒泡排序而言的时间效率是不确定的：
最好的情况下，初始数据序列已经处于有序状态，执行1趟冒泡即可，做n-1次比较，无需进行任何交换；
但在最坏的情况下，初始数据序列处于完全逆序，算法要执行n-1趟冒泡，第i趟（1< i<n）做了n-i次比较，执行n-i-1次对象交换。此时的比较总次数为n * (n-1)/2，记录移动总次数为n * (n-1) * 3/2。
冒泡排序算法空间效率很高，它只需要一个附加程序单元用于交换，其空间效率为O(1)。
冒泡排序是稳定的
快速排序
快速排序是一个速度非常快的交换排序方法，它的基本思路很简单：从待排的数据序列中任取一个数据（如第一个数据）作为分界值，所有比它小的数据元素一律放到左边，所有比它大的数据元素一律放到右边。经过这样一趟下来，该序列形成左右两个子序列，左边序列中数据元素的值都比分界值小，右边序列中数据元素的值都比分界值大。
接下来对左、右两个子序列进行递归，对两个子序列重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个，排序完成。
从上面算法分析可以看出，实现快速排序的关键在于第一趟要做的事情，如下所示。
（1）选出指定的分界值—这个容易完成。
（2）将所有比分界值小的数据元素放在左边。
（3）将所有比分界值大的数据元素放在右边。
现在的问题是：如何实现上面的2、3步骤？这个时候就要用到交换了，思路如下。
（1）定义一个i变量，i变量从左边第一个索引开始，找大于分界值的元素的索引，并用i来记录它。
（2）定义一个j变量，j变量从右边第一个索引开始，找小于分界值的元素的索引，并用j来记录它。
（3）如果i < j，交换i、j两个索引处的元素。
重复执行以上（1）、（2）、（3）步，直到i >= j，可以判断j左边的数据元素都小于分界值，j右边的数据元素都大于分界值，最后将分界值和j索引处的元素交换即可。
如下图
public class QuickSort {
/**
* 交换数组i,j位置的值
* @param data
* @param i
* @param j
*/
private static void swap(DataWrap[] data, int i, int j) {
DataWrap tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
public static void quickSort(DataWrap[] data){
subSort(data, 0, data.length - 1);
}
private static void subSort(DataWrap[] data, int start, int end) {
//需要快排的
if (start < end) {
//以第一个元素作为分界值
DataWrap base = data[start];
//i从左边开始搜索，搜索大于分界值的元素的索引
int i = start;
//j从右边搜索，搜索小于分界值的元素的索引
int j = end+1;
while (true) {
//找到大于分界值的元素的索引，或者i已经到了end处
while (i < end && data[++i].compareTo(base) <= 0){}
//找到小于分界值的元素的索引，或者j已经到达了start处
while (j > start && data[--j].compareTo(base) >= 0){}
if (i < j) {
swap(data, i, j);
}else{
break;
}
}
swap(data, start, j);
//递归左子序列
subSort(data, start, j - 1);
//递归右子序列
subSort(data, j + 1, end);
}
}
public static void main(String[] args) {
DataWrap[] data = new DataWrap[]{
new DataWrap(9, ""),
new DataWrap(16, ""),
new DataWrap(21, "*"),
new DataWrap(23, ""),
new DataWrap(-30, ""),
new DataWrap(-49, ""),
new DataWrap(21, ""),
new DataWrap(30, ""),
new DataWrap(13, "")
};
System.out.println("排序前：" + Arrays.toString(data));
quickSort(data);
System.out.println("排序后："+Arrays.toString(data));
}
}
总结
快速排序需要使用递归，而递归使用战，因此它的空间为效率为：O(log2n)
快速排序中包含跳跃式交换，因此是不稳定的排序算法
网友评论