它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。(来自百度百科)
实现程序:
/**
* Copyright (c) 2011 Trusted Software and Mobile Computing(TSMC)
* All rights reserved.
* Author: Jarg Yee <yeshaoting@gmail.com>
* http://jarg.iteye.com/
*/
import static java.lang.System.out;
/*
* 交换排序: 1. 冒泡排序 2. 快速排序
* 实现快速排序
*/
public class QSort
{
/* 待排序元素 */
private static int[] a = {3,1,3,2,9,8,1,2,4};
private static int[] b = a.clone(); // 拷贝一份a中数据到b
/* for debugging. */
public static void main(String[] args)
{
qSort(0,a.length-1); // 排序
display(); // 显示排序结果
}
/* 快速排序 */
public static void qSort(int beginIndex,int endIndex)
{
if(beginIndex<endIndex)
{
int q = partition(beginIndex,endIndex); // 分割点索引值
qSort(beginIndex,q-1); // 分治,对分割点q左半边快速排序
qSort(q+1,endIndex); // 分治,对分割点q右半边快速排序
}
}
/*
划分,从而分治
找出分割点索引值
*/
public static int partition(int beginIndex,int endIndex)
{
int x = a[beginIndex]; // 以当前待排序元素中第一个点为基准.
/*
设置二个索引,分别指向当前待排序元素头和尾
*/
int i = beginIndex,j = endIndex;
while(i<j)
{
if(a[i]<=a[j])
{
// 大于基准的元素
/* 修改索引位置 */
// 指向基准点的索引不变
// 另一个索引变化,向指向基准点的索引指向位置靠近
if(a[i] == x)
j--;
else
i++;
}
else
{
// 交换,小于基准的元素与基准交换位置
int temp = a[i];
a[i] = a[j];
a[j] = temp;
/* 修改索引位置 */
if(a[i] == x)
j--;
else
i++;
}
}
return j; // 此时i=j,返回i或者j都可以
}
/* 输出待排序元素 */
public static void display()
{
out.print("排序前:");
for(int value : b)
{
out.print("\t" + value);
}
out.println("\n-------------------------------------------");
out.print("排序后:");
for(int value : a)
{
out.print("\t" + value);
}
}
}
- 大小: 6.8 KB
分享到:
相关推荐
c语言分治法快速排序源码
分治法的另外一种排序算法,快速排序。有注释,便于阅读,因为交换时使用的引用,暂时归为C++,C语言版稍后奉上。
分治法的应用,快速排序是其中一种。注释便于读者明白。
java 快速排序 折半查找的界面实现 (递归与分治法)
实现并验证合并排序算法; 实现并验证快速排序算法(参考习题5.2第7a题,P140); 用递归与分治的方法设计并实现寻找第k小元素算法
核心思想将数组中所有元素都跟一个基准元素x比(随意选取,常取第一个或最后一个),比x小的划分成左边一块,比x大的划分成右边一块,得到两个子问题。然后递归处理这两个子问题即可。其关键在于对数组的划分。
经典的快速排序算法,使用分治法思想,使用C++的插入排序,使用算法课程的基础编程。
利用分治法实现快速排序,这是一个示例程序,可轻易改成模板
使用快速排序算法实现对n个元素进行排序。 由文件input.txt提供输入数据,输出到文件output.txt中。
用分治算法的思想,加上递归 实现快速排序
本资源包括一份分治法算法分析文档,4份Java源程序,包括二分查找、归并排序、快速排序、比赛日程安排。
这个代码是利用快速排序算法,求第K大的数。 快速排序由C. A. R. Hoare在1960年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后...
算法分析第二单元员 分治法的学习 中的经典问题3 也叫做归并排序
快速排序,使用分治算法,绝对AC,使用C++算法,没有使用sort,时间复杂度O(n logn)
基于蛮力法(选择排序、冒泡排序)、减治法(插入排序)和分治法(合并排序、快速排序)的思想分别编写一个排序算法。 【选择排序函数原型及功能说明】 选择排序开始的时候,我们扫描整个列表,找到它的最小元素,...
以最小的时空复杂度解决问题,配有详细的注释,代码可读性强
课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的
算法设计与分析实验报告,附已通过源码,供学习参考,共勉♪ 目录摘要如下: 1.问题描述 2.实验目的 3.实验原理 4.实验设计 ...(包括输入格式、算法、输出格式) ...(除了截图外,实验结果还用图表进行了分析) ...
将两个及其以上的有序表合并为一张有序表,把待排序序列通过分治法分为若干个有序子序列,然后每两个子序列合并为一个子序列,经过多次合并后整合为一张有序表。 排序过程如图: 代码如下: #include stdio.h #...
分治法排序 归并排序与二分查找 算法课课件