时间戳

首页 > 解决方案 > 为什么这个快速排序实现会给出一个奇怪的输出

c++ - 为什么这个快速排序实现会给出一个奇怪的输出

问题描述

我的快速排序给出了一个奇怪的输出。输出的某些部分是排序的，而某些部分只是随机的。我正在使用数组中的pivot元素partition递归地使用partition function小于枢轴元素的元素和大于枢轴元素的元素。2 halvesleft halfright half

#include <iostream>
using namespace std;

int partition(int *arr, int start, int end)
{
    int pivot = start;
    int temp;
    int temp2;

    while (start < end)
    {
        while (arr[start] <= arr[pivot])
            start++;
        while (arr[end] > arr[pivot])
            end--;

        if (start < end)
        {
            temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
        }
    }
    temp2 = arr[pivot];
    arr[pivot] = arr[end];
    arr[end] = temp2;
    return end;
}

void quickSort(int input[], int size)
{
    int lb = 0;
    int ub = size - 1;
    int loc;
    if (lb < ub)
    {
        loc = partition(input, lb, ub);
        quickSort(input, loc - 1);
        quickSort(input + loc + 1, ub - loc);
    }
    else
        return;
}

int main()
{
    int n;
    cin >> n;

    int *input = new int[n];

    for (int i = 0; i < n; i++)
    {
        cin >> input[i];
    }

    quickSort(input, n);
    for (int i = 0; i < n; i++)
    {
        cout << input[i] << " ";
    }

    delete[] input;
}

标签： c++algorithmrecursiondata-structuresquicksort

解决方案

在这部分中，当您尝试从位置开始对数组进行排序时，您有

quickSort(input, loc - 1);    
quickSort(input + loc + 1, ub - loc);

这意味着 input[loc] 永远不会被处理，因为你从 0 到 loc -1 和 loc +1 到 end

在这里更正

if (lb < ub)
{
    loc = partition(input, lb, ub);
    quickSort(input, loc );
    quickSort(input + loc + 1, ub - loc);
}

推荐阅读