时间戳

首页 > 解决方案 > 关于使用 std::vector 进行快速排序的问题

c++ - 关于使用 std::vector 进行快速排序的问题

问题描述

下面是我从互联网上找到的一些代码，它使用整数数组作为输入。它运行良好，但如果我将数组更改为向量，它只会打印原始输入 95、45、48、98、1、485、65、478、1、2325。谁能解释它发生的原因以及如何修复它？

#include <iostream>
#include <vector>

using namespace std;



            void printArray(vector<int> array, int n)
            {
                for (int i = 0; i < n; ++i)
                    cout << array[i] << endl;
            }

            void quickSort(vector<int> array, int low, int high)
            {
                int i = low;
                int j = high;
                int pivot = array[(i + j) / 2];
                int temp;

                while (i <= j)
                {
                    while (array[i] < pivot)
                        i++;
                    while (array[j] > pivot)
                        j--;
                    if (i <= j)
                    {
                        temp = array[i];
                        array[i] = array[j];
                        array[j] = temp;
                        i++;
                        j--;
                    }
                }
                if (j > low)
                    quickSort(array, low, j);
                if (i < high)
                    quickSort(array, i, high);
            }

            int main()
            {
                vector<int> array = {95, 45, 48, 98, 1, 485, 65, 478, 1, 2325};
                int n = sizeof(array)/sizeof(array[0]);

                cout << "Before Quick Sort :" << endl;
                printArray(array, n);

                quickSort(array, 0, n);

                cout << "After Quick Sort :" << endl;
                printArray(array, n);
                return (0);
            }

标签： c++vectorquicksort

解决方案

您正在将向量按值传递给quicksort函数，这会导致它对输入向量的副本进行操作（因此原始向量保持不变）。一个可能的解决方案是通过引用传递它。所以声明quicksort应该是：

void quickSort(std::vector<int> &array, int low, int high)

代码的另一个问题是这sizeof(array)/sizeof(array[0])不是获取向量大小的正确方法，有效的方法是使用该std::vector::size()方法（正如 H. Guijt 的回答中所指出的）

推荐阅读