快速排序
快速排序时间复杂度为O(nlogn)，由于是在原数组上面利用替换来实现，因此不需要额外的存储空间。
算法思想：
通过设置一个岗哨，每次跟这个岗哨进行比较，比他小的放在左边，比他大的放在右边。再对岗哨左边的数组0----middle-1,和middle+1-----end，进行同样的排序。
主要代码：
void QuikSort(int *arr,int begin,int end){
int middle;
if(begin < end){
middle = Patition(arr,begin,end);
QuikSort(arr,0,middle-1);
QuikSort(arr,middle+1,end);
}
}
int Patition(int * arr,int begin,int end){
int middle = arr[begin];
int tmp;
while(begin < end){
while(begin < end && arr[end] >= middle)
end--;
tmp = arr[end];
arr[end] = arr[begin];
arr[begin] = tmp;
while(begin<end && arr[begin] <= middle)
begin++;
tmp = arr[end];
arr[end] = arr[begin];
arr[begin] = tmp;
}
return begin;
}全部代码：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int arrtest1[10] = {4,3,7,8,0,9,1,2,6,5};
int arrtest2[10] = {0,1,2,3,4,5,6,7,8,9};
int arrtest3[10] = {9,8,7,6,5,4,3,2,1,0};
void copy(int *from,int *arr,int length);
void print(int *arr,int length);
void QuikSort(int *arr,int begin,int length);
int Patition(int * arr,int begin,int end);
int main(){
int Arr[10],i;
copy(arrtest1,Arr,10);
print(Arr,10);
QuikSort(Arr,0,9);
print(Arr,10);
getchar();
return 0;
}
void QuikSort(int *arr,int begin,int end){
int middle;
if(begin < end){
middle = Patition(arr,begin,end);
QuikSort(arr,0,middle-1);
QuikSort(arr,middle+1,end);
}
}
int Patition(int * arr,int begin,int end){
int middle = arr[begin];
int tmp;
while(begin < end){
while(begin < end && arr[end] >= middle)
end--;
tmp = arr[end];
arr[end] = arr[begin];
arr[begin] = tmp;
while(begin<end && arr[begin] <= middle)
begin++;
tmp = arr[end];
arr[end] = arr[begin];
arr[begin] = tmp;
}
return begin;
}
void copy(int *from,int *arr,int length){
int i;
for(i=0;i<length;i++){
arr[i] = from[i];
}
}
void print(int *arr,int length){
int i;
for(i=0;i<length;i++){
printf("%d ",arr[i]);
}
printf("\n");
}运行实例：
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2014-04-21 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
