Java教程:教你5分钟了解快速排序,前言: 快速排序是面试中经常会问到的一种排序算法,对比其他一些排序算法,快速排序的平均时间相对较少。 快速排序思想介绍快速排序使用了分治的思想,通过一轮的排序,可以将序列分割成独立的两个部分,其中一部分的值均比基准值小,另一部分的值均比基准值大。而后针对两部分序列再分别按照同样的算法进行排序,直到序列整体有序。 以如下序列arr为例进行升序排序,说明快速排序的基本算法 第一个位置的值23作为基准值base,从右边开始比较,如果arr[high]>base,high前移。 arr[high]<base,arr[low]=arr[high],然后low后移 Arr[low]<base,不交换,low后移 Arr[low]>base,arr[high]=arr[low],high前移 Arr[high]<base,arr[low]=base,low后移, low和high指向同一个位置, 将基准数据赋值给low和high指向的同一位置,本轮比较结束。然后,再对23前的数据和23后面的数据,分别再按照上述算法进行比较排序,依次类推,直到所有元素有序。 快速排序的代码实现由于对各个子序列都要进行相同算法的排序,可以采用递归思想实现快速排序 1. package com.qfedu.vo; 2. 3. public class QuickSort { 4. public static void quickSort(int[] arr,int low,int high){ 5. int i,j,temp,t; 6. if(low>high){ 7. return; 8. } 9. i=low; 10. j=high; 11. //temp存储基准数 12. temp = arr[low]; 13. 14. while (i<j) { 15. //先从右边开发判断,条件成立,high向左递减 16. while (temp<=arr[j]&&i<j) { 17. j--; 18. } 19. arr[i]=arr[j]; 20. //再从左边开始,low依次向右递增 21. while (temp>=arr[i]&&i<j) { 22. i++; 23. } 24. arr[j]=arr[i]; 25. arr[i]=temp; 26. 27. } 28. //递归调用左边内容进行排序 29. quickSort(arr, low, j-1); 30. //递归调用右边内容进行排序 31. quickSort(arr, j+1, high); 32. } 33. 34. 35. public static void main(String[] args){ 36. int[] arr = {15,23,7,87,34,56}; 37. quickSort(arr, 0, arr.length-1); 38. for (int i = 0; i < arr.length; i++) { 39. System.out.println(arr[i]); 40. } 41. } 42. } 总结以上介绍的是普通快速排序,针对快速排序,还有一些改进算法,可以进一步提高执行效率。 好程序员Java培训官网:http://www./javaEE_class.shtml |
|
来自: 好程序员IT > 《Java培训教程》