小学生才玩儿冒泡,猛男都玩儿快排
在常见的排序算法中,快速排序在性能上有绝对的优势,家里有条件的建议都把原理搞懂;
老规矩,先看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~