修改此QuickSort以始终将最后一个元素用作枢轴
https://stackoverflow.com/questions/2316756
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我有以下 QuickSort 总是选择子序列的第一个元素作为其枢轴：
void qqsort(int array[], int start, int end) {
int i = start; // index of left-to-right scan
int k = end; // index of right-to-left scan
if (end - start >= 1) { // check that there are at least two elements to sort
int pivot = array[start]; // set the pivot as the first element in the partition
while (k > i) { // while the scan indices from left and right have not met,
while (array[i] <= pivot && i <= end && k > i) // from the left, look for the first element greater than the pivot
i++;
while (array[k] > pivot && k >= start && k >= i) // from the right, look for the first element not greater than the pivot
k--;
if (k > i) // if the left seekindex is still smaller than the right index, swap the corresponding elements
swap(array, i, k);
}
swap(array, start, k); // after the indices have crossed, swap the last element in the left partition with the pivot
qqsort(array, start, k - 1); // quicksort the left partition
qqsort(array, k + 1, end); // quicksort the right partition
} else { // if there is only one element in the partition, do not do any sorting
return;
}
}
现在，如您所见，此算法总是将第一个元素作为枢轴： int pivot = array[start];
我想修改此算法以使其始终使用最后一个元素，而不是子序列的第一个元素，因为我想分析两个实现的物理运行时间。
我尝试更改行 int pivot = array[start]; 至 int pivot = array[end]; 但是该算法随后输出了一个未分类的序列：
//Changes: int pivot = array[end];
unsorted: {5 4 3 2 1}
*sorted*: {1 2 5 4 3}
为了测试另一个枢轴，我还尝试使用子序列的中心元素，但该算法仍然失败：
//Changes: int pivot = array[(start + end) / 2];
unsorted: {5 3 4 2 1}
*sorted*: {3 2 4 1 5}
有人可以帮助我正确理解该算法，并告诉我成功实现此实现需要做出什么更改，总是选择该子序列的最后一个元素作为枢轴？
解决方案
问题的原因
问题是您使用 int k = end;. 。很好使用 int i = start; 当您将枢轴元素作为数组中的第一个元素时，因为您在循环中的检查会掠过它（array[i] <= pivot）。但是，当您将最后一个元素用作枢轴时，k在端索引上停止，并将枢轴切换到分区左半部分的位置。您已经遇到麻烦了，因为您的枢轴很可能在左分区内而不是边界内的某个地方。
解决方案
要解决此问题，您需要设置 int k = end - 1; 当您将最右边的元素用作枢轴时。您还需要更改将枢轴交换到左右分区之间边框的行：
swap(array, i, end);
qqsort(array, start, i - 1);
qqsort(array, i + 1, end);
您必须使用I来使用I，因为我最终将位于右分区的最左边元素（然后可以将枢轴换成最右边的元素，并且将保留订单）。最后，你想改变 k >= i 至 k > i 在降低k或否则的同时，数组[-1]索引误差的变化很小。这是不可能发生的，因为到目前为止，我至少总是等于I+1。
那应该做到。
边注：
这是一部写得不好的Quicksort，我不建议您从中学习。它具有一些无关的，不必要的比较以及我不会浪费时间上市的其他一些错误。我建议在 这个演示文稿 Sedgewick和Bentley。
其他提示
我没有测试，但是还是检查它：
这个
// after the indices have crossed,
// swap the last element in the left partition with the pivot
swap(array, start, k);
可能应该是
swap(array, end, i);
或类似的东西，如果我们选择 end 作为枢轴。
编辑： 这是一个有趣的分区算法，但不是 标准 一。
好吧， 枢 固定在分区的逻辑中。
该算法将第一个元素视为头部，其余元素将其视为要分区的身体。
完成分区后，作为最后一步，头部（枢轴）与 最后的 左分区部分的元素，以保持订购。
我认为使用其他枢轴而不更改算法的唯一方法是：
...
if (end - start >= 1) {
// Swap the 1st element (Head) with the pivot
swap(array, start, pivot_index);
int pivot = array[start];
...
第一个提示：如果数据是随机的，则平均无关紧要，您选择哪个值作为枢轴。实际改善枢轴“质量”的唯一方法是采用更多（例如3）索引，并使用具有中位价值的索引。
第二提示：如果更改枢轴值，则还需要更改枢轴索引。这不是明确命名的，但是 array[start] 在某一时刻换成分类子序列的“中间”。您需要相应地修改这一行。如果您采用不在子序列边缘的索引，则需要在迭代之前先将其交换到边缘。
第三提示：您提供的代码过度评论。您应该能够真正理解此实现。
放一个
swap(array, start, end)
在初始化枢轴之前
int pivot = array[start]
#include <time.h>
#include <stdlib.h>
#include<iostream>
#include<fstream>
using namespace std;
int counter=0;
void disp(int *a,int n)
{
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;
}
void swap(int a[],int p,int q)
{
int temp;
temp=a[p];
a[p]=a[q];
a[q]=temp;
}
int partition(int a[], int p, int start, int end)
{
swap(a,p,start);// to swap the pivot with the first element of the partition
counter+=end-start; // instead of (end-start+1)
int i=start+1;
for(int j=start+1 ; j<=end ; j++)
{
if(a[j]<a[start])
{
swap(a,j,i);
i++;
}
}
swap(a,start,i-1); // not swap(a,p,i-1) because p and start were already swaped..... this was the earlier mistake comitted
return i-1; // returning the adress of pivot
}
void quicksort(int a[],int start,int end)
{
if(start>=end)
return;
int p=end; // here we are choosing last element of the sub array as pivot
// here p is the index of the array where pivot is chosen randomly
int index=partition(a,p,start,end);
quicksort(a,start,index-1);
quicksort(a,index+1,end);
}
int main()
{
ifstream fin("data.txt");
int count=0;
int array[100000];
while(fin>>array[count])
{
count++;
}
quicksort(array,0,count-1);
/*
int a[]={32,56,34,45,23,54,78};
int n=sizeof(a)/sizeof(int);
disp(a,n);
quicksort(a,0,n-1);
disp(a,n);*/
cout<<endl<<counter;
return 0;
}
如果您开始从数组的第一个元素到最后一个元素监视每个元素，将最后一个元素保留为每个递归的枢轴，那么您将以精确的方式获得答案 o（nlogn） 时间。
#include<stdio.h>
void quicksort(int [], int, int);
int main()
{
int n, i = 0, a[20];
scanf("%d", &n);
while(i < n)
scanf("%d", &a[i++]);
quicksort(a, 0, n - 1);
i = 0;
while(i < n)
printf("%d", a[i++]);
}
void quicksort(int a[], int p, int r)
{
int i, j, x, temp;
if(p < r)
{
i = p;
x = a[r];
for(j = p; j < r; j++)
{
if(a[j] <= x)
{
if(a[j] <a[i])
{
temp = a[j];
a[j] = a[i];
a[i] = temp;
}
i++;
}
else
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
if(x != i)
{
temp = a[r];
a[r] = a[i];
a[i] = temp;
}
quicksort(a, p, i - 1);
quicksort(a, i + 1, r);
}
}
