package com.pskfire.example;
// quickSort1.java
// demonstrates simple version of quick sort
// to run this program: C>java QuickSort1App
////////////////////////////////////////////////////////////////
class ArrayIns {
private long[] theArray; // ref to array theArray
private int nElems; // number of data items
// --------------------------------------------------------------
public ArrayIns(int max) // constructor
{
theArray = new long[max]; // create the array
nElems = 0; // no items yet
}
// --------------------------------------------------------------
public void insert(long value) // put element into array
{
theArray[nElems] = value; // insert it
nElems++; // increment size
}
// --------------------------------------------------------------
public void display() // displays array contents
{
System.out.print("A=");
for (int j = 0; j < nElems; j++)
// for each element,
System.out.print(theArray[j] + " "); // display it
System.out.println("");
}
// --------------------------------------------------------------
public void quickSort() {
recQuickSort(0, nElems - 1);
}
// --------------------------------------------------------------
public void recQuickSort(int left, int right) {
if (right - left <= 0) // if size <= 1,
return; // already sorted
else // size is 2 or larger
{
long pivot = theArray[right]; // rightmost item
// partition range
int partition = partitionIt(left, right, pivot);
recQuickSort(left, partition - 1); // sort left side
recQuickSort(partition + 1, right); // sort right side
}
} // end recQuickSort()
// --------------------------------------------------------------
public int partitionIt(int left, int right, long pivot) {
int leftPtr = left - 1; // left (after ++)
int rightPtr = right; // right-1 (after --)
while (true) { // find bigger item
while (theArray[++leftPtr] < pivot)
; // (nop)
// find smaller item
while (rightPtr > 0 && theArray[--rightPtr] > pivot)
; // (nop)
if (leftPtr >= rightPtr) // if pointers cross,
break; // partition done
else
// not crossed, so
swap(leftPtr, rightPtr); // swap elements
} // end while(true)
swap(leftPtr, right); // restore pivot
return leftPtr; // return pivot location
} // end partitionIt()
// --------------------------------------------------------------
public void swap(int dex1, int dex2) // swap two elements
{
long temp = theArray[dex1]; // A into temp
theArray[dex1] = theArray[dex2]; // B into A
theArray[dex2] = temp; // temp into B
} // end swap(
// --------------------------------------------------------------
} // end class ArrayIns
// //////////////////////////////////////////////////////////////
class QuickSort1App {
public static void main(String[] args) {
int maxSize = 16; // array size
ArrayIns arr;
arr = new ArrayIns(maxSize); // create array
for (int j = 0; j < maxSize; j++) // fill array with
{ // random numbers
long n = (int) (java.lang.Math.random() * 99);
arr.insert(n);
}
arr.display(); // display items
arr.quickSort(); // quicksort them
arr.display(); // display them again
} // end main()
} // end class QuickSort1App
// //////////////////////////////////////////////////////////////
分享到:
相关推荐
快速排序快速排序 快速排序 快速排序 快速排序 快速排序
快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序...
void quicksort(int a[], int p, int r) { if(p){ int q = partition(a,p,r); quicksort(a,p,q-1); quicksort(a,q+1,r); } }
快速排序是一种高效的排序算法,由英国计算机科学家查尔斯·安东尼·理查德·霍尔(Sir Charles Antony Richard Hoare)在1960年发明。霍尔因其对计算机科学的贡献,尤其是快速排序算法,而被广泛认可。快速排序的...
JavaScript快速排序递归与非递归实现快速排序概述快速排序(Quiksort)是一种通过基准划分区块并不断交换左右项的排序方式,其采用了分治法,减少了交换
快速排序,比较高效的排序算法之一。这是一个例子,一个关于快速排序的例子。
1、熟悉快速排序的串行算法 2、熟悉快速排序的并行算法 3、实现快速排序的并行算法 3.2 实验环境及软件 单台或联网的多台PC机,Linux操作系统,MPI系统。 3.3实验内容 1、快速排序的基本思想 2、单处理机上快速...
实际上,随机化快速排序得到理论最坏情况的可能性仅为 1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到 O(nlogn)的期望时间复杂度。 用栈模拟递归的快速排序是另一种优化版本。快速排序的实现需要消耗...
快速排序源码 快速排序源码快速排序源码 快速排序源码快速排序源码 快速排序源码快速排序源码 快速排序源码快速排序源码 快速排序源码
冒泡排序和快速排序的时间性能 冒泡排序和快速排序是两种常用的排序算法,它们的时间性能是开发者和研究人员所关心的热点话题。在本文中,我们将对冒泡排序和快速排序的时间性能进行深入分析和比较。 冒泡排序是一...
快速排序是一种基于比较的排序算法,它的基本思想是选择一个中心元素,将小于中心点的元素移动至中心点之前,大于中心点的元素移动至中心点之后,然后对上步分成的两个无序数组段重复这个过程直到段长为1。...
C语言实现多种链表快速排序
(1)用随机快速排序的方法,对输入的数值以从大到小的顺序进行快速排序。 (2)对随机快速排序和冒泡排序这两种排序方法进行比较,测试其在不同数值大小的情况下算法运行的时间复杂度。 二、 实验要求 快速排序...
"快速排序算法java代码" 快速排序算法是由Tony Hoare在1960年提出的一种排序算法,它的平均时间复杂度为O(n log n),是目前最快的排序算法之一。下面我们将详细地讲解快速排序算法的java代码实现。 快速排序算法的...
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
快速排序的并行实现,提高效率。快速排序算法并行化的一个简单思想是,对每次划分过后所得到的两个序列分别使用两个处理器完成递归排序。
快速排序、归并排序、基数排序等排序算法比较,比较时间性能,采用C++语言实现。。。
JAVA实现快速排序 快速排序是一种高效的排序算法,它的实现可以分为两个部分:基本思想和复杂度分析。在基本思想中,快速排序采用“分而治之”的思想,把大的拆分为小的,小的拆分为更小的,直到序列中的所有记录均...
快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法(Divide and Conquer)。在这个C++代码示例中,快速排序的实现被清晰地展示出来。下面将详细解释代码中的关键...
快速排序function quickSort(low, high, arr) {