Java实现快速快速排序算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Java实现快速快速排序算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2233字，纯文字阅读大概需要4分钟。

内容图文

---

算法简介

快速排序（Quick Sort） 是由冒泡排序改进而得的。在冒泡排序过程中，只对相邻的两个记录进行比较，因此每次交换两个相邻记录时只能消除一个逆序。如果能通过两个（不相邻）记录的一次交换直接消除多个逆序，则会大大加快排序的虚度。快速排序方法中的一次交换可以消除多个逆序。

算法步骤

在待排序的n个记录中任取一个记录（通常选取第一个记录）作为枢轴，设其关键字为pivotkey。经过一趟排序后，把所有关键字小于pivotkey的记录交换的前面，把所有大于pivotkey的记录交换到后面，结果将待排序记录分成两个子表，最后将枢轴放置在分界处的位置。然后对左右两个子表重复上述过程，直到每一个子表只有一个记录时，排序完成。换句话说，就是每一趟排序都将一条记录放在了正确的位置上。（正确位置就是完成排序时它所处的位置）

具体步骤

1. 选择待排序表中第一个记录作为枢轴，保存在变量pivotkey中。附设两个指针low和high,初始时分别指向表的上界和下界（第一趟时，low = 0;high = nums.length）。
2. 从表的最右侧位置依次向左侧搜索，当找到第一个值小于pivotkey的记录时，将其移动到low处。具体操作是：当low < high时，若high所指记录大于等于pivotkey，则向左移动指针high；否则移动该记录。
3. 然后从表的最左侧位置依次向右侧搜索，找到第一个关键字大于pivotkey的记录，将其移动到high处。具体操作是：若low所指记录的值小于pivotkey，则向右移动指针low；否则移动该记录。
4. 重复步骤2和3，直至low和high。此时low和high的位置即为枢轴在此躺排序的最终位置，原表被分为两个子表。

代码实现

public class Sort {
    public static void main(String[] args) {
        int[] nums = new int[]{1, 321, 34, 54, 56, 745, 7546,3,423,463,64,234,143421};
        quickSort(nums);
        for (int n : nums) {
            System.out.println(n);
        }
//        1
//        3
//        34
//        54
//        56
//        64
//        234
//        321
//        423
//        463
//        745
//        7546
//        143421
    }
    public static void quickSort(int[] nums) {
        qSort(nums,0,nums.length - 1);
    }
    public static void qSort(int[] nums,int low,int high) {
        if(low < high) {
            int pivotloc = partition(nums,low,high);
            qSort(nums,low,pivotloc - 1);
            qSort(nums,pivotloc+1,high);
        }

    }
    public static int partition(int[] nums,int low,int high) {
        int pivotkey = nums[low];  //用于比较的枢轴
        while (low < high) {
            while (low < high && nums[high] >= pivotkey) { high --; }
            nums[low] = nums[high];
            while (low < high && nums[low] <= pivotkey) { low ++;}
            nums[high] = nums[low];
        }
        nums[low] = pivotkey;
        return low;
    }
}

内容总结

以上是互联网集市为您收集整理的Java实现快速快速排序算法全部内容，希望文章能够帮你解决Java实现快速快速排序算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---