快速排序

快速排序

1
2
3
4
5
6
7
8
void QuickSort(ElemType A[],int low,int high){
if(low<high){ //递归跳出的条件
//Partition()就是划分操作,将表A[low...high]划分为满足上述条件的两个子表
int pivotpos = Partition(A,low,high); //划分
QuickSort(A,low,pivotpos-1); //依次对两个子表进行递归排序
QuickSort(A,pivotpos+1,high);
}
}
1
2
3
4
5
6
7
8
9
10
11
int Partition(ElemType A[],int low,int high){			//一趟划分
ElemType pivot = A[low]; //将当前表中第一个元素设为枢轴,对表进行划分
while(low<high){ //循环跳出条件
while(low<high&&A[high]>=pivot) --high;
A[low]=A[high]; //将比枢轴小的元素移动到左侧
while(low<high&&A[low]<=pivot) ++low;
A[high]=A[low]; //将比枢轴大的元素移动到右侧
}
A[low]=pivot; //枢轴元素存放到最终位置
return low; //返回存放枢轴的最终位置
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!