我想了解快速排序机制,但到目前为止我还搞不懂。根据维基百科,步骤是:
1.从列表中选择一个称为枢轴的元素。
2. 重新排序列表,使值小于基准的所有元素都在基准之前,而值大于基准的所有元素都在基准之后(相等的值可以任意排列) .在此分区之后,枢轴位于其最终位置。这称为分区操作。
3. 递归地将上述步骤应用于具有较小值的元素子列表,并分别应用于具有较大值的元素子列表。
这是代码:
int partition(int arr[], int left, int right)
{
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
return i;
}
void quickSort(int arr[], int left, int right) {
int index = partition(arr, left, right);
if (left < index - 1)
quickSort(arr, left, index - 1);
if (index < right)
quickSort(arr, index, right);
}
除一件事外,我对一切都一清二楚。为什么分区函数返回 i
而不是 j
?
最佳答案
我找到了这个程序(和输出)here .看看,
#include <iostream>
using namespace std;
const int INPUT_SIZE = 10;
// A simple print function
void print(int *input)
{
for ( int i = 0; i < INPUT_SIZE; i++ )
cout << input[i] << " ";
cout << endl;
}
// The partition function
int partition(int* input, int p, int r)
{
int pivot = input[r];
while ( p < r )
{
while ( input[p] < pivot )
p++;
while ( input[r] > pivot )
r--;
if ( input[p] == input[r] )
p++;
else if ( p < r )
{
int tmp = input[p];
input[p] = input[r];
input[r] = tmp;
}
}
return r;
}
// The quicksort recursive function
void quicksort(int* input, int p, int r)
{
if ( p < r )
{
int j = partition(input, p, r);
quicksort(input, p, j-1);
quicksort(input, j+1, r);
}
}
int main()
{
int input[INPUT_SIZE] = {500, 700, 800, 100, 300, 200, 900, 400, 1000, 600};
cout << "Input: ";
print(input);
quicksort(input, 0, 9);
cout << "Output: ";
print(input);
return 0;
}
OUTPUT:-
Input: 500 700 800 100 300 200 900 400 1000 600
Output: 100 200 300 400 500 600 700 800 900 1000
关于c++ QuickSort不清楚,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15370661/