java实现快速排序

zzzmh 发布于2019-08-16 12:31 / 3264人阅读

摘要：总的来说，快速排序也是利用了分治法的思想。快速排序的时间复杂度为，这是一种不稳定的排序方法。以下代码实现以二分法的思路对数组分组以最左边最右边中间三个数的中位数为主元确定主元

以上为思路。
总的来说，快速排序也是利用了分治法的思想。
基本步骤：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];
    }

云服务器 GPU云服务器 java快速排序 java递归快速排序 java中快速排序 java快速排序泛型

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/71240.html

算法学习之路，排序之快速排序（Java实现）

摘要：接下来我来说明快速排序的思路以及实现的代码。快速排序思路首先是定义一个变量，把数组的第一个元素的值赋给，然后定义两个变量指向数组的第一个元素和最后一个元素。今天突然想写个排序，以前写过，然后写了之后一直出错，然后自己百度了一下，看了别人写的方法，自己也尝试着写了一个。接下来我来说明快速排序的思路以及实现的代码。快速排序思路：首先是定义一个变量key，把数组的第一个元素的值赋给key...

charles_paul 2019-08-14 15:38 评论0 收藏0
java排序算法(快速排序)

摘要：快速排序思路在数组中寻一中间数，将比中间数小的放在左边，将比中间数大的放在右边从左边开始找，找到比中间数大的，记住，从右边开始找，找到比中间数小的，然后交换两边然后在左边再寻一中间数，同坐上面的事，右边也一样，然后循环实现数组输出中间值的位快速排序思路在数组中寻一中间数，将比中间数小的放在左边，将比中间数大的放在右边从左边开始找，找到比中间数大的，记住，从右边开始找，找到比中间数...

khlbat 2019-08-15 17:53 评论0 收藏0
跳槽季如何快速全面复习面试题

摘要：排序算法和集合工具类排序算法和集合工具类。面试官总是问排序算法也不是在难为你，而是在考察你的编程功底。你首先要理解多线程不仅仅是和那么简单，整个并发包下面的工具都是在为多线程服务。去年的这个时候楼主通过两个月的复习拿到了阿里巴巴的 offer，有一些运气，也有一些心得，借着跳槽季来临特此分享出来。简单梳理一下我的复习思路，同时也希望和大家一起交流讨论，一起学习，如果不对之处欢迎指正一...

keke 2019-08-16 14:25 评论0 收藏0
七大排序算法总结(java)

摘要：前面介绍了七大算法的思想与实现步骤，下面来做一个归总。直到无序区中的数为零，结束排序。步骤以从小到大为例，排序数组大小为。比较完以后则排序结束。堆排序思想堆排序是采用树的形式的数据结构来进行排序的，其中每一个堆都是完全二叉树。前面介绍了七大算法的思想与实现步骤，下面来做一个归总。排序方法平均复杂度最坏复杂度最好复杂度辅助空间稳定性直接选择排序 O(n^2...

cartoon 2019-08-14 14:09 评论0 收藏0