首页 > 代码库 > [整理]快速排序
[整理]快速排序
快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
/*Function: quicksortDescription: 快速排序Calls: swapInput: --v:数组 --left:数组下标 --rigt:数组下标Return: voidOthers: */ void quicksort(int v[],int left,int right){ void swap(int v[],int i,int j); if(left<right){ int i=left,j; int x=v[i];/*第一个元素作为基准元素*/ for (j=i+1;j<=right;j++)/*从第二个元素开始从左向右依次和基准元素比较,小的元素和已比较过的大的元素相互交换位置*/ { if(v[j]<x&&i!=j){ i++; swap(v,i,j); } } swap(v,left,i);/*基准元素和最后一个比较过的小的元素交换位置,至此,小的元素在基准元素左边,大的元素在其右边*/ quicksort(v,left,i-1);/*对小的元素区间继续重复上面步骤*/ quicksort(v,i+1,right);/*对大的元素区间继续重复上面步骤*/ }}void swap(int v[],int i,int j){ int temp=v[i]; v[i]=v[j]; v[j]=temp;}
#include <stdio.h>int main(void){ void quicksort(int v[]); int v[]= { 70, 30, 40, 60, 10, 20, 50, 100, 80, 90 }; int length=sizeof(v)/sizeof(int); int i; quicksort(v,0,length-1); for (i=0;i<length;i++) { printf("%d\n",v[i]); } return 0;}
参考:
快速排序算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。