说来惭愧，昨天面试的时候遇到快速排序的笔试题没答上来。搞java的长期接触的是业务方面的东西，特别是web方向的java，久而久之在学校里面学的最基本的一些东西给忘记了。网上搜索了这两种算法，，基本都是当年书本的解释，个人不是很喜欢。现将自身强化后的解释描述出来，加强记忆，最近有面试的同志不妨看看。
1.冒泡排序
书本上的基本理念是左边元素跟右侧元素一个个对比，有更小的就交换。
我将此分解为：
a.将数组的最小元素放在左边；
b.对右边做递归；
这个比较简单，实现a的代码：
// a.将数组的最小元素放在左边public static void bubbleBasic(int[] list) {// 基本前提if(list != null && list.length > 1) {// 从第二个元素开始对比for(int i=1;i<list.length;i++) {// 发现更小的就替换if(list[0] > list[i]) {int tmp = list[0];list[0] = list[i];list[i] = tmp;}}}}
a+b的代码：
// a+b.完整的冒泡排序public static void bubbleSort(int[]list, int begin) {if(list != null && (list.length – begin) > 1) {for(int i=begin+1;i<list.length;i++) {if(list[begin] > list[i]) {int tmp = list[begin];list[begin] = list[i];list[i] = tmp;}}bubbleSort(list, begin +1);}}
当然有更简单的不用递归的方式的书本代码：
// 书本的冒泡排序public static void bubbleBook(int[] list) {if(list != null && list.length > 1) {for(int i = 0 ; i < list.length-1 ; i++){for(int j = i+1 ; j < list.length ; j++){if(list[i] > list[j]) {int tmp = list[i];list[i] = list[j];list[j] = tmp;}}}}}
2.快速排序
书本上的基本理念是高位低位交叉对比，把数组分成两部分，左边都小于某个元素A，右边都大于A。
个人感觉这个描述很晕，其实是包含两部分，1.交叉对比，2.左边都小右边都大。我屏蔽掉第1点，把A固定成第一个元素，将此问题分解为：
a.把数组第一个元素放在某个位置，使得左边都小于它，右边都大于它；
b.对左右做递归；
对于a，不限制实现方式，相信绝大部分人都能做到。其实嘛算法就是要理解思想，实现方式是很多的，当然我这里也是用交叉对比来实现，我比较喜欢叫左右压缩对比。
实现a的代码：
// a.把数组第一个元素放在某个位置，使得左边都小于它，右边都大于它public static void quickBasic(int[] list) {// 基本前提if(list != null && list.length > 1) {// 第一个元素当前位置int i_current = 0;// 得到左右边界int i_left = 0;int i_right = list.length -1;// 只要右边界还大于左边界，说明还有压缩空间while(i_left < i_right) {// 不断压缩右边界，直到没有压缩空间或者出现比第一个元素更小的元素while(i_current < i_right && list[i_current] < list[i_right]) {i_right–;}// 交换元素（即使没找到更小元素也交换，因为一直找不到的话i_right最终会等于i_current，这时候就是自身跟自身交换，就当冗余步骤好了）int tmp = list[i_current];list[i_current] = list[i_right];list[i_right] = tmp;// 第一个元素的位置已经改变i_current = i_right;//———-元素交换到右边后开始对左边压缩，跟上面的过程完全相反———-while(i_current > i_left && list[i_current] > list[i_left]) {i_left++;}tmp = list[i_current];list[i_current] = list[i_left];list[i_left] = tmp;i_current = i_left;//———–返回while重复上面过程———-}//———–程序运行到这里，已经没有压缩空间了，功能完成，这时候i_left = i_current = i_right}}
a+b的代码：
// a+b.完整的快速排序public static void quickSort(int[] arr, int leftIndex, int rightIndex){if(arr != null && leftIndex < rightIndex) {// 备份一下初始化的左右边界，递归时候用到int _leftIndex = leftIndex;int _rightIndex = rightIndex;int currentIndex = leftIndex;while(leftIndex < rightIndex) {while(currentIndex < rightIndex && arr[currentIndex] < arr[rightIndex]) {rightIndex–;}int tmp = arr[currentIndex];arr[currentIndex] = arr[rightIndex];arr[rightIndex] = tmp;currentIndex = rightIndex;while(leftIndex < currentIndex && arr[leftIndex] < arr[currentIndex]) {leftIndex++;}tmp = arr[currentIndex];arr[currentIndex] = arr[leftIndex];arr[leftIndex] = tmp;currentIndex = leftIndex;}// 左右开始递归quickSort(arr, _leftIndex, currentIndex-1);quickSort(arr, currentIndex+1, _rightIndex);}}
快速排序暂时没发现不用递归能实现的方法。
上述方法的测试实例：
public static void main(String[] args) {int[] list = new int[]{2,1,4,5,8,7,6,3,9,0};bubbleBasic(list);// 结果是0,2,4,5,8,7,6,3,9,1（打印方法就不写了）list = new int[]{2,1,4,5,8,7,6,3,9,0};bubbleSort(list, 0);// 结果是0,1,2,3,4,5,6,7,8,9list = new int[]{2,1,4,5,8,7,6,3,9,0};bubbleBook(list);// 结果是0,1,2,3,4,5,6,7,8,9list = new int[]{2,1,4,5,8,7,6,3,9,0};quickBasic(list);// 结果是0,1,2,5,8,7,6,3,9,4list = new int[]{2,1,4,5,8,7,6,3,9,0};quickSort(list, 0, list.length -1);// 结果是0,1,2,3,4,5,6,7,8,9}
与其临渊羡鱼，不如退而结网。
