好程序员Java教程教你5分钟了解快速排序

傷城~ 2021-11-22 21:42 236阅读 0赞

好程序员Java教程教你5分钟了解快速排序，前言：

快速排序是面试中经常会问到的一种排序算法，对比其他一些排序算法，快速排序的平均时间相对较少。

## **快速排序思想介绍** ##

快速排序使用了分治的思想，通过一轮的排序，可以将序列分割成独立的两个部分，其中一部分的值均比基准值小，另一部分的值均比基准值大。而后针对两部分序列再分别按照同样的算法进行排序，直到序列整体有序。

以如下序列arr为例进行升序排序，说明快速排序的基本算法

**![1666397-20190621143659028-1329953659.png][]**

第一个位置的值23作为基准值base，从右边开始比较，如果arr\[high\]>base,high前移。

**![1666397-20190621143708321-99698191.png][]**

arr\[high\]<base,arr\[low\]=arr\[high\]，然后low后移

**![1666397-20190621143716888-138076940.png][]**

Arr\[low\]<base,不交换，low后移

![1666397-20190621143726614-2044067697.png][]

Arr\[low\]>base,arr\[high\]=arr\[low\]，high前移

**![1666397-20190621143735342-1986408980.png][]**

Arr\[high\]<base,arr\[low\]=base，low后移，

**![1666397-20190621143742354-1068932878.png][]**

low和high指向同一个位置，

将基准数据赋值给low和high指向的同一位置，本轮比较结束。然后，再对23前的数据和23后面的数据，分别再按照上述算法进行比较排序，依次类推，直到所有元素有序。

**![1666397-20190621143749016-1862008636.png][]**

## **快速排序的代码实现** ##

由于对各个子序列都要进行相同算法的排序，可以采用递归思想实现快速排序

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. \}

## **总结** ##

以上介绍的是普通快速排序，针对快速排序，还有一些改进算法，可以进一步提高执行效率。

转载于:https://www.cnblogs.com/gcghcxy/p/11064449.html

[1666397-20190621143659028-1329953659.png]: /images/20211122/1543532b11c64e8e8e23f3025d516eff.png
[1666397-20190621143708321-99698191.png]: /images/20211122/bfa731642f73474d9b7e1d7e410210a6.png
[1666397-20190621143716888-138076940.png]: /images/20211122/ee2d9adbf6664e6887eb2f6f7500b4b0.png
[1666397-20190621143726614-2044067697.png]: /images/20211122/da6a28854c8d48f69626247b5d8bf319.png
[1666397-20190621143735342-1986408980.png]: /images/20211122/2c28bda984aa43e3b9fda8e65b19d595.png
[1666397-20190621143742354-1068932878.png]: /images/20211122/08f93495154a4a4f95af622c704bad70.png
[1666397-20190621143749016-1862008636.png]: /images/20211122/9a4c17e2e6014315b2ef1bd54368598f.png