//quick sort //author: jinyejun //date: 2014-11-4 8:30 #include<cstdio> #define MAXN 1000 int arr[1000]; void swap(int i,int j); void quick_sort(int s,int t); int partion(int s,int t); int main(){ //输入待排序的数组 printf("请输入待排序数组长度\n"); int len; scanf("%d",&len); printf("请输入待排序数组\n"); for(int i=0;i<len;i++){ scanf("%d",arr+i); } printf("排序过后的数组\n"); quick_sort(0,len-1); for(int i=0;i<len;i++){ printf("%d ",arr[i]); } return 0; } //快速排序主程序 void quick_sort(int s,int t) { //找到分割点 if(s<t){ int m = partion(s,t); quick_sort(s,m-1); quick_sort(m+1,t); } } int partion(int s,int t){ int i = s; int j = t+1; //分割元素 int p = arr[s]; while(true){ //从左边开始寻找比分割元素大的值 while(arr[++i] < p && i < t); //从右边开始寻找比分割元素小的值 while(arr[--j] > p); //如果两边相遇则结束 if(i>=j) break; //交换两边找到的值,使得左边元素 //都比分割元素小,右边元素都比 //分割元素大 swap(i,j); } //把分割元素放到合适的位置里形成新的数组 arr[s] = arr[j]; arr[j] = p; return j; } //交换两边的元素 void swap(int i,int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
相关推荐
* 快速排序3.0 —— 随机快排,时间复杂度收敛于 O(NlogN) */ public class QuickSort { /** * * @param arr 需要排序的数组 * @param L 需要排序部分的左边界 * @param R 需要排序部分的右边界 */ public ...
(1)用随机快速排序的方法,对输入的数值以从大到小的顺序进行快速排序。 (2)对随机快速排序和冒泡排序这两种排序方法进行比较,测试其在不同数值大小的情况下算法运行的时间复杂度。 二、 实验要求 快速排序...
快速排序c++实现代码 它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归...
几张树图快速掌握快速排序的方法,上课用的没有程序可以参考一下
以前学习数据结构的时候写快排用的循环都是双重for循环,今天偶尔看到了运用递归来实现快速排序,所以突发想记录一下。由于我以前学过c和java,现在在自学python,所以一下代码均为python。但基本思想是一样的。 1....
php递归与非递归快速排序写法php递归与非递归快速排序写法php递归与非递归快速排序写法php递归与非递归快速排序写法
c语言实现的快速排序算法,及其一步步优化代码(1. 数组长度较小时候选择插入排序;2. 主元在数组最左最右,中间三个数字中间选择中间大小的, 数组拆分后将 重复数字挪到主元附近,不进行重复partition)
1.快速排序的思想 先从数列中取出一个数作为基准数(简单起见就选第一个数) 分区过程:将比这个数大的数全放到他的右边,比他小的数全放到他的左边(分治) 再对左右两边的区重复第一步和第二部操作,直到各区间...
里面主要是用java 编写的有关快速排序算法的详细说明!!