`

快速排序算法

阅读更多
    快速排序算法和冒泡排序算法类似,都是基于交换排序思想的,快速排序算法对冒泡排序算法进行了改进,从而具有更高的执行效率
    通过多次比较和交换来实现排序,流程如下:
    1)首先设定一个分界值,通过该分界值将数组分成左右两部分
    2)将大于等于分界值得数据集中到数组右边,小于分界值得数据集中到数组的左边。此时,左边部分中各元素都小于等于分界值,而右边部分中各元素都大于等于分界值
    3)然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样将左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理
    4)重复上述过程,可以看出,这是一个递归定义。
   
    例如:选择8个整型数据69、62、89、37、97、17、28、49是一组无序数据
    1)首先选取一个分界值,这里选择第一个数据69作为分界值。在变量left中保存数组的最小的序号0,在变量right中保存数据的最大序号7,在变量base中保存分界值69
    2)从数组右侧开始,逐个取出数据与分界值69比较,直到找到比base小的数据为止,数组最右侧的元素A[right]的值49比base变量保存的值69小。
    3)将右侧比基准base小的数保存到A[left]元素中。
    4)接下来,从数组左侧开始,逐个取出元素与分界值69比较,直到找到比分界值69大的数据为止。数组最左侧的元素A[left]的值为49,比base的值小,将left自增1再取A[left]的值62与base的值69比较,62小于69,继续将left自增1.再取A[left]的值89与base比较,89大于69,结束查找
    5)将左侧比分界值69大的数保存到A[right]元素中。
    6)将分界值69中的值保存到A[left]中,最后得到结果


public class QuickSort {
	static final int SIZE=18;
	static void quickSort(int[] arr,int left,int right)			//快速排序算法
	{
	    int f,t;
		int rtemp,ltemp;

	    ltemp=left;
	    rtemp=right;
	    f=arr[(left+right)/2];						//分界值
		while(ltemp<rtemp)
		{
	        while(arr[ltemp]<f)
			{
				++ltemp;
			}
	        while(arr[rtemp]>f) 
			{
				--rtemp;
			}
	        if(ltemp<=rtemp)
	        {
				t=arr[ltemp];
		        arr[ltemp]=arr[rtemp];
	    	    arr[rtemp]=t;
				--rtemp;
	        	++ltemp;
			}
	    }
	    if(ltemp==rtemp) 
		{
			ltemp++;
		}

	    if(left<rtemp) 
		{
			quickSort(arr,left,ltemp-1);			//递归调用
		}
	    if(ltemp<right) 
		{
			quickSort(arr,rtemp+1,right);			//递归调用
		}
	}
	public static void main(String[] args) 
	{
		int[] shuzu=new int[SIZE];
		int i;
		
		for(i=0;i<SIZE;i++)
		{
			shuzu[i]=(int)(100+Math.random()*(100+1));			//初始化数组
		}
		
		System.out.print("排序前的数组为:\n");				//输出排序前的数组
		for(i=0;i<SIZE;i++)
		{
			System.out.print(shuzu[i]+" ");
		}
		System.out.print("\n");
		
		quickSort(shuzu,0,SIZE-1);					//排序操作
		
		System.out.print("排序后的数组为:\n");
		for(i=0;i<SIZE;i++)
		{
			System.out.print(shuzu[i]+" ");					//输出排序后的数组
		}
		System.out.print("\n");

	}

}

分享到:
评论

相关推荐

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

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

    快速排序算法以及归并算法

    ### 快速排序算法 快速排序是一种高效的排序算法,采用分而治之的策略,其核心思想是选择一个基准元素,通过一趟排序将待排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分的所有数据都要小,然后再...

    快速排序算法matlab

    ### 快速排序算法在MATLAB中的应用与理解 #### 一、快速排序算法简介 快速排序是一种非常高效的排序算法,由英国计算机科学家托尼·霍尔(Tony Hoare)于1960年提出。它采用分治策略来把一个序列分为较小的两个子...

    C语言实现快速排序算法

    快速排序算法,C语言 快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有...

    c语言 数据结构 快速排序算法

    c语言版本的数据结构的快速排序算法,适用于新手学习

    快速排序算法实现

    快速排序算法C语言实现,快排序算法QuickSort.cpp

    快速排序算法实现 c#代码

    ### 快速排序算法在C#中的实现 #### 一、快速排序算法简介 快速排序是一种高效的排序算法,由英国计算机科学家托尼·霍尔(Tony Hoare)于1960年提出。该算法采用分治策略来把一个序列分为较小的两个子序列,再对这...

    快速排序算法java代码

    "快速排序算法java代码" 快速排序算法是由Tony Hoare在1960年提出的一种排序算法,它的平均时间复杂度为O(n log n),是目前最快的排序算法之一。下面我们将详细地讲解快速排序算法的java代码实现。 快速排序算法的...

    严蔚敏快速排序算法的伪代码。。。。。

    根据提供的标题、描述、标签及部分内容,我们可以梳理出与快速排序算法相关的关键知识点。 ### 快速排序算法概述 快速排序是一种高效的排序算法,在实际应用中,它的平均性能通常优于其他时间复杂度为 \(O(n\log n...

    分别使用Java和Python实现快速排序算法.zip

    快速排序:分别使用Java和Python实现快速排序算法.zip 快速排序:分别使用Java和Python实现快速排序算法.zip 快速排序:分别使用Java和Python实现快速排序算法.zip 快速排序:分别使用Java和Python实现快速排序算法....

    C++快速排序算法程序

    C++快速排序算法程序,用于处理大量数据, 并对这些数据进行快速的排序

    改进的快速排序算法

    快速排序算法的改进思路 1.选取好的基准,是两边的数据个数尽量的均匀 取数组的第一个,中间,最后一个数据,取三个数中第二大的数作为基准 2. 不递归 3.与插入结合,当段内的数组个数小于等于16的时候,使用...

    快速排序算法 C语言实现

    快速排序算法 C语言实现 快速排序算法是一种高效的排序算法,通过递归的方式将记录分区排序。下面将详细介绍快速排序算法的实现细节。 首先,我们需要了解快速排序算法的基本思想。快速排序算法的核心思想是选择一...

    Java实现快速排序算法+编程知识+技术开发

    Java实现快速排序算法+编程知识+技术开发; Java实现快速排序算法+编程知识+技术开发; Java实现快速排序算法+编程知识+技术开发; Java实现快速排序算法+编程知识+技术开发; Java实现快速排序算法+编程知识+技术...

    快速排序算法和冒泡排序效率对比

    快速排序和冒泡排序是两种常见的排序算法,它们在计算机科学中扮演着重要的角色,特别是在数据处理和优化程序性能方面。本篇文章将深入探讨这两种排序算法的原理、效率以及它们在C#编程语言中的实现。 首先,让我们...

    matlab 实现快速排序算法_一共有主程序,分类,插入和选择四个程序

    资源名:matlab 实现快速排序算法_一共有主程序,分类,插入和选择四个程序 资源类型:matlab项目全套源码 源码说明: 全部项目源码都是经过测试校正后百分百成功运行的,如果您下载后不能运行可联系我进行指导或者...

    超快速排序算法,性能优于快速排序算法和基数排序算法

    ### 超快速排序算法详解 #### 一、引言 在计算机科学中,排序算法是一种重要的基础算法,被广泛应用于各种系统软件和应用软件之中。传统的排序算法如快速排序和基数排序各有优缺点:快速排序算法因其简洁的结构和...

    一个不会出现堆栈溢出的快速排序算法

    总的来说,采用循环法的快速排序算法解决了递归版本可能导致的堆栈溢出问题,且在处理大型随机数组时能保持良好的效率。通过对数组的巧妙分区和基准元素的随机选取,该算法在实际应用中表现出色。文件"cishi"可能...

Global site tag (gtag.js) - Google Analytics