1)快速排序的基本思想:
设当前待排序的无序区为R[low......high],在R[low......high]中任选一个记录作为基准(Pivot),以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high],并使左边子区间中所有记录的关键字均不大于基准,右边的子区间中所有记录的关键字均不小于基准。基准记录不参与下次排序,它已经处于排好位pivotpos。下次递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。
2)具体代码:
[code]
package com.amplesky;
public class QuickSort
{
public static void main(String[] args)
{
int [] a = {5,6,7,65,3,4,2,6,4,5};
int low = 0;
int heigh = a.length -1;
quickSort(a,low,heigh);
for (int i =0; i <= heigh ;i++)
{
System.out.print(a[i]+" ");
}
System.out.println();
}
public static void quickSort(int a[], int low,int heigh)
{
if( low >= heigh)
{
return ;
}
int index = partion(a, low, heigh);
quickSort(a,low, index -1);
quickSort(a,index+1, heigh);
}
public static int partion(int a[], int low,int heigh)
{
int swap = a[low];
while(low < heigh)
{
while(low < heigh && a[heigh] >= swap)
{
heigh -- ;
}
if(low < heigh)
{
a[low++] = a[heigh];
}
while(low < heigh && a[low] <= swap)
{
low ++ ;
}
if(low < heigh)
{
a[heigh--] = a[low];
}
}
a[low]= swap;
return low;
}
}
[/code]
分享到:
相关推荐
选择排序 冒泡排序 插入排序 合并排序 快速排序算法原理及代码实现 不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 当面临巨大数据量的排序的时候,还是优先选择合并排序算法和快速排序算法。...
对本章的各种排序方法(直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序和归并排序)的时间性能进行比较。 2、 基本要求 (1)设计并实现上述各种排序算法; (2)对正序和逆序的初始...
1.内部排序:使用8种内部排序算法(冒泡排序、插入排序、选择排序、希尔排序、快速排序、归并排序、基数排序、堆排序),对出版社信息按照指定关键字进行排序,分析其时空复杂度(在实验报告的总结与思考中会有相应...
本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。本书还介绍了对强连通...
7.3 快速排序的随机化版本 7.4 快速排序分析 7.4.1 最坏情况分析 7.4.2 期望运行时间 思考题 本章注记 第8章 线性时间排序 8.1 排序算法的下界 8.2 计数排序 8.3 基数排序 8.4 桶排序 ...
贯穿全书的主体是如何思考、设计、开发的方法,而具体的编程语言,只是提供了一个具体场景方便介绍的媒介。 全书共21章,详细介绍Python语言编程的方方面面。本书从基本的编程概念开始讲起,包括语言的语法和语义,...
该项目包括数据结构、算法示例编码,如列表、堆栈、队列、快速排序等...... 通过在 Leetcode 判断上编码,我开始思考编程的意义是什么,什么是时间复杂度以及如何估计它。 继续努力吧。 熊去吧!!! 总结如何解决...
通过分析经典中值滤波算法以及几种改进的快速算法,提出了2种新的快速算法并进行了详细地介绍,即不需要排序的基于统计法的中值滤波算法和只需要少量数据排序的基于分治法的中值滤波算法。实验结果表明,提出的基于分治...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
书中专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。此书还介绍了对强连通...
书中专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。此书还介绍了对强连通...
本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。本书还介绍了对强连通...
本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。本书还介绍了对强连通...
本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。本书还介绍了对强连通...
本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。本书还介绍了对强连通...
本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。本书还介绍了对强连通...
本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。本书还介绍了对强连通...