實現3元素分區的快速排序算法，

Question

如何將此快速排序算法轉換爲3,5,7,9和11元素的分區？

#include"stdafx.h" 
#include<iostream> 
using namespace std; 
#include <stdio.h> 
#include <stdlib.h> 
#define size 50 
void swap(int *x,int *y) 
{ 
int temp; 
temp = *x; 
*x = *y; 
*y = temp; 
} 

int partition(int i,int j) 
{ 
return((i+j) /2); 
} 

void quicksort(int list[],int m,int n) 
{ 
int key,i,j,k; 
if(m < n) 
{ 
k = partition(m,n); 
swap(&list[m],&list[k]); 
key = list[m]; 
i = m+1; 
j = n; 
while(i <= j) 
{ 
while((i <= n) && (list[i] <= key)) 
i++; 
while((j >= m) && (list[j] > key)) 
j--; 
if(i < j) 
swap(&list[i],&list[j]); 
} 

swap(&list[m],&list[j]); 
quicksort(list,m,j-1); 
quicksort(list,j+1,n); 
} 
} 
void printlist(int list[],int n) 
{ 
int i; 
for(i=0;i<n;i++) 
printf("%d\t",list[i]); 
} 

void main() 
{ 
int n,i; 
int list[size]; 


printf("How many numbers do you want to enter"); 
scanf("%d",&n); 
printf("Enter the numbers you want to sort"); 
for(i=0;i<n;i++) 
{ 
scanf("%d",&list[i]); 
} 


printf("The list before sorting is:\n"); 
printlist(list,n); 
quicksort(list,0,n-1); 
printf("The list after sorting using quicksort algorithm:\n"); 
printlist(list,n); 
system("pause"); 
} 

Answer 1

我認爲你的C++老師只是有一個糟糕的措辭選擇。 「3個元素的分區」幾乎肯定意味着：通過選擇第一個，中間和最後一個元素的中間值來選擇主元素 - 這是最常用的編碼技術，並且在數組已經排序後具有良好的屬性。

推斷該定義爲5，7，9，11.

Answer 2

分區是quicksort算法的重要組成部分。回顧the algorithm瞭解什麼是分區。祝你好運。