package com.wjy.renren; import java.util.Arrays; public class QuickSort { public static void main(String args[]){ int[] array={6,8,4,2,7,9,1,1,9,5}; System.out.println("QuickSort: "); quickSort(array, 0, array.length-1); System.out.println(Arrays.toString(array)); } private static void quickSort(int[] array,int head,int tail){ int begin=head; int end=tail; if(begin>=end){ return; } int temp=array[begin]; while(true){ while(temp<=array[end]&&(begin<end)){ end--; } if(begin>=end){ break; } array[begin]=array[end]; while(temp>=array[begin]&&(begin<end)){ begin++; } if(begin>=end){ break; } array[end]=array[begin]; } array[end]=temp; quickSort(array, head, begin-1); quickSort(array, end+1, tail); } }
一趟快速排序的算法是:
2)以第一个数组元素作为关键数据,赋值给key,即key=A[0];
3)从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key的值A[j],将A[j]赋给A[i];
4)从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]赋给A[j];
5)重复第3、4步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[j]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。
最近发现了一个类似于快排的算法,交换次数很少,和快排思想一样,就是每次确定最后一个元素的最终位置,将小于他的放在左边,大于它的放右边。
int count=0; void swap(int *arr,int i,int j) { int temp; temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } int partion(int *arr,int begin,int end) { int movenum=0; int value=arr[end]; int i; int pos=begin; for(i=begin;i<end;i++) { if(value>=arr[i]) { if(pos!=i) { swap(arr,pos,i); count++; } pos++; //movenum++; } } //swap(arr,begin+movenum,end); swap(arr,pos,end); count++; return pos; } void compute(int *arr,int begin,int end) { if(arr==NULL || begin<0 || end<0 || begin>=end) { return; } else { int middle=partion(arr,begin,end); if(middle>begin) { compute(arr,begin,middle-1); } if(middle<end) { compute(arr,middle+1,end); } } } int main() { int arr[100]; int n; int i; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d",&arr[i]); } compute(arr,0,n-1); for(i=0;i<n;i++) { printf("%d\n",arr[i]); } printf("count is:%d\n",count); system("pause"); return 0; }
相关推荐
快速排序快速排序 快速排序 快速排序 快速排序 快速排序
1、熟悉快速排序的串行算法 2、熟悉快速排序的并行算法 3、实现快速排序的并行算法 3.2 实验环境及软件 单台或联网的多台PC机,Linux操作系统,MPI系统。 3.3实验内容 1、快速排序的基本思想 2、单处理机上快速...
快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序...
(1)用随机快速排序的方法,对输入的数值以从大到小的顺序进行快速排序。 (2)对随机快速排序和冒泡排序这两种排序方法进行比较,测试其在不同数值大小的情况下算法运行的时间复杂度。 二、 实验要求 快速排序...
快速排序,比较高效的排序算法之一。这是一个例子,一个关于快速排序的例子。
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
全面的排序算法实现,包括插入排序、合并排序、堆排序、快速排序。 堆排序:HeapSort 讲解详见http://blog.csdn.net/fly_yr/article/details/8550701 插入排序:InSertion_Sort 讲解详见...
用函数实现快速排序,并输出每次分区后排序的结果 Input 第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 Output 每行输出每趟排序的结果,数据之间用一个空格分隔 Sample Input ...
C语言实现多种链表快速排序
快速排序是实际运用中用的最多的算法,虽然它在最坏的情况下会达到n^2,但它的平均性能非常好,期望时间复杂度为nlgn,而且隐含的常数因子非常小,并且是原址排序。 快速排序原理:从一组数中任意选出一个数,将...
(1) 冒泡排序和快速排序; (2) 插入排序和希尔排序; (3) 选择排序和堆排序; (4) 递归和非递归的归并排序。 2. 产生不同规模和分布的数据,以 Excel 生成算法执行时间 T(n)关于输入规模 n 的曲线的形式,...
快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟 扫描后,使得排序序列的长度能大幅度地减少。在冒泡排序中,一次 扫描只能确保最大数值的数移到正确位置,而待排序序列的长度可能只 减少1。快速...
快速排序的并行实现,提高效率。快速排序算法并行化的一个简单思想是,对每次划分过后所得到的两个序列分别使用两个处理器完成递归排序。
选择排序 冒泡排序 插入排序 合并排序 快速排序算法原理及代码实现 不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 当面临巨大数据量的排序的时候,还是优先选择合并排序算法和快速排序算法。...
1)实现快速排序算法。 2)要求输入待排序元素个数,利用随机函数生成指定数目的元素,元素值的 取值范围为[10, 1000000]。 3)运行快速排序程序对所生成元素进行排序,要求将元素的初始输入序列和 排序后的结果序列...
快速排序算法,C语言 快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有...
C语言快速排序.pdf 快速排序(Quick Sort)是一种高效的排序算法,具有良好的时间复杂度和空间复杂度。快速排序的实现基于分治法,具体分为三个步骤:分解、解决和合并。 在分解步骤中,序列被划分成两个可能为空...
冒泡排序和快速排序的时间性能 冒泡排序和快速排序的时间性能 冒泡排序和快速排序的时间性能 冒泡排序和快速排序的时间性能 冒泡排序和快速排序的时间性能
知道快速排序算法的思想,但是一直都没有动手写,今天写了下,发现还不是那么容易
按所推荐的程序在IE下跑了下,的确,排序耗时很小。 代码如下: [removed] /* * 洗牌 */ function ... /* * 快速排序,按某个属性,或按“获取排序依据的函数”,来排序. * @method soryBy * @static * @