当前位置:   article > 正文

快速排序的三种实现方法_快速排序算法实现

快速排序算法实现
  1. 快速排序的单趟排序

快速排序的单趟排序:是以一个数作为基准值,实现将数组中比基准数小的数放在基准值的左侧,比基准值大的数放在基准值的右侧。

方法一:霍尔法

霍尔法的由来:霍尔是一个人的名字,他是最初发现快速排序的人,所以,它使用的单趟排序算法被称为霍尔法。

1.基本思路:

​ 用key标记基准值的下标(数组下标0的元素),使用两个指针left和right分别指向待排数组的最左侧和最右侧,right指针找比key基准值小的数,left指针找比key基准值大的数,找到后将两个数交换位置,同时实现大数右移和小数左移,直到left与right相遇则排序完成,最后将key基准值的下标返回,就完成了单趟排序。

  1. package LiKou;
  2. public class QuickSort {
  3. public static void main(String[] args) {
  4. int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
  5. quickSort(arr,0,arr.length-1);
  6. for (int i = 0; i < arr.length; i++) {
  7. System.out.println(arr[i]);
  8. }
  9. }
  10. public static void quickSort(int[] arr,int low,int high){
  11. int i,j,temp,t;
  12. if(low>high){
  13. return;
  14. }
  15. i=low;
  16. j=high;
  17. //temp就是基准位 temp = arr[low];
  18. while (i<j) {
  19. //先看右边,依次往左递减
  20. while (temp<=arr[j]&&i<j) {
  21. j--;
  22. }
  23. //再看左边,依次往右递增
  24. while (temp>=arr[i]&&i<j) {
  25. i++;
  26. }
  27. //如果满足条件则交换
  28. if (i<j) {
  29. t = arr[j];
  30. arr[j] = arr[i];
  31. arr[i] = t;
  32. }
  33. }
  34. //最后将基准为与i和j相等位置的数字交换
  35. arr[low] = arr[i];
  36. arr[i] = temp;
  37. //递归调用左半数组
  38. quickSort(arr, low, j-1);
  39. //递归调用右半数组
  40. quickSort(arr, j+1, high);
  41. }
  42. }

方法二:挖坑法1.基本思路:挖坑法是将key基准值用变量单独保存,然后将key的位置空出来形成一个坑,left和right指针分别从左右两端向中心遍历,此时left先指向这个坑,从右边先开始,right找比key小的数,找到后将该数直接放进坑里,并将自己空出来的位置设置为坑,left找比key大的数,找到后将该数放进坑里,并将现在空出来的位置设置为坑,一直遍历,直到left与right相遇,相遇位置一定为坑(left和right必定有一个指向坑),此时将key基准值放进坑内,并返回基准值下标完成单趟排序。

  1. package LiKou;
  2. public class QuickSort2 {
  3. public static void main(String[] args) {
  4. int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
  5. Quick3(arr,0,arr.length-1);
  6. for (int i = 0; i < arr.length; i++) {
  7. System.out.println(arr[i]);
  8. }
  9. }
  10. public static void Quick2(int[] arr,int left,int right){
  11. if(left>right){
  12. return;
  13. }
  14. int key=arr[left];
  15. int pre=left;
  16. int cur=left+1;
  17. while(cur<=right){
  18. if(arr[cur]<=key && ++pre!=cur){
  19. int temp=arr[cur];
  20. arr[cur]=arr[pre];
  21. arr[pre]=temp;
  22. }
  23. cur++;
  24. }
  25. int temp=arr[left];
  26. arr[left]=arr[pre];
  27. arr[pre]=temp;
  28. Quick2(arr,pre+1,right);
  29. Quick2(arr,left,pre-1);
  30. }
  31. public static void Quick3(int[] arr,int left,int right){
  32. if(left>=right){
  33. return;
  34. }
  35. int key=arr[left];
  36. int i=left;
  37. int j=right;
  38. while(i<j){
  39. while(j>i && arr[j]>=key){
  40. j--;
  41. }
  42. if(j>i){
  43. arr[i]=arr[j];
  44. }
  45. while(i<j && arr[i]<=key){
  46. i++;
  47. }
  48. if(j>i){
  49. arr[j]=arr[i];
  50. }
  51. }
  52. arr[i]=key;
  53. Quick3(arr,left,i-1);
  54. Quick3(arr,i+1,right);
  55. }
  56. }

方法三:前后指针法

1.基本思路:

(1) 用key保存数组第一个元素作为基准值,定义前指针prev指向第一个数,后指针cur指向前指针的后一个位置。

(2) 由cur挨个遍历数组中的数据,如果cur寻找比key基准值小的数,则prev后移一个位置,并且交换cur和prev所对应的元素值,cur和prev位置不变。

(3) 依次类推直到cur完全遍历完数组,停止。

prev之前的值一定小于key基准值,而prev与cur之间的一定大于基准值

最后将prev处与key位置的元素交换,将基准值下标返回(此时基准值下标已经交换到prev位置)。则完成单趟排序。

  1. package LiKou;
  2. public class QuickSort2 {
  3. public static void main(String[] args) {
  4. int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
  5. Quick2(arr,0,arr.length-1);
  6. for (int i = 0; i < arr.length; i++) {
  7. System.out.println(arr[i]);
  8. }
  9. }
  10. public static void Quick2(int[] arr,int left,int right){
  11. if(left>right){
  12. return;
  13. }
  14. int key=arr[left];
  15. int pre=left;
  16. int cur=left+1;
  17. while(cur<=right){
  18. if(arr[cur]<=key && ++pre!=cur){
  19. int temp=arr[cur];
  20. arr[cur]=arr[pre];
  21. arr[pre]=temp;
  22. }
  23. cur++;
  24. }
  25. int temp=arr[left];
  26. arr[left]=arr[pre];
  27. arr[pre]=temp;
  28. Quick2(arr,pre+1,right);
  29. Quick2(arr,left,pre-1);
  30. }
  31. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Monodyee/article/detail/454438
推荐阅读
相关标签
  

闽ICP备14008679号