我会直接进入我的问题。所以基本上我要做的就是生成一个由不同数量的随机数组成的数组。一个有1万，5万，10万，50万，60万等等。然后我将使用快速排序对它们进行排序，并将排序后的数组打印到屏幕上。此外，它运行所需的时间也将被记录和打印。唯一的部分我有问题，然而是生成数组。由于某些原因，生成过去的500,000个随机数不工作，返回如下:
进程在2.112秒后退出，返回值3221225725
按任意键继续…([1]: https://i.stack.imgur.com/m83el.png)
这是我的代码:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void randNums(int array[], int range) {
int i, num;
for (i = 0; i < range; i++) {
num = rand() % range;
array[i] = num;
}
}
//prints elements of given array
void display(int array[], int size) {
int i;
for (i = 0; i < size; i++) {
printf("#%d. %dn", i, array[i]);
}
}
//displays time taken for sorting algorithm to run
void timeTaken(char sortingAlgo[], int size, clock_t start, clock_t end) {
double seconds = end - start;
double milliseconds = seconds / 1000;
printf("Time taken for %s Sort to sort %d numbers was %f milliseconds or %f seconds",
sortingAlgo, size, milliseconds, seconds);
}
//quick sort
void quickSort(int array[], int first, int last) {
int i, j, pivot, temp;
if (first < last) {
pivot = first;
i = first;
j = last;
while (i < j) {
while (array[i] <= array[pivot] && i < last)
i++;
while (array[j] > array[pivot])
j--;
if (i < j) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
temp = array[pivot];
array[pivot] = array[j];
array[j] = temp;
quickSort(array, first, j - 1);
quickSort(array, j + 1, last);
}
}
int main() {
int size = 600000;
int myArray[size];
time_t end, start;
int first, last;
randNums(myArray, size);
first = myArray[0];
last = sizeof(myArray) / sizeof(myArray[0]);
time(&start);
quickSort(myArray, first, last);
time(&end);
display(myArray, size);
timeTaken("Quick", size, start, end);
return 0;
}
任何帮助都将非常感激，谢谢!
这段代码中有很多不难解决的小bug。我将在这里的重构和清理中尝试分解它:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void randNums(int* array, int range) {
// Declare iterator variables like `i` within the scope of the iterator.
for (int i = 0; i < range; i++) {
// No need for a single-use variable here, just assign directly.
array[i] = rand () % range;
}
}
void display(int* array, int size) {
// for is not a function, it's a control flow mechanism, so
// it is expressed as `for (...)` with a space. `for()` implies
// it is a function, which it isn't.
for (int i = 0; i < size; i++) {
printf("#%d. %dn", i, array[i]);
}
}
void timeTaken(char* sortingAlgo, int size, clock_t start, clock_t end) {
// Time calculation here needs to account for the fact that clock_t
// does not use seconds as units, it must be converted
// https://en.cppreference.com/w/c/chrono/clock_t
printf(
"Time taken for %s Sort to sort %d numbers was %.6f seconds",
sortingAlgo,
size,
((double) (end - start)) / CLOCKS_PER_SEC
);
}
void quickSort(int* array, int first, int last) {
// Establish a guard condition. Rest of the function is no longer
// nested in a control flow structure, so it simplifies the code.
if (first >= last) {
return;
}
int pivot = first;
int i = first;
int j = last;
// Use `while (...)` as it's also a control flow structure.
while (i < j) {
// Adding space around operators improves clarity considerably. Unspaced
// elements like `a->b()` are supposed to stand out and not be confused
// with visually similar `a>>b()` which does something very different.
while (array[i] <= array[pivot] && i < last) {
i++;
}
// Use surrounding braces on all blocks, even single-line ones, as this
// can avoid a whole class of errors caused by flawed assumptions.
// while (...) { ... }
while (array[j] > array[pivot]) {
j--;
}
if (i < j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
int temp = array[pivot];
array[pivot] = array[j];
array[j] = temp;
quickSort(array, first, j - 1);
quickSort(array, j + 1, last);
}
int main(int argc, char** argv) {
int size = 600000;
// If an argument was given...
if (argc > 1) {
// ...use that as the size parameter instead.
size = atol(argv[1]);
}
// Allocate an array of sufficient size
int* numbers = calloc(size, sizeof(int));
randNums(numbers, size);
// time_t has at best second-level precision, it's very inaccurate.
// Use clock_t which gives far more fidelity.
clock_t start = clock();
// This function takes *offsets*, not values.
quickSort(numbers, 0, size - 1);
clock_t end = clock();
display(numbers, size);
timeTaken("Quick", size, start, end);
free(numbers);
return 0;
}
这里的第一个错误是错误地调用quickSort():
// Represents first *value* in the array
first = myArray[0]; // Should be: 0
// Rough calculation of the size of the array, but this is off by one
last = sizeof(myArray)/sizeof(myArray[0]); // Should be: size - 1
quickSort(myArray, first, last);