使用quicksort用指针对数组进行排序 [英] Sort arrays with pointers using quicksort

问题描述

我正在尝试使用quicksort对数组"tab"中的值进行排序，但是它不起作用.主要功能只是为每个标签设置名称和薪金[n]

I'm trying to sort the values in the array "tab" using quicksort, but it isn't working. the main function just set names and salaries for each tab[n]

typedef struct employee Employee;

struct employee{
  char name[81];
  float salary;
};

Employee *tab[10];

void sort(Employee **tab, int begin, int end){
  int p = tab[(begin + end) / 2] , i = end, j = begin;  
  /*p is the pivot*/
  do{
    while(tab[i]->salary < p && i < end) i++; 
    while(tab[j]->salary > p && j > begin) j--; 

    if(i <= j){
      int tmp = tab[i]->salary;
      tab[i]->salary = tab[j]->salary;
      tab[j]->salary = tmp;
      i++; j--;
    }
  }while(i <= j);

  if(begin < j) sort(tab, begin, j);
  if(end > i) sort(tab, i, end);
}

推荐答案

注释中指出的更改.这是一种降序排序(如后续问题所述).

Changes noted in comments. This is a descending order sort (as asked in a follow up question).

#include <stdio.h>

typedef struct employee{
    char name[81];
    float salary;
}Employee;

void sort(Employee **tab, int begin, int end){
    float p = tab[(begin + end) / 2]->salary; /* float needed for compare == */
    int i = begin, j = end;
    Employee *tmp;                          /* microsoft is c89 */

    while(i <= j){                      /* using while */
        while(tab[i]->salary > p) i++;  /* >, <= pivot stops scan */
        while(tab[j]->salary < p) j--;  /* <, >= pivot stops scan */
        if(i > j)                       /* using break */
            break;
        tmp = tab[i];
        tab[i] = tab[j];
        tab[j] = tmp;
        i++; j--;
    }

    if(begin < j) sort(tab, begin, j);
    if(end > i) sort(tab, i, end);
}

int main(int argc, char**argv)
{
    Employee tab[] = {{"john", 525.}, {"jack", 520.},
                      {"mary", 537.}, {"jane", 523.},
                      {"joan", 548.}, {"sam",  524.},
                      {"lisa", 527.}, {"ann",  541.},
                      {"tom",  521.}, {"ted",  531.}};
    Employee *ptr[sizeof(tab)/sizeof(tab[0])];
    int i;
    /* create array of pointers */
    for(i = 0; i < (sizeof(tab)/sizeof(tab[0])); i++)
        ptr[i] = &tab[i];
    sort(ptr, 0, sizeof(ptr)/sizeof(ptr[0])-1);
    for(i = 0; i < (sizeof(ptr)/sizeof(ptr[0])); i++)
        printf("%5s %6.2f\n", ptr[i]->name, ptr[i]->salary);
    return 0;
}

这篇关于使用quicksort用指针对数组进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！