时间戳

首页 > 解决方案 > 对数组进行排序会给出错误的值

c++ - 对数组进行排序会给出错误的值

问题描述

我已经在 C++ 中实现了快速排序。以下是我的代码。

#include <iostream>
using namespace std;

template <typename T>
void swap(T *a, T *b)
{
    T temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

template <typename T>
void PrintArray(T arr[], int n)
{
    cout << "---------- Array ----------" << endl;
    for (int i=0; i<n ; i++)
    {
        cout << arr[i] <<'\t';
    }
    cout << endl;
}

template <typename T>
int partition(T arr[], int low, int high)
{   
    T pivot = arr[low];
    int i = low+1, j = high;
    do
    {
        while (pivot >= arr[i])
        {
            i += 1;
        }

        while (pivot < arr[j])
        {
            j -= 1;
        }

        if (i<j)
        {
            swap<T>(arr[i], arr[j]);
        }

    }while( i < j);

    swap<T>(arr[low], arr[j]);
    return j;  
}

template <typename T>
void quick_sort(T arr[], int low, int high)
{
    if (low < high)
    {
        int parition_index;
        parition_index = partition<T>(arr, low, high);

        quick_sort<T>(arr, low, parition_index-1);

        quick_sort<T>(arr, parition_index+1, high);
    }       
}

int main()
{
    // Array creation
    int n = 8;
    int a[] ={4, 3,2, 1, 18, -1, 89, -200};
    
    // Array sorting
    quick_sort<int>(a,0, n);
    PrintArray<int>(a, n);

    return 0;
}

它给出了排序数组，即-200, -1, 1, 2, 3, 4, 18, 89大多数时候。但是，重新运行代码可能会在某些索引处产生垃圾值（例如：）-968225408, -200, -1, 1, 2, 3, 4, 18。为了检查，我用帖子https://www.geeksforgeeks.org/quick-sort/中的块中的函数替换了上面代码中的所有函数。尽管如此，问题仍然存在。

代码可能有什么问题，问题的解决方案是什么。

标签： c++algorithmsortingquicksort

解决方案

@FrançoisAndrieux 评论对于找出问题非常有用。

正如他指出的那样，j将 8 作为超出范围的值。解决问题

第 1 步：quick_sort<int>(a,0, n-1);在int main().

步骤2：敲掉自定义swap函数

推荐阅读