小学生才玩儿冒泡，猛男都玩儿快排
在常见的排序算法中，快速排序在性能上有绝对的优势，家里有条件的建议都把原理搞懂；
老规矩，先看demo
public class QuickSort { public static int[] sort(int[] arr, int left, int right) { //left和right为数组边界的下标，如果left >= right，则直接返回，无需排序 if (left >= right) return arr; //定义两个游标i和j，我们将通过i和j确定出参照数的下标 //注意将i、j与left、right区分，i、j是游标，而left、right是扫描边界，边界是进入方法后确定不变的，而i和j会一直变化 int i = left, j = right, temp = arr[left]; //开始从两端往中间扫描，确认参照数下标，所有操作都是基于i<j while (i < j) { //先从右往左扫描 //如果j处的元素大于参照数，则j-1，继续往数组中部扫描 while (arr[j] >= temp && i < j) j--; //如果j处的元素小于参照数，则将j处的元素赋值给i处，这里的if判断其实可以不写，写出来只是为了方便大家理解 if (arr[j] < temp && i < j) arr[i] = arr[j]; //再从左往右扫描 //如果i处的元素小于参照数，则i+1，继续往数组中部扫描 while (arr[i] <= temp && i < j) i++; //如果i处的元素大于参照数，则将i处的元素赋值给j处，这里的if判断其实可以不写，写出来只是为了方便大家理解 if (arr[i] > temp && i < j) arr[j] = arr[i]; //记住我们扫描的目的===> 为了找出参照数在数组中正确的下标，这个下标左边的元素都比参照数小，右边的都比它大 //记住我们扫描的目的===> 为了找出参照数在数组中正确的下标，这个下标左边的元素都比参照数小，右边的都比它大 //记住我们扫描的目的===> 为了找出参照数在数组中正确的下标，这个下标左边的元素都比参照数小，右边的都比它大 } //这里也可以换成arr[j] = temp，因为经过扫描后，i==j arr[i] = temp; //这是快速排序的精髓所在，分治递归，将数组分成两半，前半部分是0到i-1 sort(arr, left, i - 1); //后半部分是i+1到数组长度-1 sort(arr, i + 1, right); return arr; } public static void main(String[] args) { //定义一个无序数组 int[] arr = {5, 12, 3, 18, 19, 55, 0, 28, -1, 33}; System.out.print("原数组："); for (int i : arr) { System.out.print(i + " "); } //left和right代表数组两端边界的下标 sort(arr, 0, arr.length - 1); System.out.print("\n排序后："); for (int i : arr) { System.out.print(i + " "); } } }
运行结果
原数组：5 12 3 18 19 55 0 28 -1 33 排序后：-1 0 3 5 12 18 19 28 33 55
原理：
给定一个数组arr
在数组中选择一个数字作为参照数，这个数字一般就是数组的第一个元素（最理想的参照数是排序好后的数组中的中位数，但我们不知道是谁，所以就直接用数组内第一个元素）
重点来了，然后定义两个游标 i 和 j ，因为我们要从数组两端往中间扫描，所以首次扫描时i等于left等于0，j等于right等于arr.length-1
分别从数组两端往中间扫描，一般先从右边开始，直到找到一个正确的参照数下标，什么样的下标才叫正确？把参照数放到这个下标后，参照数左边的数字都比参照数小，右边的数字都比参照数大
第一次扫描完成后，会进行递归扫描，递归扫描会把原数组以参照数隔开，切分成两个数组，这两个数组再进行上述操作，最终实现数组元素排序
我知道你哪儿不懂
一定要分清left、right和i、j的关系，left和right是确定数组边界，就是数组中left到right之间的元素才会进行排序，比如如果你输入的left=1，right=arr.length-2，那么数组中首尾两个元素是不参与排序的
自己看吧：
sort(arr, 1, arr.length - 2);//首尾两个元素不参与排序
运行结果
原数组：5 12 3 18 19 55 0 28 -1 33
排序后：5 -1 0 3 12 18 19 28 55 33
再来一个加深理解：
sort(arr, 5, arr.length - 1);//前5个元素不参与排序
运行结果
原数组：5 12 3 18 19 55 0 28 -1 33
排序后：5 12 3 18 19 -1 0 28 33 55
ok我话说完，skr~
