快速排序 C语言递归调用

84 阅读 0 评论 56 点赞

我是靠谱客的博主天真舞蹈，最近开发中收集的这篇文章主要介绍快速排序 C语言递归调用，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

递归：要满足两个条件 1.循环部分，2.基准条件。

int partition( int a[], int left, int right ) a []是要从左到右排序的数组，其中left是第一个元素的索引，right是最后一个元素的索引。此函数确定数组中的枢轴，并将所有比pilov少的元素向左移动，而将所有所有元素向右移动。重新定位所有元素后，它将返回枢轴的索引。

其中先比较左边，中间，右边三数的大小关系，在将pivot和right-1两个位置进行交换，从而只需比较left-(righth-1)之间的数，

while (1) { /*将序列中比基准小的移到基准左边，大的移到右边*/
while ( a[++Low] < Pivot ) ;
while ( a[--High] > Pivot ) ;
if ( Low < High ) {
temp = a[Low];
a[Low] = a[High];
a[High] = temp;
}//Swap( &A[Low], &A[High] );
else break;

这部分代码是关键，主要是实现让两数进行交换，当不满足条件时推出循环，最重要的是要实现返回递归可以实现下去的条件，

//Swap( &A[Low], &A[Right-1] ); /* 将基准换到正确的位置 */
if(Low < right-1){
temp = a[Low];
a[Low] = a[right-1];
a[right-1] = temp;
return Low;
}
else return Low-1;

这部分做到使递归执行下去的条件。

#include <stdio.h>
int partition( int a[], int left, int right );
void sort ( int a[], int left, int right )//设置统一接口
{
if ( left < right ) {
int p = partition(a, left, right);
sort(a, left, p);
sort(a, p+1, right);
}
}
int main(void)
{
int n;
scanf("%d", &n);
int a[n];
int i;
for (
i=0; i<n; i++ ) {
scanf("%d", &a[i]);
}
sort(a, 0, n-1);
for ( i=0; i<n; i++ ) {
printf("%dn", a[i]);
}
}
int partition( int a[], int left, int right ){
/* 核心递归函数 */
int Pivot, Low, High,temp;
int Center = (left+right) / 2;
if ( a[left] > a[Center] ){
temp = a[left];
a[left] = a[Center];
a[Center] = temp;
}
//Swap( &A[Left], &A[Center] );
if ( a[left] > a[right] ){
temp = a[left];
a[left] = a[right];
a[right] = temp;
}
//Swap( &A[Left], &A[Right] );
if ( a[Center] > a[right] ){
temp = a[Center];
a[Center] = a[right];
a[right] = temp;
}
//Swap( &A[Center], &A[Right] );
/* 此时A[Left] <= A[Center] <= A[Right] */
//Swap( &A[Center], &A[Right-1] ); /* 将基准Pivot藏到右边*/
//right = right -1;
if(Center != right-1){
temp = a[Center];
a[Center] = a[right-1];
a[right-1] = temp;
Pivot = a[right-1];
/* 选基准 */
}
else
Pivot = a[Center];
/* 选基准 */
//right = right -1;
Low = left; High = right-1;
if(Low == High) return Low;
while (1) { /*将序列中比基准小的移到基准左边，大的移到右边*/
while ( a[++Low] < Pivot ) ;
while ( a[--High] > Pivot ) ;
if ( Low < High ) {
temp = a[Low];
a[Low] = a[High];
a[High] = temp;
}//Swap( &A[Low], &A[High] );
else break;
}
//Swap( &A[Low], &A[Right-1] );
/* 将基准换到正确的位置 */
if(Low < right-1){
temp = a[Low];
a[Low] = a[right-1];
a[right-1] = temp;
return
Low;
}
else return Low-1;
}