一、什么是交换排序？
1.交换排序的基本思想是两两比较待排序记录的关键字，若两个记录的次序相反则交换这两个记录，直到没有反序的记录为止。
2.交换排序主要方法：
冒泡排序
快速排序
二、冒泡排序
1、什么是冒泡排序？
冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行，直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
将待排序的数组看成从上到下的存放，把关键字较小的记录看成较轻的，关键字较大的记录看成较重的。
较小关键字值的记录，好像水中的气泡一样，向上浮；
较大关键字值的记录，好像水中的石块一样，向下沉；
当所有的气泡都浮到了相应的位置，并且所有的石块都沉到了水中，排序就结束了。
2、冒泡排序算法的原理分析？
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
3）算法分析
从第一个记录开始，依次对无序区中相邻记录进行关键字比较，如果大在上，小在下，则交换，第一趟扫描下来表中最大的沉在最下面
然后再对前n-1个记录进行冒泡排序，直到排序成功为止。
一般，第i趟扫描时，r[0]到r[n-i]和r[i+1]到r[n-1]分别为当前的无序区和有序区。
待排序的序列：{52, 39, 67, 95, 70, 8, 25, 52}
4、算法代码实现
代码
//【算法】 冒泡排序算法 public void bubbleSort() { // System.out.println("冒泡排序"); RecordNode temp; // 辅助结点 boolean flag = true; // 是否交换的标记 for (int i = 1; i < this.curlen && flag; i++) { // 有交换时再进行下一趟，最多n-1趟 flag = false; // 假定元素未交换 for (int j = 0; j < this.curlen - i; j++) { // 一次比较、交换 if (r[j].key.compareTo(r[j + 1].key) > 0) { // 逆序时，交换 temp = r[j]; r[j] = r[j + 1]; r[j + 1] = temp; flag = true; //如果发生交换，记录 } } System.out.print("第" + i + "趟: "); display(); } }
- 测试
public class TestSeqList4_bubble { public static void main(String[] args) throws Exception { int[] arr = {52,39,67,95,70,8,25,52}; SeqList seqList = new SeqList(arr.length); for (int i = 0; i < arr.length; i++) { seqList.insert(i, new RecordNode(arr[i])); } // 希尔排序算法 seqList.bubbleSort(); } } //冒泡排序 //第1趟: 39 52 67 70 8 25 52 95 //第2趟: 39 52 67 8 25 52 70 95 //第3趟: 39 52 8 25 52 67 70 95 //第4趟: 39 8 25 52 52 67 70 95 //第5趟: 8 25 39 52 52 67 70 95 //第6趟: 8 25 39 52 52 67 70 95
5）性能分析
时间复杂度：O(n2)
空间复杂度：仅需要一个记录的辅助空间，O(1)
是稳定的排序方法
6）练习
练习1：使用冒泡排序，写出每一趟的排序结果。
序列：16, 15, 50, 53, 64, 7
练习2：使用冒泡排序，写出每一趟的排序结果
序列：9 , 20 , 13 , 20 , 12
三、快速排序
1、什么是快速排序？
快速排序（Quicksort）是对冒泡排序算法的一种改进。
快速排序：Quick Sort
通过一趟排序将要排序的记录分割成独立的两个部分，其中一部分的所有记录的关键字值都比另外一部分的所有记录关键字值小。
然后再按此方法对这两部分记录分别进行快速排序。
整个排序过程可以递归进行，以此达到整个记录序列变成有序。
2、快速排序步骤分析
快速排序算法通过多次比较和交换来实现排序，其排序流程如下：
(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。 将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。
(2)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
(3)重复上述过程，可以看出，这是一个递归操作。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
3、算法分析
假设待排序的记录序列为：{ r[row] , r[row+1] , ... , r[high] }
首先在该序列中任意选取一条记录（该记录称为支点，通常选r[row]作为支点）
然后将所有关键字值比支点小的记录都放到它的前面
所有关键字值比支点大的记录都放到它的后面
由此可以将该支点记录最后所落的位置i作为分界线，
将记录序列{ r[row] , r[row+1] , ... , r[i-1], r[i], r[i+1], r[i+2], ... , r[high] }分隔成两个子序列 { r[row] , r[row+1] , ... , r[i-1]} 和 {r[i+1], r[i+2], ... , r[high] }。
这个过程称为一趟快速排序。通过一趟排序，支点记录就落在了最终排序结果的位置上。
核心思路：
变量i 作用：从左往右寻找比支点大的值，从而交换到后面的位置（上一次j的位置）。
变量 j 作用：从右往左寻找比支点小的值，从而交换到前面的位置（上一次i的位置）。
4）算法代码实现：一趟快速排序
代码
//【算法】一趟快速排序 //交换排序表r[i..j]的记录，使支点记录到位，并返回其所在位置 //此时，在支点之前(后)的记录关键字均不大于(小于)它 public int Partition(int i, int j) { RecordNode pivot = r[i]; //第一个记录作为支点记录 System.out.println(i + ".." + j + ", pivot=" + pivot.key + " "); System.out.print("初始值： "); int c = 0; display(); while (i < j) { //从表的两端交替地向中间扫描 // 1.1 从后到前，寻找第一个比支点小的元素 while (i < j && pivot.key.compareTo(r[j].key) <= 0) { j--; } // 1.2 将后面较小的元素，移到前面去 if (i < j) { r[i] = r[j]; //将比支点记录关键字小的记录向前移动 System.out.print("第"+(++c)+"次交换后："); display(); i++; } // 2.1 从前到后，选择第一恶比支点大的元素 while (i < j && pivot.key.compareTo(r[i].key) > 0) { i++; } // 2.2 将前面较大的元素，移到后面去 if (i < j) { r[j] = r[i]; //将比支点记录关键字大的记录向后移动 System.out.print("第"+(++c)+"次交换后："); display(); j--; } } r[i] = pivot; //支点记录到位 System.out.print("一趟完成： "); display(); return i; //返回支点位置 }
- 测试
public class TestSeqList5_part { public static void main(String[] args) throws Exception { int[] arr = {52,39,67,95,70,8,25,52}; SeqList seqList = new SeqList(arr.length); for (int i = 0; i < arr.length; i++) { seqList.insert(i, new RecordNode(arr[i])); } // 一趟快速排序 seqList.Partition(0, arr.length - 1); } } //一趟快速排序 //0..7, pivot=52 //初始值： 52 39 67 95 70 8 25 52 //第1次交换后： 25 39 67 95 70 8 25 52 //第2次交换后： 25 39 67 95 70 8 67 52 //第3次交换后： 25 39 8 95 70 8 67 52 //第4次交换后： 25 39 8 95 70 95 67 52 //一趟完成： 25 39 8 52 70 95 67 52
5）算法代码实现：完整快排
代码
//【算法】 递归形式的快速排序算法 //对子表r[low..high]快速排序 public void qSort(int low, int high) { if (low < high) { int pivotloc = Partition(low, high); // 一趟排序，将排序表分为两部分 qSort(low, pivotloc - 1); // 低子表递归排序 qSort(pivotloc + 1, high); // 高子表递归排序 } } //【算法完整快排】顺序表快速排序算法 public void quickSort() { qSort(0, this.curlen - 1); }
- 测试
public class TestSeqList6_quick { public static void main(String[] args) throws Exception { int[] arr = {52,39,67,95,70,8,25,52}; SeqList seqList = new SeqList(arr.length); System.out.print("数组序列号："); for (int i = 0; i < arr.length; i++) { System.out.print(" " + i); seqList.insert(i, new RecordNode(arr[i])); } System.out.println(); // 快速排序 seqList.quickSort(); } } //快速排序 //数组序列号： 0 1 2 3 4 5 6 7 //0..7, pivot=52 //初始值： 52 39 67 95 70 8 25 52 //第1次交换后： 25 39 67 95 70 8 25 52 //第2次交换后： 25 39 67 95 70 8 67 52 //第3次交换后： 25 39 8 95 70 8 67 52 //第4次交换后： 25 39 8 95 70 95 67 52 //一趟完成： 25 39 8 52 70 95 67 52 //0..2, pivot=25 //初始值： 25 39 8 52 70 95 67 52 //第1次交换后： 8 39 8 52 70 95 67 52 //第2次交换后： 8 39 39 52 70 95 67 52 //一趟完成： 8 25 39 52 70 95 67 52 //4..7, pivot=70 //初始值： 8 25 39 52 70 95 67 52 //第1次交换后： 8 25 39 52 52 95 67 52 //第2次交换后： 8 25 39 52 52 95 67 95 //第3次交换后： 8 25 39 52 52 67 67 95 //一趟完成： 8 25 39 52 52 67 70 95 //4..5, pivot=52 //初始值： 8 25 39 52 52 67 70 95 //一趟完成： 8 25 39 52 52 67 70 95
6）性能分析
时间复杂度：O( nlog2n )
空间复杂度：O( log2n )
是不稳定排序
7）快速排序练习
练习1：使用快速排序，写出每一趟的排序结果。
序列：16, 15, 50, 53, 64, 7
练习2：使用快速排序，写出每一趟的排序结果
序列：9 , 20 , 13 , 20 , 12
