`
cooliufang
  • 浏览: 129703 次
社区版块
存档分类
最新评论

Java排序算法之 —— 快速排序

阅读更多
package algorithm.sort;

/**
 * 快速排序:基于分治模式 分解: 划分为两个子数组(可能为空),A[left..mid-1]和A[mid+1..right]. 其中,前一个数组都小于等于A[mid],后一个数组都大于等于A[mid].mid下标在过程中划分得出。
 * 解决:递归调用快速排序,对两个子数组排序 合并:因为子数组已经是排好序,所以合并不需要操作即可得到排好序的数组
 * 
 * @author Administrator
 * 
 */
public class QuickSort {
	//对数组指定元素进行排序
	public void quickSort(int[] a, int from, int end) {
		if (from < end) {
			int mid = partition(a, from, end);
			quickSort(a, from, mid - 1);
			quickSort(a, mid + 1, end);
		}
	}
	
	//整个数组排序
	public void quickSort(int[] a) {
		quickSort(a, 0, a.length-1);
	}
	
	//快速排序的关键过程是对partition过程,对子数组重排
	public int partition(int[] a, int from, int end) {
		int i = from - 1;
		for (int j = from; j < end; j++) {
			if (a[j] <= a[end]) {	// 首先以最后一个元素作为中间分隔元素
				i++;
				exchange(a, i, j);
			}
		}
		i++;
		exchange(a, i, end);
		return i;
	}

	// 交换元素
	public void exchange(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	// 打印数组
	public void printArr(String str, int[] a) {
		System.out.print(str + "\t");
		for (int i = 0; i < a.length; i++)
			System.out.print(a[i] + " ");
		System.out.println();
	}

	//测试数据
	public static void main(String[] args) {
		QuickSort qs = new QuickSort();
		int[] a = {2,5,78,56,43,9,23};
		qs.printArr("原始数组为:", a);
		qs.quickSort(a);
		qs.printArr("快速排序后:", a);
	}
}



//output~:
原始数组为: 2 5 78 56 43 9 23
快速排序后: 2 5 9 23 43 56 78
分享到:
评论

相关推荐

    算法可视化系列——排序算法——快速排序

    快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法(Divide and Conquer)。在这个系列中,我们将通过算法可视化来深入理解快速排序的工作原理。 快速排序的步骤...

    java算法——快速排序

    快速排序 * 1.i=left,j=right,将基准数挖出形成第一个坑a[i]; * 2.j--由后向前找比它小的数,找到后挖出此数填前一个坑a[i]; * 3.i++由前向后找比它大的数,找到后挖出此数填到前一个坑a[j]中 * 4.以i为中线,...

    算法可视化系列——排序算法——冒泡排序

    - 在实际编程中,更高效的排序算法如快速排序、归并排序等更为常用。 在`AlgorithmBubleSort.java`中,我们还可以探讨代码的可读性、空间复杂度以及可能的优化措施,例如使用双指针法减少不必要的比较。这些都将是...

    算法课程设计——分治法(java实现)

    在本课程设计中,我们将使用 Java 语言对快速排序算法进行实现,并对算法的性能进行分析和比较。 快速排序算法的优点包括: * 高效的排序速度:快速排序算法的时间复杂度为 O(n log n),它是一种高效的排序算法,...

    算法可视化系列——排序算法——选择排序

    **选择排序**是一种简单直观的排序算法,它的工作原理如下:...在实际应用中,更高效的排序算法如快速排序、归并排序或堆排序等通常会优先考虑。然而,对于教学和理解排序算法的基本原理,选择排序是一个很好的起点。

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

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

    算法可视化系列——排序算法——希尔排序

    希尔排序(Shell Sort)是一种基于插入排序的快速排序方法,由Donald Shell于1959年提出。它的主要思想是将待排序的数据按照一定的间隔进行分组,然后对每组进行插入排序,随着间隔逐渐缩小,最后进行一次全排列,...

    快速排序与归并排序的算法比较实验报告

    这篇实验报告将深入探讨两种经典的排序算法——快速排序和归并排序,通过对它们在Java环境中的实现和性能测试,揭示它们在处理不同规模数据时的效率差异。 **快速排序(Quick Sort)** 快速排序由C.A.R. Hoare在...

    java版本排序算法

    以上介绍了三种基本的排序算法——插入排序、冒泡排序和选择排序。虽然它们在处理小规模数据集时表现良好,但在大规模数据集面前,这些算法的性能通常不如更高效的算法,如快速排序、归并排序等。然而,了解这些基础...

    数据结构与算法分析——Java语言描述

    常见的排序算法(如冒泡排序、快速排序、归并排序、堆排序)和查找算法(如线性查找、二分查找)都有详尽的解释和实例。此外,还包括动态规划、贪心算法、回溯法等高级算法思想。算法分析不仅关注实现,更强调时间...

    排序算法 Java经典算法

    首先,我们来看看基础的排序算法——冒泡排序。冒泡排序是最简单的交换排序,通过重复遍历待排序的数列,依次比较相邻元素并根据需要交换它们的位置,直到没有任何一对数字需要交换为止。虽然效率较低,但它对于理解...

    最快的排序算法 图解八大排序算法——我见过的最详细的讲解(转),排序算法数据结构

    常见的排序算法有八种,即选择排序、冒泡排序、插入排序、归并排序、快速排序、堆排序、.radix 排序和基数排序。 一、分类 内部排序和外部排序是两种基本的排序分类。内部排序是指待排序记录存放在计算机随机...

    数据结构与算法分析——Java语言描述-带书签目录高清扫描版

    排序算法如冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序,各有优缺点,适用于不同的数据特性。查找算法包括顺序查找、二分查找和哈希查找,其中哈希表提供了近乎常数时间的查找效率。此外,高级算法如...

    排序算法-基于Java实现的排序算法之BubbleSort实现.zip

    本项目聚焦于一种基础且经典的排序算法——冒泡排序(Bubble Sort),并以Java编程语言作为实现工具。Java是一种广泛使用的面向对象的编程语言,其简洁的语法和丰富的库函数使得实现各种算法变得方便。 冒泡排序是...

    Java经典算法50题——答案下载!

    1. 排序算法:包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等,理解每种排序算法的工作原理和时间复杂度是至关重要的。 2. 搜索算法:线性搜索、二分搜索、深度优先搜索(DFS)、广度优先搜索...

    java实现的4种排序算法(冒泡、快速、插入、选择)

    以下是根据标题和描述中提到的四种排序算法——冒泡排序、快速排序、插入排序和选择排序的详细说明。 **冒泡排序(BuddleSort)**: 冒泡排序是一种简单的交换排序,它通过重复遍历待排序的列表,比较相邻元素并...

    数据结构与算法答案——java语言描述

    5. **排序算法**:包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等。Java的`Collections.sort()`方法使用了高效的排序算法,如TimSort,了解这些算法的原理有助于编写高性能的代码。 6. **图与树*...

    《Java数据结构和算法》学习笔记(2)——4种简单排序算法

    这些算法虽然在复杂度上不如高级排序算法如快速排序或归并排序,但它们提供了基础的排序逻辑,有助于理解更复杂的算法思想。 首先,我们来详细讲解插入排序(Insertion Sort)。插入排序的工作原理类似于我们手动...

    java代码-使用java解决java排序之-快速排序的问题的源代码

    java代码-使用java解决java排序之-快速排序的问题的源代码 ——学习参考资料:仅用于个人学习使用!

Global site tag (gtag.js) - Google Analytics