时间戳

首页 > 解决方案 > 我正在使用快速排序对数组进行排序。但是我让数组未排序。我试图找到错误但失败了

c++ - 我正在使用快速排序对数组进行排序。但是我让数组未排序。我试图找到错误但失败了

问题描述

#include<iostream>
#include<algorithm>
#include<string.h>

using namespace std;

int partition(int input[], int start, int end)
{
    int x = input[start],count=0;

    for (int i=start+1;i<=end;i++)
    {
        if (input[i] <= x)
            count++;
    }

    int temp = input[start+count];
    input[start+count] = x;
    input[start] = temp;

    int i=start, j=end;

    while (input[i] != x && input[j] != x)
    {
        if (input[i] > x && input[j] < x)
        {
            int temp1 = input[j];
            input[j] = input[i];
            input[i] = temp1;

            i++;
            j--;
        }
        else if (input[i] <= x)
        {
            i++;
        }
        else
        {
            j--;
        }
    }

    return count+1;
}

void helpSort(int input[], int start, int end)
{
    if (start >= end)
        return;

    int c = partition(input, start, end);

    helpSort(input, start, start+c-1);
    helpSort(input, start+c+1, end);

    return;
}

void quickSort(int input[], int size)
{
    int start=0,end=size-1;

    helpSort(input, start, end);
}

int main()
{
    int arr[] = {1,3,7,2,6,4,8,9,0,5};

    quickSort(arr, 10);

    for (int i=0;i<10;i++)
    {
        cout<<arr[i]<<" ";
    }

    return 0;
}

我的方法是找到小于数组第一个元素的数字。对其进行分区，然后在分区数组上调用 qs 。例如：- 1 5 7 8 9 3 将其分区为 1。然后使用 1 之前和 1 之后的两个数组对其进行 qs大批。End 表示我的数组的最后一个元素。这是我的代码。提前致谢。

标签： c++sortingquicksort

解决方案

问题出在 while 循环条件中。当它遇到与分区元素相同的元素时，循环关闭。（重复数字）

此外，if 条件不考虑重复元素，即 if (i>x 或 j<x)。它应该是 i>x 或 j<=x。

计数返回应该是返回计数而不是计数+1。这解决了我遇到的问题。

推荐阅读