实现快速排序算法的3要素划分，

本文介绍了实现快速排序算法的3要素划分，的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

如何转换这种快速排序算法到3，5,7,9和11元分区？

的#includestdafx.h中 ＃包括＆LT;的iostream＆GT; 使用名字空间std; ＃包括＆LT; stdio.h中＆GT; ＃包括＆LT; stdlib.h中＆GT; ＃定义尺寸50 无效掉期（INT * X，诠释* Y） { INT温度; TEMP = * X; * X = * Y; * Y =温度; } INT分区（INT I，诠释J） { 返回（（I + J）/ 2）; } 无效快速排序（INT名单[]，INT男，INT N） { INT键，I，J，K; 如果（米n种） { K =分区（M，N）; 掉期（放大器;列表[M]，和放大器;列表[K]）; 键=列表[M]。 I = m + 1个; J = N; 而（I＆LT; = j）条 { 而（（I＆LT; = N）及及（名单[1] - =键）） 我++; 而（（J＆GT; = M）及及（名单[J] GT;密钥）） j--; 如果（ⅰ＆所述; j）条 掉期（放大器;列表[I]，和放大器;列表[J]）; } 掉期（放大器;列表[M]，和放大器;列表[J]）; 快速排序（列表中，M，J-1）; 快速排序（列表中，J + 1，n）的; } } 无效的printList（INT名单[]，INT N） { INT I; 对于（I = 0; I＆n种;我+ +） 的printf（％D \ T，名单[I]）; } 无效的主要（） { 诠释N，I; INT表【尺寸】; 的printf（要输入多少个数字办）; scanf函数（％d个，和放大器; N）; 的printf（请输入您要排序的编号）; 对于（I = 0; I＆n种;我+ +） { scanf函数（％d个，和放大器;列表[I]）; } 的printf（排序前，这份名单是：\ N）; 的printList（列表中，n）; 快速排序（列表，0，N-1）; 的printf（使用快速排序算法进行排序后的列表：\ N）; 的printList（列表中，n）; 系统（暂停）; }

解决方案

我觉得你的C ++老师只是有文字的一个糟糕的选择。 3个元素的分区几乎可以肯定是指：选择所述枢转元件通过拾取第一，中间和最后一个元素的中值 - 这是最常见的编码技术，并具有良好的性能，当该阵列已经排序

推断出定义5，7，9，11。

How to convert this Quick sort algorithm into partition of 3 ,5,7,9 and 11 elements?

#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"); }

解决方案

I think your C++ teacher simply has a poor choice of wording. "partition of 3 elements" almost certainly means: choose the pivot element by picking the median of the first, middle and last elements -- this is the most common coding technique and has good properties when the array is already sorted.

Extrapolate that definition for 5, 7, 9, 11.