解决快速排序中median函数触发SIGSEGV段错误的问题
从你给出的错误信息和代码来看，导致段错误（SIGSEGV）的核心原因是类型不匹配引发的未定义行为，同时还有几处逻辑错误会导致内存访问异常或排序逻辑失效。下面逐个分析并给出修复方案：
1. 最致命的问题：参数类型不匹配
你的permute_array函数参数定义为int a[]，但调用时传入的是uint32_t array[size]（无符号32位整数数组）。这会导致swap函数接收到错误类型的指针，在交换操作时破坏内存结构，最终引发段错误。
修复：
将permute_array的参数类型改为uint32_t a[]，保持和调用方一致：
void permute_array(uint32_t a[], size_t n) { srand(time(NULL)); for (size_t i = n - 1; i > 0; i--) { size_t j = rand() % (i+1); swap(&a[i], &a[j]); } }
2. Median函数的索引范围错误
在median函数中，你用rand()%(n)生成随机索引，但传入的n是数组的最后一个索引（比如size=1000时n=999），这会导致索引范围是0~998，漏掉了999这个有效索引。更严重的是，如果n为0，会导致rand()%0的未定义行为。
修复：
将索引生成改为rand()%(n+1)，确保覆盖0~n的所有有效索引：
index[0] = rand() % (n + 1);
3. Median函数的重复索引判断逻辑错误
当前你只比较当前索引和上一个选中的索引，无法避免三个索引中出现重复（比如第一个选0，第二个选1，第三个选0），极端情况下还可能陷入死循环（比如rand一直返回同一个值）。
修复：
使用循环确保三个索引完全不重复：
uint32_t median(uint32_t arr[], int n) { if (n <= 3) { return arr[0]; } else { int index[3]; // 生成第一个随机索引 index[0] = rand() % (n + 1); // 生成第二个不重复的索引 do { index[1] = rand() % (n + 1); } while (index[1] == index[0]); // 生成第三个不重复的索引 do { index[2] = rand() % (n + 1); } while (index[2] == index[0] || index[2] == index[1]); uint32_t array[3] = {arr[index[0]], arr[index[1]], arr[index[2]]}; insertion_sort(array, 3); return array[1]; } }
4. QuickSort的分区逻辑缺陷
你当前的快速排序只取出pivot的值进行比较，但没有将pivot放到合适的位置，这会导致分区时出现错误的索引范围，甚至在递归时访问越界。正确的做法是先将pivot交换到固定位置（比如数组末尾），再进行分区，最后将pivot归位。
修复：
修改pivot_select返回pivot的索引而非值，调整分区逻辑：
// 修改pivot_select返回索引 int pivot_select(uint32_t arr[], int first, int last, int pivot_opt) { int pivot_idx = last; int random_index; switch (pivot_opt) { case 0: pivot_idx = last; break; case 1: random_index = first + rand() % (last - first + 1); pivot_idx = random_index; break; case 2: // 生成三个在first~last之间的不重复索引 int idx[3]; idx[0] = first + rand() % (last - first + 1); do { idx[1] = first + rand() % (last - first + 1); } while (idx[1] == idx[0]); do { idx[2] = first + rand() % (last - first + 1); } while (idx[2] == idx[0] || idx[2] == idx[1]); // 找到中位数对应的索引 uint32_t v0 = arr[idx[0]], v1 = arr[idx[1]], v2 = arr[idx[2]]; if ((v0 >= v1 && v0 <= v2) || (v0 <= v1 && v0 >= v2)) { pivot_idx = idx[0]; } else if ((v1 >= v0 && v1 <= v2) || (v1 <= v0 && v1 >= v2)) { pivot_idx = idx[1]; } else { pivot_idx = idx[2]; } break; default: break; } // 将pivot交换到末尾，方便分区 swap(&arr[pivot_idx], &arr[last]); return last; } // 修改quick_sort的分区逻辑 void quick_sort(uint32_t arr[], int first, int last, int pivot_opt) { if (first >= last) return; // 新增递归终止条件，避免无效递归 int pivot_idx = pivot_select(arr, first, last, pivot_opt); uint32_t pivot = arr[pivot_idx]; int i = first, j = last - 1; while (i <= j) { comparations_count++; while (i <= j && arr[i] < pivot) { comparations_count++; i++; } comparations_count++; while (i <= j && arr[j] > pivot) { comparations_count++; j--; } comparations_count++; if (i <= j) { exchanges_count++; swap(&arr[i++], &arr[j--]); } } // 将pivot交换到正确的分区位置 swap(&arr[i], &arr[last]); pivot_idx = i; quick_sort(arr, first, pivot_idx - 1, pivot_opt); quick_sort(arr, pivot_idx + 1, last, pivot_opt); }
5. 函数声明缺失
你的代码中main函数调用了多个函数，但没有提前声明，编译器会隐式声明这些函数（默认返回int类型），这会导致参数类型不匹配的问题。
修复：
在main函数之前添加所有函数的声明：
void fill(uint32_t arr[], uint32_t n); void swap(uint32_t *a, uint32_t *b); void permute_array(uint32_t a[], size_t n); void insertion_sort(uint32_t arr[], size_t n); void quick_sort(uint32_t arr[], int first, int last, int pivot_opt); int pivot_select(uint32_t arr[], int first, int last, int pivot_opt); uint32_t median(uint32_t arr[], int n);
完成以上修复后，你的快速排序应该可以正常运行，并且各pivot选择方式都能正确工作。
内容的提问来源于stack exchange，提问作者Leonard
