交换排序主要包括冒泡排序与快速排序，下面是冒泡排序和其两种改进方法、快速排序以及其改进方法的代码：
package com.xqq.冒泡排序; /** * 冒泡排序是对相邻两个记录进行关键字比较和交换，这样每次交换后只能改变一对逆序记录 * 而快速排序则是从待排序记录的两端开始进行比较和交换，并逐渐向中间靠拢， * 有可能改变挤兑逆序记录，从而加快了排序速度 * 快速排序： 当序列基本有序或者逆序时， 每一趟基准只能将其他记录分成一部分，这样降低了时间效率 * @author xqq */ public class Sort<T> { // 原始的冒泡排序是 : 每一趟，将一个所需要的元素冒泡之最顶端--即最末尾（也可以根据要求来） // 最多组要(n - 1)趟冒泡排序就可以使得记录称为有序序列 @SuppressWarnings("unchecked") public void bubbleSort1(T[] arrays) { Comparable<? super T> temp; int cmp; for (int i = arrays.length - 1; i > 0; i--) { for (int j = 0; j <= i - 1; j++) { temp = (Comparable<? super T>) arrays[j]; cmp = temp.compareTo(arrays[j + 1]); if (cmp > 0) { swap(arrays, j, j + 1); } } } } private void swap(T[] arrays, int i, int j) { T temp = arrays[i]; arrays[i] = arrays[j]; arrays[j] = temp; } // 在冒泡排序过程中，一旦发现某一趟没有进行交换操作，就表明此时待排序的记录序列已经成为有序序列。 // 所以引入标志检测 在某一趟中是否发生了交换 @SuppressWarnings("unchecked") public void bubbleSort2(T[] arrays) { Comparable<? super T> temp; int cmp; boolean exchange; for (int i = arrays.length - 1; i > 0; i--) { exchange = false; for (int j = 0; j <= i - 1; j++) { temp = (Comparable<? super T>) arrays[j]; cmp = temp.compareTo(arrays[j + 1]); if (cmp > 0) { swap(arrays, j, j + 1); exchange = true; } } if (!exchange) break; } } // 如果同时记录第i趟冒泡排序中最后一次发生交换的位置m， // 就会发现从此位置以后的记录均为有序序列，那么无序区的范围可以缩小到0 - m @SuppressWarnings("unchecked") public void bubbleSort3(T[] arrays) { Comparable<? super T> temp; int cmp; boolean exchange; int last = arrays.length - 2; for (int i = arrays.length - 1; i > 0; i--) { exchange = false; int m = last; // 初始时将最后需要交换的位置设置为最后一个元素 // 这个判断条件不能直接用last，因为last在这一趟冒泡排序过程中有可能一直在变化 for (int j = 0; j <= m; j++) { temp = (Comparable<? super T>) arrays[j]; cmp = temp.compareTo(arrays[j + 1]); if (cmp > 0) { swap(arrays, j, j + 1); exchange = true; last = j; // 记录每次发生交换的位置 } } if (!exchange) break; } } // 快速排序： public void quickSort1(T[] arrays) { if (arrays == null || arrays.length <= 1) return; quicksort1(arrays, 0, arrays.length - 1); } // 快速排序优化，减少数组元素的交换次数 public void quickSort2(T[] arrays) { if (arrays == null || arrays.length <= 1) return; quicksort2(arrays, 0, arrays.length - 1); } private void quicksort1(T[] arrays, int first, int end) { int partition = partition1(arrays, first, end); if (first < partition - 1) quicksort1(arrays, first, partition - 1);// 对左侧区域递归进行快速排序 if (end > partition + 1) quicksort1(arrays, partition + 1, end); // 对右侧进行快速排序 } // 快速排序 找基准位置 @SuppressWarnings("unchecked") private int partition1(T[] arrays, int first, int end) { T temp = arrays[first]; Comparable<? super T> t = (Comparable<? super T>) temp; int i = first, j = end; while (i < j) { while (j > i && t.compareTo(arrays[j]) <= 0) j--; arrays[i] = arrays[j]; while (i < j && t.compareTo(arrays[i]) >= 0) i++; arrays[j] = arrays[i]; } arrays[i] = temp; return i; } // 快速排序优化 减少交换次数 @SuppressWarnings("unchecked") private int partition2(T[] arrays, int first, int end) { T temp = arrays[first]; Comparable<? super T> t = (Comparable<? super T>) temp; int i = first, j = end; while (i < j) { while (j > i && t.compareTo(arrays[j]) <= 0) j--; while (i < j && t.compareTo(arrays[i]) >= 0) i++; swap(arrays, i, j); } swap(arrays, first, i); return i; } private void quicksort2(T[] arrays, int first, int end) { // int partition = partition1(arrays, first, end); int partition = partition2(arrays, first, end); if (first < partition - 1) quicksort2(arrays, first, partition - 1);// 对左侧区域递归进行快速排序 if (end > partition + 1) quicksort2(arrays, partition + 1, end); // 对右侧进行快速排序 } } 测试代码： package com.xqq.冒泡排序; import java.util.Arrays; public class Main { public static void main(String[] args) { Integer [] arrays = {4, 5, 7, 3, 3, 2, 1}; Sort<Integer> sort = new Sort<Integer>(); // sort.bubbleSort1(arrays); // sort.bubbleSort2(arrays); // sort.bubbleSort3(arrays); // sort.quickSort1(arrays); sort.quickSort2(arrays); System.out.println(Arrays.asList(arrays).toString()); } }