脚本宝典收集整理的这篇文章主要介绍了

java实现快速排序

脚本宝典小编觉得挺不错的,现在分享给大家,也给大家做个参考,希望能帮助你少写一行代码,多一份安全和惬意。

图片描述

以上为思路。
总的来说,快速排序也是利用了分治法的思想。
基本步骤:1.先选择好合适的主元pivot,
2.然后再把比主元小的元素放到主元的左边(右边),把较大的元素放到主元的右边(左边),
3.接着再以主元为分界点,把数组分为两个部分,再分别对两边的数组重复第二步的操作,
4.最后便实现了有序排列。

快速排序的时间复杂度为O(NlgN),这是一种不稳定的排序方法。

以下代码实现

public static void quickSort(int arr[], int left, int right) {         int index = partition(arr, left, right);                  if (left < index - 1)             quickSort(arr, left, index - 1);              if (index < right)             quickSort(arr, index, right);     }     //以二分法的思路对数组分组     private static int partition(int arr[], int left, int right){         int i = left, j = right;         int tmp;         //以最左边、最右边、中间三个数的中位数为主元         int pivot = findPivot(arr, left, (left+right)>>1, right);            while (i <= j) {                    while (arr[i] < pivot)                 i++;              while (arr[j] > pivot)                 j--;              if (i <= j) {                 tmp = arr[i];                 arr[i] = arr[j];                 arr[j] = tmp;                 i++;                 j--;             }         }            return i;     }     //确定主元     private static int findPivot(int[] nums, int left, int mid, int right){         if(nums[left] > nums[right]) {             int temp = nums[left];             nums[left] = nums[right];             nums[right] = temp;         }                  if(nums[left] > nums[mid]) {             int temp = nums[left];             nums[left] = nums[mid];             nums[mid] = temp;         }                  if(nums[mid] > nums[right]) {             int temp = nums[right];             nums[right] = nums[mid];             nums[mid] = temp;         }         return  nums[mid];     }

总结

以上是脚本宝典为你收集整理的

java实现快速排序

全部内容,希望文章能够帮你解决

java实现快速排序

所遇到的程序开发问题,欢迎加入QQ群277859234一起讨论学习。如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典网站推荐给程序员好友。 本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。

80%的人都看过