帮助实施快速排序 [英] Help implementing quick sort

问题描述

这是我所拥有的，它不起作用.无法弄清原因...问题可能出在quick_sort函数中.

This is what I have and it doesn't work. Can't figure out why... The problem is probably in the quick_sort function.

#include <stdio.h>
#include <stdlib.h>

void quick_sort(int * a, int l, int r);
void swap(int * a, int i, int j);

int main(void)
{
  #define N 10
  int a[N], i;
  for (i = 0; i < N; ++i) {
    a[i] = rand();
    printf("%d\n", a[i]);
  }
  quick_sort(a, 0, N - 1);
  for (i = 0; i < N; ++i)
    printf("%d\n", a[i]);
  return 0;
  #undef N
}

void quick_sort(int * a, int l, int r)
{
  int i, j;
  if (l < r) {
    swap(a, rand() % (r - l + 1), r);
    i = l;
    for (j = l; j < r; ++j)
      if (a[j] < a[r]) {
        swap(a, i, j);
        ++i;
      }
    swap(a, i, r);
    quick_sort(a, l, i - 1);
    quick_sort(a, i + 1, r);
  }
}

void swap(int * a, int i, int j)
{
  int k;
  k = a[i];
  a[i] = a[j];
  a[j] = k;
}

推荐答案

修复此行:swap(a, rand() % (r - l + 1), r);

应该是:swap(a, l + rand() % (r - l + 1), r);

这篇关于帮助实施快速排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！