我的QuickSort实现跳过了最后一个值。

Question

相对新手程序员，想实现一个quicksort算法。分区总是每个新数组中的第一个。我从左边和右边运行指针i和j，直到找到比i的分区大而比j的分区小的东西，然后我就把两者交换。除了总是跳过最后一个值之外，这段代码工作得比较好。

#include <iostream>
#include <string>
#include <iomanip>
#include <cstdlib>
#include <time.h>
#include <fstream>

using namespace std;
void QuickSort(int[], int, int);
void Partition(int[], int, int);
int main()
{
    int A[] = { 1, 3, 2, 6, 7, 5, 8, 9};
    QuickSort(A, 0, 7);
    for (int i = 0; i < 7; i++) {
        cout << A[i];
    }
}

void QuickSort(int A[], int first, int last) {
    if (last - first <= 1) {
        return;
    }

    Partition(A, first, last);



}

void Partition(int A[], int first, int last) {
    int partition = first;
    int i, j;
    i = first + 1;
    j = last;
    while (i < j) {
        if (A[i] < A[partition]) {
            while (A[i] < A[partition] && i != j) {
                i++;
            }
                if (A[i] >= A[partition]) {
                    while (A[j] > A[partition] && i != j) {
                        j--;

                    }

                }
                if (i == last && j == last && partition < i) {
                    if (A[partition] > A[i]) {
                        int k = A[partition];
                        int l = A[i];
                        A[i] = l;
                        A[j] = k;
                    }
                }
                int k, l;
                k = A[i];
                l = A[j];
                A[i] = l;
                A[j] = k;

        }
        else if (A[j] > A[partition]) {
            while (A[j] > A[partition] && i!=j) {
                j--;
            }
                if (A[j] < A[partition]) {
                    while (A[i] < A[partition] && i != j) {
                        i++;

                    }


                int k, l;
                k = A[i];
                l = A[j];
                A[i] = l;
                A[j] = k;
            }
        }

        else {
            int k, l;
            k = A[i];
            l = A[j];
            A[i] = l;
            A[j] = k;

        }

        i++;
        if (i > j) {
            i--;
        }

    }

    i = i - 1;
    int l, k;
    l = A[i];
    k = A[partition];
    A[i] = k;
    A[partition] = l;


    QuickSort(A, first, i);
    QuickSort(A, i + 1, last);
}

Answer 1

这只是你打印结果的方式。

for (int i = 0; i < 7; i++) {
    cout << A[i];
}

它只打印数组中的前7个元素, 而总共有8个元素. 试试下面的方法

for (int i = 0; i < 8; i++) {
    cout << A[i];
}

这是每一个编程学习者常犯的一个关一错误，避免这个错误的好方法是记住一定要把 i < array.size() 在for循环条件下。