`
ASCII
  • 浏览: 30815 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

快速排序

阅读更多
/**
 *  这段程序并不难,应该很好看懂,我把过程大致讲一下,首先你的脑子里先浮现一个数组和三个指针,
 *  第一个指针称为p指针,在整个过程结束之前它牢牢的指向第一个数,第二个指针和第三个指针分别为lo指针和hi指针,
 *  分别指向最左边的值和最右边的值。lo指针和hi指针从两边同时向中间逼近,在逼近的过程中不停的与p指针的值比较,
 *  如果lo指针的值比p指针的值小,lo++,还小还++,再小再++,直到碰到一个大于p指针的值,这时视线转移到hi指针,
 *  如果 hi指针的值比p指针的值大,hi--,还大还--,再大再--,直到碰到一个小于p指针的值。
 *  这时就把lo指针的值和hi指针的值做一个调换。持续这过程直到两个指针碰面,这时把p指针的值和碰面的值做一个调换,
 *  然后返回p指针新的位置。
 * 
 * @author 75-qj
 * @version $Id: QuickSort.java, v 0.1 2010-3-4 上午11:09:35 75-qj Exp $
 */
public class QuickSort {

    /**
     * 主算法,运用递归
     * 
     * @param n        待排序的数组
     * @param left     数组左边序号
     * @param right    数组右边序号
     */

    void quicksort(int n[], int left, int right) {
        int dp;
        if (left < right) {

            dp = partition(n, left, right);

            quicksort(n, left, dp - 1);

            quicksort(n, dp + 1, right); //这两个就是递归调用,分别整理53左边的数组和右边的数组
        }
    }

    /**
     * 返回中间值的位置,下面这函数就是做这个的。
     * 
     * @param n        待排序的数组
     * @param left     数组左边序号
     * @param right    数组右边序号
     * @return         
     */

    int partition(int n[], int left, int right) {
        int lo, hi, pivot, t;

        pivot = n[left];
        lo = left - 1;
        hi = right + 1;

        while (lo + 1 != hi) {
            if (n[lo + 1] <= pivot)
                lo++;
            else if (n[hi - 1] > pivot)
                hi--;
            else {
                t = n[lo + 1];
                n[++lo] = n[hi - 1];
                n[--hi] = t;
            }
        }

        n[left] = n[lo];
        n[lo] = pivot;
        return lo;
    }

    public static void main(String[] args) {
        QuickSort q = new QuickSort();

        int[] n = { 53, 12, 98, 63, 18, 72, 80, 46, 32, 21 };

        q.quicksort(n, 0, 9);

        for (int i : n) {
            System.out.println(i);
        }
    }
}

 

这个是从网上找的,并非原创。只是自我总结归纳一下,望作者海涵,哈哈。

基础的算法,数据结构,我们这些java人员也不能丢弃,需要好好总结下,才能写出更好的程序。

分享到:
评论

相关推荐

    快速排序 快速排序例子

    ### 快速排序知识点解析 #### 一、快速排序简介 快速排序是一种高效的排序算法,由英国计算机科学家托尼·霍尔(Tony Hoare)在1960年提出。它采用分治策略来把一个序列分为较小和较大的两个子序列,然后递归地...

    C语言实现多种链表快速排序

    快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出,它的基本思想是通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,然后分别对这两部分记录...

    快速排序 快速排序快速排序快速排序

    快速排序快速排序 快速排序 快速排序 快速排序 快速排序

    确定性快速排序与随机化快速排序的比较

    快速排序是一种高效的排序算法,在计算机科学和数学中被广泛研究。其基本原理是分治法策略,即将一组数据分为两个子序列并分别进行排序。快速排序期望的时间复杂度为O(nlogn),但在最坏的情况下,它的时间复杂度可...

    简单的快速排序

    快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法(Divide and Conquer),即把一个大问题分解成若干个小问题来解决,最终将小问题的结果合并得到原问题的解。在这...

    排序算法编程 堆排序 快速排序

    本主题将深入探讨四种常见的排序算法:堆排序、快速排序以及两种未在标题中明确提到但同样重要的排序方法——基数排序和计数排序。 首先,让我们详细了解一下堆排序。堆排序是一种基于比较的排序算法,利用了数据...

    快速排序 --- 非递归实现

    快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法,通过一趟排序将待排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分的所有数据都要小,然后再按...

    快速排序算法(c#实现)

    快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治策略,通过一趟排序将待排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分的所有数据都要小,然后再...

    快速排序算法相关分析

    快速排序算法是一种有效的排序算法,虽然算法在最坏的情况下运行时间为 O(n^2),但由于平均运行时间为 O(nlogn),并且在内存使用、程序实现复杂性上表现优秀,尤其是对快速排序算法进行随机化的可能,使得快速排序在...

    随机快速排序 算法设计与分析实验报告

    (1)用随机快速排序的方法,对输入的数值以从大到小的顺序进行快速排序。 (2)对随机快速排序和冒泡排序这两种排序方法进行比较,测试其在不同数值大小的情况下算法运行的时间复杂度。 二、 实验要求 快速排序...

    快速排序算法的java实现

    快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法(Divide and Conquer),通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的...

    冒泡排序和快速排序的时间性能

    冒泡排序和快速排序的时间性能 冒泡排序和快速排序是两种常用的排序算法,它们的时间性能是开发者和研究人员所关心的热点话题。在本文中,我们将对冒泡排序和快速排序的时间性能进行深入分析和比较。 冒泡排序是一...

    快速排序的递归简洁实现

    快速排序是一种高效的排序算法,由英国计算机科学家托尼·霍尔于1960年提出。它采用分治策略来把一个序列分为较小的两个子序列,然后递归地对子序列进行排序,最终合并得到有序序列。快速排序在平均情况下的时间...

    TIA博途中通过SCL语言实现快速排序的具体方法示例.docx

    快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它基于分治法的策略,通过选取一个基准值并重新排列数组,将问题分解为较小的部分,然后递归地对这些部分进行排序,最终达到整个序列...

    FPGA并行快速排序算法-位宽可设

    在本文中,我们将深入探讨基于FPGA的并行快速排序算法,特别关注“位宽可设”的特性。这种算法能够高效地处理大量数据,并且在硬件实现上具有很高的灵活性。我们将从以下几个方面来阐述这个主题: 一、快速排序算法...

    快速排序演示程序/vc++/mfc

    快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它基于分治策略,通常比其他O(n^2)时间复杂度的排序算法更快,平均时间复杂度为O(n log n)。在本项目中,“快速排序演示程序/vc++/mfc...

    《快速排序 直接插入排序 堆排序 希尔排序 选择排序:五种排序》

    (1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...

    数据结构 快速排序 输出每一趟结果

    根据给定文件的信息,我们可以总结出以下关于“数据结构 快速排序 输出每一趟结果”的知识点: ### 一、快速排序的基本概念 快速排序是一种高效的排序算法,采用分治法策略来把一个序列分为较小和较大的两个子序列...

Global site tag (gtag.js) - Google Analytics