package com.quicksort;
public class QuickSort {
public int partiTion(int[] a, int start, int end){
int i = start - 1;//小于数组中最后一个数的索引值
int x = a[end];
for(int j = start;j<=end - 1;j++){//将数组分为大于最后一个值部分和小于最后一个值的部分
if(a[j]<=x){
i = i+1;
int tmp = a[j];
a[j] = a[i];
a[i] = tmp;
}
}
//将数组中最靠前的大于最后一个数的数和数组中最后一个数交换,保证交换后的数组是这样一种情形:a[x<=i]<a[i+1]<a[i+2<=x]
int tmp = a[i+1];
a[i+1] = a[end];
a[end] = tmp;
return i+1;
}
public void quickSort(int[] a, int start, int end){
if(start>end){
return;
}
int q = this.partiTion(a, start, end);//在原数组的基础上将数组分为大于某值和小于某值的两堆
quickSort(a, start, q - 1);//对选定值左边的值递归快排
quickSort(a, q + 1, end);//对选定值右边的值递归快拍
}
public static void main(String[] args) {
int[] a = new int[]{0,5,6,7,3,2};
QuickSort quickSort = new QuickSort();
quickSort.quickSort(a, 1, a.length-1);
for(Integer i : a){
System.out.println(i);
}
}
}
分享到:
相关推荐
数据结构与算法 - 快速排序算法实现报告 在数据结构与算法的学习过程中,快速排序算法是一种重要的排序算法,它具有排序速度快、就地排序的优点,但也具有不稳定性。以下是快速排序算法的详细实现报告。 快速排序...
算法设计,快速排序的C++实现代码,并测试运行时间
经典排序算法 - 快速排序Quick sort 经典排序算法 - 桶排序Bucket sort 经典排序算法 - 插入排序Insertion sort 经典排序算法 - 基数排序Radix sort 经典排序算法 - 鸽巢排序Pigeonhole sort 经典排序算法 - ...
将杂乱无章的数据元素,通过一定的方法按关键字顺序排列的过程叫做排序。...本资源通过matlab实现合并排序、简单选择排序、快速排序、冒泡排序、直接插入排序5种常用的排序算法,并部分绘制代表算法原理的动图。
快速排序算法的实现可以分为以下几个步骤: 1. 选择pivot元素:选择数组中的一个元素作为pivot,可以随机选择或选择数组的中间元素。 2. 分区:将数组分成两个部分:左侧元素都小于pivot,右侧元素都大于pivot。 3....
快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法(Divide and Conquer),将一个大问题分解为小问题来解决,最终合并小问题的结果得到原问题的解。在数据结构中,...
本篇文章主要探讨了如何在VC++环境中利用多线程技术来实现三种经典的排序算法:冒泡排序、快速排序和归并排序,并对它们的性能进行了比较。 首先,冒泡排序是一种简单的排序算法,它重复地遍历待排序的数列,一次...
在实际编程实现快速排序时,需要注意以下几点: - **避免最坏情况**:可以通过随机化主元的选择来避免数组已排序或接近排序导致的最坏情况。 - **优化小规模数据**:对于小规模数据,快速排序的递归开销可能会超过...
在给出的"Lab 1"文件中,可能包含了实现快速排序的代码,包括普通快速排序和随机快速排序的版本,以及统计两种排序算法运行时间的代码。通过分析和运行这些代码,你可以更深入地理解快速排序的工作原理和性能特性。
本实验旨在通过对两种经典排序算法——快速排序和归并排序的研究与实现,深入理解它们的基本原理、时间复杂度,并通过编程实践比较这两种算法在不同数据规模下的性能表现。 #### 二、快速排序 **1. 基本思想** ...
本篇文章将详细讨论几种常见的排序算法:选择排序、冒泡排序、插入排序、合并排序以及快速排序,分析它们的算法原理、时间效率,并通过经验分析验证理论分析的准确性。 **1. 选择排序(Selection Sort)** 选择排序...
快速排序算法的实现思路可以分为两个步骤: 1. 选择一个基准元素(pivot),将数组分成两个子数组,一部分记录的关键字小于基准元素,一部分记录的关键字大于基准元素。 2. 对这两个子数组递归地应用快速排序算法,...
**希尔排序、快速排序与归并排序:NlogN经典排序算法详解** 排序算法是计算机科学中的基础且重要的一部分,尤其是在处理大量数据时,高效排序能够显著提升程序性能。本资料包聚焦于三类时间复杂度为O(nlogn)的经典...
在FPGA上实现快速排序,我们可以利用其并行处理能力。通过将数据分块并在多个处理单元中同时进行排序,大大提高了排序速度。这里的“只需两个时钟即可输出12个数据的排序结果”表明该设计实现了高度并行化的快速排序...
本主题将详细探讨四种常见的排序算法:选择排序、插入排序、快速排序以及冒泡排序,它们都是用C语言实现的。以下是这些排序算法的详细解析: 1. **选择排序(Selection Sort)** - 选择排序是一种简单直观的排序...
在数据结构课程设计中,实现快速排序不仅要求理解和应用算法,还涉及到编程技巧和界面设计。 一、设计思想与流程图 快速排序的设计思想可以总结为以下步骤: 1. 选择一个基准元素(pivot)。 2. 将数组分为两部分:...
本书第三部分专注于介绍各种排序算法,包括冒泡排序、插入排序、选择排序、快速排序、归并排序和堆排序等。作者不仅分析了每种排序算法的原理,还比较了它们的效率和适用场景,帮助程序员在实际编程中作出恰当的选择...
高级排序算法如快速排序、归并排序等,它们的时间复杂度通常优于O(n^2),其中快速排序平均情况下的时间复杂度为O(n log n),在最坏情况下也能保持在O(n^2)。而归并排序则始终稳定在O(n log n)。 除了这些常见的排序...
快速排序:分别使用Java和Python实现快速排序算法.zip 快速排序:分别使用Java和Python实现快速排序算法.zip 快速排序:分别使用Java和Python实现快速排序算法.zip 快速排序:分别使用Java和Python实现快速排序算法....