如何在c++中计算已执行的元素排列并显示快速排序的排序过程?

Question

我是快速排序算法的新手，我想计数交换并输出它的过程(显示每次执行排列后数组排序的中间状态)。谢谢你。

#include <iostream>
#include <iomanip>
using namespace std;

void print(const int a[])
{
for(int i=0;i < 10; i++) {
cout << setw(3) << a[i];
}
cout << endl;
}
int Partition( int *A , int start , int end )
{
int pivot = A[end]; 
int partitionIndex = start; 
int i = start;
while ( i < end ){ 
if( A[i] < = pivot ){
swap ( A[i], A[partitionIndex] );
partitionIndex++; 
}
i ++ ;
print(A); //something wrong here?
}
swap( A[partitionIndex], A[end]);
return partitionIndex;  
}

这是我的递归函数

void QuickSort( int *A , int start , int end ){
if( start < end ){
int partitionIndex = Partition( A , start , end );
QuickSort( A , start , partitionIndex - 1 );
QuickSort( A , partitionIndex + 1 , end );
}

main函数

int main(){
int n = 10;
int *A = new int[n]; 
for (int i = 0 ; i < n ; i ++ ){
cin >> A[i];
}
cout<<endl;
QuickSort( A , 0 , n - 1 ); 
for(int i = 0 ; i < n ; i++){
cout << A[i] <<" "; 
}
delete []A;
}

Answer 1

下面是快速排序的一个版本，打印它正在做的事情。它以特定的颜色突出显示活动使用的项目:

• 黄色用于比较两个项目
• 红色用于交换两个物品
• 绿色用于显示枢轴结束的位置

代码:

#include <iostream>
#include <iomanip>
using std::cout;
using std::setw;
void print(const char *prefix, const int a[], const int color, const int left, const int right, const int start, const int end, const int size)
{
cout << setw(20) << prefix << " ";
for (int i=0; i<size; i++)
{
if (i >= start && i <= end)
{
if (i == left || i == right)
cout << " x1b[1mx1b[" << color << "m" << setw(3) << a[i] << "x1b[0m";
else
cout << " x1b[0m" << setw(3) << a[i];
}
else
cout << setw(4) << " ";
}
cout << "n";
}
int swaps = 0;
void swap(int A[], const int left, const int right, const int start, const int end, const int size)
{
if (left == right)
return;
print("Swapping:", A, 31, left, right, start, end, size);
int temp = A[left];
A[left]  = A[right];
A[right] = temp;
swaps++;
}
int partition(int A[], const int start, const int end, const int size)
{
int pivot = A[end];
int partitionIndex = start;

for (int i = start; i < end; i++)
{
print("Comparing:", A, 33, i, end, start, end, size);
if (A[i] < pivot)
swap(A, i, partitionIndex++, start, end, size);
}
swap(A, partitionIndex, end, start, end, size);
return partitionIndex;
}
void quicksort(int A[], const int start, const int end, const int size)
{
if (start > end)
return;
cout << "n";
print("About to sort:", A, 0, -1, -1, start, end, size);
if (start == end)
return;
int p = partition(A, start, end, size);
print("Partitioned:", A, 32, p, p, start, end, size);
quicksort(A, start, p-1, size);
quicksort(A, p+1, end, size);
}        
int main()
{
int A[] = { 7, 2, 9, 1, 8, 4, 6, 3, 10, 5 };
quicksort(A, 0, 9, 10);
cout << "n";
print("Sorted:", A, -1, -1, -1, 0, 9, 10);
return 0;
}

试试:https://onlinegdb.com/BJJ-9IXGd

如果您的环境不理解ANSI转义序列，这里有一个显示类似信息但不使用它们的变体:

#include <iostream>
#include <iomanip>
using std::cout;
using std::setw;
void print(const char *prefix, const int a[], const int start, const int end, const int size)
{
cout << setw(20) << prefix << " {";
for (int i=0; i<size; i++)
if (i >= start && i <= end)
cout << (i == 0 ? "" : ",") << setw(3) << a[i];
else
cout << (i == 0 ? "" : ",") << setw(3) << " ";
cout << "}n";
}
void print_swap(const char *prefix, const int a[], const int left, const int right, const int size)
{
cout << setw(20) << prefix << " {";
for (int i=0; i<size; i++)
if (i == left || i == right)
cout << (i == 0 ? "" : ",") << setw(3) << a[i];
else
cout << (i == 0 ? "" : ",") << setw(3) << " ";
cout << "}n";
}
int swaps = 0;
void swap(int A[], const int left, const int right, const int size)
{
if (left == right)
return;

print_swap("Swapping:", A, left, right, size);
int temp = A[left];
A[left]  = A[right];
A[right] = temp;
swaps++;
}
int partition(int A[], const int start, const int end, const int size)
{
int pivot = A[end];
int partitionIndex = start;

for (int i = start; i < end; i++)
{
print_swap("Comparing:", A, i, end, size);
if (A[i] < pivot)
swap(A, i, partitionIndex++, size);
}
swap(A, partitionIndex, end, size);
return partitionIndex;
}
void quicksort(int A[], const int start, const int end, const int size)
{
if (start > end)
return;
cout << "n";
print("About to sort:", A, start, end, size);
if (start == end)
return;
int p = partition(A, start, end, size);
print("Partition:", A, p, p, size);
print("Partitioned:", A, start, end, size);
quicksort(A, start, p-1, size);
quicksort(A, p+1, end, size);
}        
int main()
{
int A[] = { 7, 2, 9, 1, 8, 4, 6, 3, 10, 5 };
quicksort(A, 0, 9, 10);
cout << "n";
print("Sorted:", A, 0, 9, 10);
return 0;
}

试试:https://onlinegdb.com/rktvKUQfd