`
zhao1659
  • 浏览: 7064 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

算法(快速排序)

阅读更多
快速排序就是把某一个值排到中间,比如:第一个值跟最后一个开始比,如果比第一个值小,就交换位置,然后再从第一个位置开始找比他大的值,进行交换。
java代码:参考了百科里面的例子
package zy.boring.order.impl;

import zy.boring.order.QuickOrder;

public class QuickOrderImpl implements QuickOrder {

	@Override
	public int[] quickOrder(int[]data, int low, int high) {
		//定义局部变量i,j,初始i,j是递归的首位两个元素的索引
		int i = low;
		int j = high;
		//一开始老不能结束递归,加了这句
		if(low<high){
			//确定数组第一个元素为目标元素
			int keyInt = data[i];
			//确保i始终小于j
			while(i<j){
				//首先通过第一个元素(keyInt)跟从末尾开始的元素逐一比较,找到比keyInt小的元素
				while(i<j && keyInt<data[j]){
					j--;
				}
				//把data[i]交换
				if(i<j){
					data[i] = data[j];
					//焦点向右移
					i++;
				}
				//通过keyInt从头开始的元素逐一比较,找到比keyInt大的元素
				//这里开始的时候没有加i<j这句,导致了错误,要时刻保持i<j
				while(i<j && keyInt>data[i]){
					i++;
				}
				//data[j]交换
				if(i<j){
					data[j] = data[i];
					//焦点向左移
					j--;
				}
			}
			data[i] = keyInt;
			//调用递归,分别把左半边跟又半边进行排序
				quickOrder(data,low,i);
				quickOrder(data,i+1,high);
		}
		return data;
	}

}


虽然参考了例子,但还是遇到一些问题,也看到自己的一些不足。
不常编码,junit的使用,递归函数

写了相应的测试,不知道合不合理。
开始的时候判断两个数组是否相等还自己写了一大堆,后来发现原来有工具类可以来用,这里用到了Arrays的工具类。
package zy.boring.order.impl.test;

import java.util.Arrays;

import junit.framework.TestCase;
import zy.boring.order.QuickOrder;
import zy.boring.order.impl.QuickOrderImpl;

public class QuickOrderImplTest extends TestCase {

	protected void setUp() throws Exception {
		super.setUp();
	}

	public void testQuickOrder() {
		int[] testInt = {5,9,3,8,2,1,6,7};
		int[] expectInt = {1,2,3,5,6,7,8,9};
		QuickOrder quickOrder = new QuickOrderImpl();
		int[] actureInt = quickOrder.quickOrder(testInt, 0, testInt.length-1);
		//用数组工具Arrays来比较是否
		assertTrue(Arrays.equals(actureInt, expectInt));
	}

}

分享到:
评论

相关推荐

    舞动的排序算法 快速排序

    舞动的排序算法 快速排序 通过动画演示快速排序,很好的学习,课程资源。

    Python 算法 快速排序.py

    Python 算法 快速排序.py

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

    根据给定的文件信息,我们将深入探讨两种经典的排序算法——快速排序和归并排序,并结合Java语言实现进行详细解析。 ### 快速排序算法 快速排序是一种高效的排序算法,采用分而治之的策略,其核心思想是选择一个...

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

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

    算法 快速排序 冒泡排序 监视哨 折半查找

    快速排序、冒泡排序、监视哨以及折半查找是计算机科学中非常重要的基础算法,对于理解和应用编程至关重要,特别是对于参与ACM(国际大学生程序设计竞赛)或其他算法竞赛的程序员来说,这些都是必须掌握的核心技能。...

    我最喜欢的排序算法 快速排序和归并排序.doc

    快速排序和归并排序是两种高效且广泛应用的排序算法,它们在时间和空间复杂度上有各自的特点。 快速排序是由英国计算机科学家C.A.R. Hoare在1960年提出的,其核心思想是“分治”策略。算法首先选择一个基准元素,...

    最快的排序算法 计算机最快的算法-史上14个最快速算法:孩子的计算能力爆表!大脑堪比计算机!...,排序算法数据结构

    快速排序算法是一种高效的排序算法,它的工作原理是通过选择一个元素作为pivot,然后将数组分为两个部分,以达到排序的目的。快速排序算法的时间复杂度为O(n log n),因此它适合大规模的数据排序。 5.归并排序算法 ...

    快速排序优化算法

    Java语言的快速排序优化算法实现 算法思想: 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程...

    算法实验(java快速排序。归并排序,分治算法,回溯算法,n后问题)

    包括所有算法分析设计的实验(java快速排序。归并排序,分治算法,回溯算法,n后问题)

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

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

    分治算法实验(用分治法实现快速排序算法)教学文稿.docx

    分治算法实验(用分治法实现快速排序算法)教学文稿.docx 本文档是关于分治算法实验的教学文稿,旨在指导学生学习分治算法的思想和实现快速排序算法。通过实验报告,学生可以了解分治算法的基本概念、算法设计思想、...

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

    快速排序算法的基本思想是:随机选取数组中的一个值,将所要进行排序的数分为左右两个部分,其中一部分的所有数据都比另外一部分的数据小,然后将所分得的两部分数据进行同样的划分,重复执行以上的划分操作,直到...

    快速排序算法相关分析

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

    C++算法快速排序(模板)

    这个是C++中的快速排序算法(模板)(凑字)(来对抗肌肤垃圾时间浪费了时空的距离附近)

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

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

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

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

    快速排序算法matlab

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

    快速排序-算法报告.doc

    快速排序是一种高效的排序算法,由C.A.R. Hoare在1960年提出,它采用了分治(Divide and Conquer)策略。快速排序的基本思想是通过一趟排序将待排序的数据分割成两部分,其中一部分的所有数据都比另一部分的所有数据...

Global site tag (gtag.js) - Google Analytics