它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。(来自百度百科)
实现程序:
/**
* 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
分享到:
相关推荐
在这个"代码包_分治法快速排序法示例_"中,我们将深入探讨快速排序的工作原理、实现过程以及它在实际编程中的应用。 快速排序的基本步骤如下: 1. **选择基准元素**:首先,我们需要在待排序的数组中选择一个基准...
快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它基于分治法(Divide and Conquer)的思想,是计算机科学中最为广泛使用的排序算法之一。分治法的基本策略是将一个复杂的问题分解成两...
在这个场景中,我们主要关注的是如何运用分治法实现快速排序。 快速排序的基本步骤如下: 1. **选择枢轴**:从待排序的数组中选取一个元素作为“枢轴”(pivot)。这个元素将作为划分的标准,使得数组被分成两部分...
它的主要思想是分治法,即将大问题分解为小问题来解决。在快速排序中,我们选择一个基准值(pivot),然后将数组分为两部分:一部分包含所有小于基准的元素,另一部分包含所有大于或等于基准的元素。这个过程通过...
快速排序(QuickSort)是一种基于分治法的排序算法,由C.A.R. Hoare在1962年提出。该算法的基本思想是选择一个ivot元素,将数组分成两个部分,然后递归地对这两个部分进行排序。快速排序算法的时间复杂度平均情况下...
其中,归并排序和快速排序就是基于分治法的典型应用。 **分治法的三步走** 1. **分解**:将原问题分解为多个规模较小但结构相同的子问题。例如,在排序问题中,我们可以将数组分为两半。 2. **解决**:递归地解决...
它基于分治法的思想,将一个大问题分解成若干小问题来解决。在这个场景中,我们讨论的是如何使用分治法的思想来实现插入排序,并通过C++语言进行编程实践。 ### 分治法原理 分治法是计算机科学中解决问题的一种策略...
分治法在排序领域的典型应用是快速排序(Quick Sort),这是一种效率极高的排序算法,由C.A.R. Hoare在1960年提出。快速排序的基本思想是通过选取一个基准值(pivot)将数组划分为两个子数组,使得一个子数组中的...
快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的核心思想是分治法(Divide and Conquer),即将一个大问题分解为两个或更多的小问题来解决。分治法通常包括三个步骤:分解、解决和...
使用快速排序算法实现对n个元素进行排序。 由文件input.txt提供输入数据,输出到文件output.txt中。
归并排序也是基于分治法的排序算法,但与快速排序不同的是,它不是通过交换元素来实现排序,而是通过合并已排序的子数组来达到目的。归并排序的过程如下: 1. **分割**:将原始数组分为两个或更多个子数组,每个子...
分治法是一种重要的计算机科学算法,它将一个大问题分解为若干个规模较小的相同或相似的子问题,然后递归地解决这些子问题,最后将子问题的解合并成原问题的解。这种策略有助于简化问题处理,提高效率,并在某些情况...
快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的核心思想是分治法(Divide and Conquer),即将一个大问题分解为两个或更多的小问题来解决。分治法通常包括三个步骤:分解、解决和...
用分治算法的思想,加上递归 实现快速排序
分治法是一种解决问题的方法,它将一个大问题分解成两个或更多的相同或相似的小问题,直到最后小问题可以简单的直接求解,原问题的解即小问题的解的合并。快速排序正是应用了这一策略,通过选取一个基准数,将待排序...
这个代码是利用快速排序算法,求第K大的数。 快速排序由C. A. R. Hoare在1960年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后...
在快速排序中,分治法的具体步骤如下: 1. **选择基准**:从数组中选取一个元素作为基准,可以选择第一个、最后一个或随机元素。 2. **分区操作**:重新排列数组,使得所有小于基准的元素位于其左侧,所有大于等于...
分治算法实验(用分治法实现快速排序算法) 本实验的目的是通过分治算法实现快速排序算法,掌握分治算法的问题描述、算法设计思想、程序设计。实验中,我们将学习如何使用分治法来实现快速排序算法,并对其性能进行...
内容概要:本文详细解析了快速排序算法的实现原理,重点介绍了分治法的核心逻辑和递归实现的关键点。主要内容包括快速排序的基本原理、选择基准值、分区操作以及递归排序子数组的步骤。文中提供了具体的Python实现...