我检查了K&R书中的快速排序代码,2小时后我仍然不能理解第一个交换(swap(a, left, (left+right)/2);)实现了什么。我试着删除它,但排序仍然有效。有人能解释一下吗?这是一个性能问题吗?如果是这样,为什么呢?这个动作在我看来似乎是随机的(也就是说,在一些数字组上,它将提高性能,而在一些数字上则不会)。
谢谢。
void qsort(int a[], int left, int right)
{
int i, last;
if (left >= right)
return;
swap(a, left, (left+
谁能解释一下我在“C编程语言”一书中找到的这段代码。它在4.10 -递归一节中。
// swap: interchange v[i] and v[j]
void swap(int v[], int i, int j) {
int temp;
temp = v[i];
v[i] = v[j];
v[j] = temp;
}
// qsort: sort v[left]...v[right] into increasing order
void qsort(int v[], int left, int right) {
int i, last;
我试图更好地理解约简,目前我正在研究两种算法,“中间值”和“快速排序”。
我了解到,这两种算法都使用类似(实际上完全相同)的分区子程序来帮助解决它们的问题,这最终使它们非常相似。
Select(A[1...n],k): // Pseudocode for median of medians
m = [n/5]
for i from 1 to m:
B[i] = Select(A[5i-4..5i],3)
mom = Select(B[1..m],m/2)
r = partition(A[1..n],mom) // THIS IS THE SUBROUTINE
我发现很难理解下面的代码片段。我理解所显示的指向函数风格的指针,但我发现混淆之处在于所指示的行。
void qsort(void **v, int left, int right, int (*comp) (void *, void *))
{
int i, last;
void swap(int **v, int i, int j);
if (left >= right) /* do nothing if array contains */
return; /* fewer than two elements */
我正在努力实现快速排序。看起来很简单,实现一个枢轴函数,以便将较小的元素和较大的元素聚集在两个单独的列表中。递归地这样做,直到列表足够小,可以在恒定的时间内排序。
def pivot(a, pivot_index):
# I guess you can keep two indexes one greater and one lesser and swap.
i, j = 0, len(a)-2
p = a[pivot_index]
a[pivot_index] = a[len(a)-1]
a[len(a)-1] = p
while(i<
我正在为一个班级做一个项目。我们将编写一个快速排序,它在指定的值处转换为插入排序。这没有问题,我现在遇到的困难是弄清楚为什么我没有得到我期望的表现。
其中一个要求是它必须在1300ms内对一个包含500000个it的数组进行排序(这是在标准机器上的,所以CPU速度不是问题)。首先,我不能让它在5,000,000上工作,因为堆栈溢出错误(太多的递归调用...)。如果我增加堆的大小,我仍然会变得比这慢得多。
下面是代码。有谁能给我提示吗?
提前感谢
public class MyQuickSort {
public static void sort(int [] toSort, int
**我需要创建一个快速排序算法,但这样它就只使用一个列表并在其中进行交换。我设法使它“排序”或定位第一个元素,但现在我不知道如何实现递归。我面临的最大问题是如何递归地处理列表中的某个部分,而不是创建新的列表。这是我的代码:-------------------------------------------------------------------------------** 新代码,同样的问题。
这是我的密码。它能完成任务,但却被困在循环中。
def qsort(n,l,g):
if l is None:
l=0
if g is None:
g=len(n)
if g-
根据许多网站上给出的伪代码,我写了这个Hoare分区算法,它接受一个数组,根据给定的轴心对要分区的子数组的开始和结束索引进行分区。它工作得很好,但有人能解释一下它的逻辑,它是如何做到的吗?下面是代码:
def hoare(arr,start,end):
pivot = 4
i,j = start,end
while i < j:
while i < j and arr[i] <= pivot:
i += 1
while j >= i and arr[j] > pivot:
我正在尝试使用递归和几种辅助方法来实现quickSort。当我运行程序时,我得到一条越界消息,告诉我我已经转向数组的index -1。有没有人能提供关于修复我的quickSort方法的建议?(这就是问题所在)。我知道我的其他方法是正确的。
示例{7,6,5,4,3,2,1}
结果应该是{1,2,3,4,5,6,7}
public static <T extends Comparable<? super T>> void quickSort(T[] a) {
quickSort(a,0,a.length - 1);
}
public st
我一直在尝试实现Hoare分区方法,但我和计算机似乎都不能理解它,因为它是在科尔曼和维基百科中编写的。这两个源代码中的算法看起来如下所示:
algorithm partition(A, lo, hi) is
pivot := A[lo]
i := lo - 1
j := hi + 1
loop forever
do
j := j - 1
while A[j] > pivot
do
i := i + 1
while A[i] < pivot
我实现了以下代码,但它似乎不适用于我的数组具有重复值的情况。
private int partition(Integer[] arr,int left, int right)
{
int i = left;
int j = right;
int pivot = arr[left];
while(true)
{
while(arr[i] <pivot) i++;
while(arr[j] > pivot) j--;
if(i < j)
{
p
我有一项任务要用Java编写快速排序(仅用正位数)算法(除了Scanner之外,我不能使用任何导入),但是没有递归和堆栈。
我对此有两个问题:
我确实使用堆栈和递归版本来支持和迭代快速排序,但是我无法想象没有它如何完成它。我听说过一些“就位”的实现,但我并没有真正理解它--它能解决我的问题吗?
如果有人能告诉我做这件事的方法,我会很感激(如果可以的话,不要发布实现,我只是想了解一下,它不会复制别人的代码)或者推荐一些我可以找到的书(或者类似的问题)。
通过插入一些小数组来实现排序是个好主意吗?如果是这样的话,N在这个代码中应该有多大:
if (arraySize < N) ins
我已经实现了一个有效的quickSort算法,使用数组中的第一个元素作为枢轴,如下所示:
public int[] quickSort( int[] a, int start, int end){
int l = start;
int r = end;
int pivotIndex = start; //<---- first element in the array as pivot!
// must be at least two elements
if ( end - start >= 1){
// set p
我正在尝试实现以第一个元素为中心的快速排序划分算法,我研究了以最后一个元素为中心的快速排序算法。有人能告诉我在下面的伪代码中我哪里错了吗?
/* Taking first element of array as pivot and movig all elements
smaller than pivot left to pivot and greater tto its right */
// L is leftmost index, R is rightmost index
Partition(A[],L,R)
{
pivot = A[L]
i = L-1
这是我在实现快速排序算法时遇到的代码。你能在这里解释一下递归是如何工作的吗?
void quickSort(int arr[], int left, int right)
{
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
/* partition */
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
有人能告诉我我的代码有什么问题吗?
int Partition(vector<string>& userIDs, int i, int k) {
int pivot = (i + (k - i) / 2);
string temp;
while(i<k) {
cout << "pivot:" << pivot << endl;
while (userIDs.at(i).compare(userIDs.at(pivot))<0) {
我知道有几个类似的帖子,但没有一个答案是令人满意的,这就是为什么我想再次问这个问题。
考虑下面的代码。这是我根据CRLS算法介绍实现的快速排序
int partition(int* a, int s, int e)
{
int pivot = a[e];
int q = s-1;
for (int i = s; i <= e; i++)
{
if (a[i] <= pivot) {
q++;
int tmp = a[q];
a[q] = a[i];
当我对一些有许多重复元素的数据进行排序时,快速排序算法是inefficient.Can --有人解释了吗?
这是我的快速排序代码:
int partition(int arr[],int low,int high)
{
int i = low + 1;
int j = high;
int tmp = arr[low];
while(1)
{
while(j != low && arr[j] > tmp) --j; //from right to left
while(i != high &
大家好,我试过这个快速排序程序的逻辑。但我需要将此代码转换为设置间隔模式,并需要一步一步地涵盖整个过程。请帮助我将此逻辑改进为setinterval程序。我认为目前它处于递归模式。
function quicksort(arr)
{
if (arr.length == 0)
return [];
var left = new Array();
var right = new Array();
var pivot = arr[0];
for (var i = 1; i < arr.length; i++) {
if
我正在快速地工作,但出于某种原因,我最终还是遇到了同样的问题。不知何故,即使我复制/粘贴应该工作的快速排序代码,我也总是在数组中的某个位置得到一个0的值。
public class quicksort {
public int[] x;
public quicksort(int a[]){
x=a;
procedure(0, x.length-1);
}
public void procedure(int left, int right){
int index=left;
int smaller=left+1;//going to sort everything
我正在尝试实现快速排序算法(在C#中),下面是我的代码:
public static void sort(ref int[] A)
{
if (A.Length==0 || A.Length==1)
{
return;
}
quickSort(ref A,0,A.Length-1);
}
private static void quickSort(ref int[] A, int left, int right)
{
if (left >= right || left < 0 || right < 0)
我正在上大学,试图学习如何使用快速排序。我打算在几周内制作一个程序,但首先我要试着了解它是如何工作的。我发现了一个家庭作业的问题,看起来它可以帮助我理解。唯一的问题是,在看了维基百科和其他几个网站后,我感到困惑和绝望。
Apply quicksort to the sequence A = {*6,*4,*3,*9,*4,*7,*5}。不是使用三个元素的中位数,而是使用第一个元素。(这篇文章介绍了最坏情况下性能的最大风险,但它使得手动解决问题变得更容易。)如下所示,展示你的主要工作。当一个元素变得重要时,只需在它周围放置一个方块。然后,稍后。它通过给元素加下划线来表示它是/曾经是一个支点。它使
我对Java很陌生,我正在尝试实现QuickSort。下面是我的剧本。
public class QuickSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[] ={5,6,7,4,1,3};
QuickSort qs = new QuickSort();
qs.quickSort(a,0,a.length-1);
for(int i=0;i<a.length;i++) {
我有两天时间试图弄清楚为什么我的快速排序函数返回除两个元素之外的所有按正确顺序排序的元素。
用输入
quicksort([0,7,3,11,23,87,999,1023,12,713,5,6,9])
输出
[0, 6, 3, 5, 7, 9, 11, 12, 23, 87, 713, 999, 1023]
你认为这个功能有什么问题?
def quicksort(array):
#Base case
if len(array) <= 1:
return array
#Choose pivot always at the left part and p
我需要编写函数(快速排序pred lst) lst是要排序的数字列表pred是对列表进行排序的谓词,该谓词的签名是:(lambda (x )…)
- (quick-sort < lst) will sort ascending (small to large)
- (quick-sort > lst) will sort descending (large to small)
- (quick-sort (lambda (x y) (< (car x) (car y))) lst) will sort a list
with inner lists according to