快速排序稳定性验证代码

#include<iostream>
using namespace std; 
#include"QuickSort.h"
#include"swap.h"
int comparisons6 = 0;
int moves6 = 0;
void QuickSort(int arr[], int low, int high, int& comparisons, int& moves)
{
    // 创建辅助数组，保存原始索引位置
    int* aux = new int[high+1];
    for (int i = 0; i < high+1; i++)
    {
        aux[i] = i;
    }
    int i = low, j = high;
    int temp = arr[low];//取第一个元素为标准数据元素
    int tempAux = aux[low];
    while (i < j)
    {
        while (i < j && temp <= arr[j]) //在数组的右端扫描 
        {
            j--;
            comparisons6++;//关键字比较一次
        }
        if (i < j)
        {
            arr[i] = arr[j];
            aux[i] = aux[j];
            i++;
            moves6++;//关键字移动一次
        }

        while (i < j && arr[i] < temp) //在数组的左端扫描
        {
            i++;
            comparisons6++;//关键字比较一次 
        }
        if (i < j)
        {
            arr[j] = arr[i];
            aux[j] = aux[i];
            j--;
            moves6++;//关键字移动一次
        }
    }
    arr[i] = temp;
    aux[i] = tempAux;
    moves6++;//关键字移动一次
    if (low < i) QuickSort(arr, low, i - 1, comparisons6, moves6);//对左端子集合进行递归
    if (i < high) QuickSort(arr, j + 1, high, comparisons6, moves6);//对右端子集合进行递归
    
    // 验证稳定性
    bool stable = true;
    for (int i = 1; i < high + 1; i++)
    {
        // 如果值相等，但是索引位置发生变化，则说明不稳定
        if (arr[i] == arr[i - 1] && aux[i] < aux[i - 1])
        {
            stable = false;
            break;
        }
    }
    if (stable)
    {
        cout << "快速排序是稳定的" << endl;
    }
    else
    {
        cout << "快速排序是不稳定的" << endl;
    }
}
我这个快速排序通过建立辅助数组的方法验证稳定性是在网上找的，但是.他会输出n条“快速排序是稳定/不稳定”的语句，我不知道什么情况，别的排序没有出现这个问题

参考GPT和自己的思路：这段代码会输出n条“快速排序是稳定/不稳定”的语句，是因为在每次递归执行排序时都会进行稳定性的验证，而不是在整个排序过程结束后进行一次验证。如果你希望只输出一次验证结果，可以将稳定性验证的代码移动到递归调用结束后。

你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/7469402
我还给你找了一篇非常好的博客，你可以看看是否有帮助，链接：冒泡排序算法及代码
除此之外, 这篇博客: 冒泡排序法中的代码部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:

方法一：

#include<stdio.h>

    int main()
    {

        int i,j,temp;
        int arr[4]={43,12,66,19};
   
        for(i=0;i<4;i++){
            for(j=0;j<4;j++){
                    if(arr[j]>arr[j+1]){

                        temp=arr[j];
                        arr[j]=arr[j+1];
                        arr[j+1]=temp;
                }
            }
        }
        printf("按从小到大排序：\n");
        for(i=0;i<4;i++){
            printf("%d ",arr[i]);
        }

        return 0;
    }

这是比较基本的代码，也可以根据需要进行修改。

以上代码运行结果如下：

方法二：

#include<stdio.h>

    int main()
    {

        int i,j,temp;
        int arr[]={43,12,66,19};
        int len=sizeof(arr)/sizeof(arr[0]);  //计算出数组的长度
        for(i=0;i<len-1;i++){
            for(j=0;j<len-1-i;j++){
                    if(arr[j]>arr[j+1]){

                        temp=arr[j];
                        arr[j]=arr[j+1];
                        arr[j+1]=temp;
                }
            }
        }
        printf("按从小到大排序：\n");
        for(i=0;i<len;i++){
            printf("%d ",arr[i]);
        }

        return 0;
    }

运行结果也是一样的：

这两个方法都是冒泡排序，只不过方法二在后续的修改中更加方便。

接下来简单讲一下方法二中的语句：

int arr[]={43,12,66,19};
int len=sizeof(arr)/sizeof(arr[0]);  //计算出数组的长度

第一句是定义一个数组arr[],他的特点就是[]里面是空的可以不用写数组的长度，那问题来了，数组的长度怎么计算呢？这就到了第二句了，第二句中sizeof就是用来计算大小的，我们可以用他来计算数组的长度。这样子的话，不管我们在数组里输入多少数字，都能进行排序。

我们来看一下运行效果：

那我们代码里实现的是从小到大对数组进行排序，那我们如果想要把数组进行从大到小进行排序的话，该如何进行修改呢？

 if(arr[j]>arr[j+1]){

                        temp=arr[j];
                        arr[j]=arr[j+1];
                        arr[j+1]=temp;
                }

我们来看一下这段代码，就是第j个数和第j+1个进行比较，数值大的就排到后面，就可以实现从小到大进行排序。如果我们要进行从大到小进行排序，只需要把">"改成"<"就可以了。

接下来就让我们看一下运行效果吧：

好了，关于冒泡排序法就总结到这啦~拜拜下次见。

您还可以看一下张云波老师的以太坊智能合约项目实战课程中的代币发行和转账测试小节, 巩固相关知识点