什么是交换排序呢？
两两比较待排序的关键字，并交换不满足次序要求的那对数，直到整个表都满足次序要求为止。
交换排序具体分为冒泡排序和快速排序。下面对两种排序进行讲解。
一、基本思想
冒泡排序很简单，貌似只要会一点排序算法的，那他会的肯定是冒泡。思想很简单，就是从一端第一个开始，多次进行(比较->交换)，最终最大(小)的元素会浮在另一端，重复此操作，直到全部有序。看下面代码，我在代码中有具体的讲解。
二、代码实现
private static int[] bubbleSort(int[] arr) { // 总体思路：从左到右，相邻的两个进行比较，如果第一个比第二个大，就交换位置 // 这样经过一轮排序，最大的会在数组的末尾，再重复操作排剩下的，第二大的在末尾倒数第二个 for(int i=0;i<arr.length-1;i++) // 外循环:需要确定length-1个位置 for(int j=0;j<arr.length-1-i;j++) { // 内循环:此时已经确定了i个位置，这些不参与比较，剩下只需比较length-1次 if(arr[j]>arr[j+1]) { int temp = arr[j+1]; arr[j+1] = arr[j]; arr[j] = temp; } } return arr; }三、性能分析
1.时间效率:若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数(N-1)和记录移动次数(0)均达到最小值,所以，冒泡排序最好时间复杂度为O(N)。若初始文件是反序的，需要进行 N -1 趟排序。每趟排序要进行 N - i 次关键字的比较(1 ≤ i ≤ N - 1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较(N(N-1)/2 )和移动次数(3N(N-1)/2)均达到最大值,所以，冒泡排序的最坏时间复杂度为O(N2)。因此，冒泡排序的平均时间复杂度为O(N2)。总结起来，其实就是一句话：当数据越接近正序时，冒泡排序性能越好。 2.空间效率:在整个算法中，需要一个用于交换记录的辅助空间，所以空间复杂度为O(1)。
3.稳定性：冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
一、基本思想
前面介绍的起泡排序总是在两两相邻的记录之间做比较和交换，比较和交换的次数较多,而记录的上移和下移速度却比较慢。快速排序(QuickSort)又被称为分区排序，它的基本思想是:在待排序文件中任选一个记录(称为基准记录)，以它的排序码为基准值,将排序码比它小的记录都放到它的前面,，排序码比它大的记录都放到它的后面。至此,该基准记录就找到了排序的最终位置，同时将文件划分成前、后两个区。在两个区上用同样的方法继续划分，直到每个区中最多只有一个记录，排序完成。在快速排序过程中，比较和交换是从数组的两端向中间进行的,使得排序码较小或较大的记录一次就能够交换到数组的前面或后面，记录的每次移动距离都较远，因而使得总的比较和移动次数较小。快速排序是对起泡排序的一种改进，它是目前所有的内部排序方法中速度最快的一种。 通俗的讲法，先从数组中任意取出一个数作为基准数,一般我们都取第一个，把它另存为key,然后第一个位置的数就不用管了，可以把他想成已经被挖走了，留下了一个坑。此时把key假装是将来排序完成后的最中间的数，那么接下来，我就想让比key小的全在它的左边，比key大的全在它的右边。那么如何完成呢？我需要两个左右哨兵i、j负责与key的比较，i负责遍历左部分数列，j负责遍历右部分数列。也就是让i遍历找出比key大的然后给它移到右边去，让j遍历找出比key小的然后给它移到左边去。但是你移到另一边放哪个位置呀，前面我有说第一个数被挖走了，所以这里可以通过元素填坑的方式进行调整。此时此刻，坑在第一个位置，所以我可以让右边移过来的数填到这里，所以这意味着先从最右边开始遍历，这里我选第一个元素为key,坑在第一个，所以应该从最右边开始遍历，如果j找到一个，就和坑进行交换，这时坑就到右边了，接下来就让i从最左边开始遍历，如果i找到比key大的，就和坑进行交换，这时坑就又跑到左边了，就这样i、j每个人轮流来一次。还有一点注意，当哨兵找到符合要求的元素后，哨兵应该停留在此处，等另一个哨兵完成后，你应该从此处开始继续向中间寻找(而不是又从头开始)，那么什么时候结束呢？ 在上初中时应该都做过这样一个问题，两辆车相向而行，问多长时间能够相遇，对，他们两个哨兵你走一步我走一步相向而行，终有一天相遇，相遇了说明了什么，说明i哨兵已经完成了从最左边到相遇点的遍历，j哨兵已经完成了从最右边到相遇点的遍历，也就是所有元素全都被遍历了，而且都经过了比较，已经符合了我的要求(本应该在key左边的都已经在左边了，本应该在key右边的都已经在右边了)。那么在之前我曾经假设过key是在最中间的元素，可是事实并不是如此，我经过亲自实践比较确定了key的位置，就是此时此刻相遇的点，也就是那个坑的位置。 我曾经在思考这个坑到底有什么作用？ 我总感觉里面蕴含着一种数学或哲学思想。我们先思考下最开始这个坑的选择，我选择的是第一个位置作为坑，当然你也可以选择别的位置的坑，不管我们选择哪个位置作为坑，都要假设他将是最中间位置，但是假设归假设，你还要事实验证下吧。我们看看其他位置的元素是不是大于它的在它右边，小于它的在它左边。因为我选的是第一个元素即最左边的这个元素，它左边已经没有元素了所以我只能检测右边的元素是否都全部大于它，如果有不大于key的，那么就意味着你不应该在我的右边，你应该在我左边，那么如何实现在我左边呢，就是和我进行交换。也就是交换可以改变你在我左右的位置，而且不会需要新的空间来过渡。但是你交换完后，下一次又如何检测呢？因为坑的位置一直在变，必须得找到不变的事物，现在有个办法，就是固定的从两头开始同时检测，说同时也不是同时，而是你检测一下我检测一下，这就需要i、j这两个哨兵了，这两个哨兵是不变的，他们分别在自己的领域寻找奸细(即不应该在我这边的把它交给另一方)。当两个哨兵从各自端点遍历时，比如，当i哨兵遍历到一个大于key的元素说明在它之前的元素都检验合格，因此让坑和这个元素交换，那么此时坑左边的所有元素应该全是小于key的元素；接下来让j哨兵遍历到一个小于key的元素，在此，说明之前的元素也都检验合格，这时坑又和这个不合格的交换。思考下此时两个哨兵的位置，哨兵们从当前位置到各自的端点是不是全都符合要求？答案肯定的，即{i检查合格的元素}{i还未检测到}{假设key的位置}{j未检测到}{j检查合格的元素}，在我思考中，坑是随便选的，坑地位置也是随便乱窜的，但其实它乱窜也是有规则的，他只在[i,j]区间内乱窜，然而这个区间是不断缩小的，终有一天它会固定下来。固定下来也就是key找到了自己的真实位置了！
以上所说的过程只是快速排序中的一趟排序，还要经历多趟才能够得到一个有序数列。它的每一趟排序都是确定某一个元素的位置，然后以这个元素为界限分为两部分，对他们进行同样的遍历。伴随着不断的元素确定位置，两部分内的元素越来越少，终有一天某一趟排序下来，这个元素分为的两部分中只有单个元素了，那就不再需要遍历了，这个过程可以看做是一个递归。
二、代码实现
首先说明的一点是，快速排序算法这个算法我感觉让人理解起来比较难，但是代码写起来却比较简单；而之前我写的堆排序，人理解起来比较容易，但是代码却不好写。
public class Demo { public static void main(String args[]) { int[] arr = {49,14,38,74,96,65,8,49,55,27}; quickSort(arr,0,arr.length-1); for(int a:arr) System.out.print(a+" "); } private static void quickSort(int[] a,int low,int high) { if(low<high){ int part = division(a,low,high); quickSort(a,low,part-1); quickSort(a,part+1,high); } } private static int division(int[] a,int low,int high) { int key = a[low]; boolean flag = true; while(low<high) { if(flag) { if(a[high]<key) { a[low] = a[high]; flag = false; } else high--; } else { if(a[low]>key) { a[high] = a[low]; flag = true; } else low++; } } a[low] = key; return low; } }三、性能分析
1.时间效率:在快速排序过程中,记录的比较次数大于记录的移动次数,因为只有在后面区间发现了小于基准记录排序码的记录或在前面区间发现大于基淮记录排序码的记录时才会移动记录。所以,只讨论快速排序的比较次数就可以分析其时间复杂度。
最好的情况下，快速排序过程对应的二叉树是一棵类似完全二叉树。因此，在最好的情况下,对n个记录进行排序的过程中需要划分的层数为,而每一层划分中,记录之间的比较次数为O(n);所以快速排序的最好时间复杂度为。 在最坏的情况下,n个记录的快速排序过程对应的二叉树是一棵单分支树。若初始记录序列是按排序码有序的，则每一次划分只得到一个非空子区间，另一个子区间为空，就是这种情况。此时,需要做n-1层的划分,每一层划分的比较次数约为O(n),所以最坏时间复杂度为,可见,快速排序反而蜕化为起泡排序。为避免这样的情况发生,通常以三者取中法来选取基准记录，即取排序区间两端及中间位置的三个记录的排序码居中的为基准记录。 理论上已经证明,快速排序的平均时间复杂度仍为,当n较大时,通常快速排序被认为在同数量级的排序方法中平均性能是最好的。 2.空间效率:快速排序是递归过程,每层递归调用时的指针和参数均要用栈来存放涕归调用的深度与对应的二叉树的深度-致。因而,最好的空间复杂度为 ,最切的空间复杂度为O(n),平均空间复杂度也为。
3.稳定性：快速排序是一个不稳定的排序方法。
