快速排序是目前使用可能最广泛的排序算法了。
一般分如下步骤:
1)选择一个枢纽元素(可以是第一个,也可以是中间的那个)
2)使用该枢纽元素分割数组,使得比该元素小的元素在它的左边,比它大的在右边。并把枢纽元素放在合适的位置。
3)根据枢纽元素最后确定的位置,把数组分成三部分,左边的,右边的,枢纽元素自己,对左边的,右边的分别递归调用快速排序算法即可。
快速排序的核心在于分割算法,也可以说是最有技巧的部分。
快速排序的基本思想是
1、先从数列中取出一个数作为基准数
2、分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边
3、再对左右区间重复第二步,直到各区间只有一个数
- int a[101],n;//定义全局变量,这两个变量需要在子函数中使用
- void quicksort(int left,int right)
- {
- int i,j,t,temp;
- if(left>right)
- return;
- temp=a[left]; //temp中存的就是基准数
- i=left;
- j=right;
- while(i!=j)
- {
- //顺序很重要,要先从右边开始找
- while(a[j]>=temp && i<j)
- j--;
- //再找右边的
- while(a[i]<=temp && i<j)
- i++;
- //交换两个数在数组中的位置
- if(i<j)
- {
- t=a[i];
- a[i]=a[j];
- a[j]=t;
- }
- }
- //最终将基准数归位
- a[left]=a[i];
- a[i]=temp;
- quicksort(left,i-1);//继续处理左边的,这里是一个递归的过程
- quicksort(i+1,right);//继续处理右边的 ,这里是一个递归的过程
- }
- int main()
- {
- int i,j,t;
- //读入数据
- scanf("%d",&n);
- for(i=1;i<=n;i++)
- scanf("%d",&a[i]);
- quicksort(1,n); //快速排序调用
- //输出排序后的结果
- for(i=1;i<=n;i++)
- printf("%d ",a[i]);
- getchar();getchar();
- return 0;
- }
package com.test; import java.util.Arrays; public class QuickSortTest { public static void main(String[] args) { int[] a = {9,1,5,2,10,8}; quickSort(a,0,a.length-1); } /* * 排序的核心算法 * * @param array * 待排序数组 * @param startIndex * 开始位置 * @param endIndex * 结束位置 */ public static void quickSort(int[] array , int startIndex ,int endIndex){ if (startIndex >= endIndex) { return; } int index = sort(array,startIndex,endIndex); //注意下面为递归循环quickSort方法,而不是sort方法 quickSort(array, startIndex, index-1); quickSort(array, index+1, endIndex); System.err.println(Arrays.toString(array)); } /* * 交换并返回分界点 * * @param array * 待排序数组 * @param startIndex * 开始位置 * @param endIndex * 结束位置 * @return * 分界点 */ public static int sort(int[] array, int startIndex ,int endIndex){ int first = array[startIndex]; System.out.println("first:" + first); int i = startIndex; int j = endIndex; while(i<j){ while(i<j && array[j] >= first){ j--; } array[i] = array[j]; while(i<j && array[i] <= first){ i++; } array[j] = array[i]; /*//或 if(i<j) { int t=array[i]; array[i]=array[j]; array[j]=t; } */ } array[i] = first; System.out.println("i:" + i); return i; } }
==========================================================================
方法其实很简单:分别从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”。先从右往左找一个小于6的数,再从左往右找一个大于6的数,然后交换他们。这里可以用两个变量i和j,分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边(即i=1),指向数字6。让哨兵j指向序列的最右边(即j=10),指向数字8。
现在交换哨兵i和哨兵j所指向的元素的值。交换之后的序列如下。
================================================================================
快速排序的基本思想是
1、先从数列中取出一个数作为基准数
2、分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边
3、再对左右区间重复第二步,直到各区间只有一个数
概括来说为 挖坑填数+分治法
下面举例来进行说明,主要有三个参数,i为区间的开始地址,j为区间的结束地址,X为当前的开始的值
第一步,i=0,j=9,X=21
21 | 32 | 43 | 98 | 54 | 45 | 23 | 4 | 66 | 86 |
第二步,从j开始由,后向前找,找到比X小的第一个数a[7]=4,此时i=0,j=6,X=21
进行替换
4 | 32 | 43 | 98 | 54 | 45 | 23 | 21 | 66 | 86 |
第三步,由前往后找,找到比X大的第一个数a[1]=32,此时i=2,j=6,X=21
4 | 21 | 43 | 98 | 54 | 45 | 23 | 32 | 66 | 86 |
第四步,从j=6开始由,由后向前找,找到比X小的第一个数a[0]=4,此时i=2,j=0,X=21,发现j<=i,所以第一回结束
可以发现21前面的数字都比21小,后面的数字都比21大
接下来对两个子区间[0,0]和[2,9]重复上面的操作即可
下面直接给出过程,就步详细解说了
i=2,j=6,X=43
4 | 21 | 43 | 98 | 54 | 45 | 23 | 32 | 66 | 86 |
i=4,j=6,X=43
4 | 21 | 32 | 98 | 54 | 45 | 23 | 43 | 66 | 86 |
i=4,j=5,x=43
4 | 21 | 32 | 43 | 54 | 45 | 23 | 98 | 66 | 86 |
i=5,j=5,x=43
4 | 21 | 32 | 23 | 43 | 45 | 54 | 98 | 66 | 86 |
然后被分为了两个子区间[2,3]和[5,9]
….最后排序下去就是最终的答案
4 | 21 | 23 | 32 | 43 | 45 | 54 | 66 | 86 | 98 |
总结:
1.i =L; j = R; 将基准数挖出形成第一个坑a[i]。
2.j–由后向前找比它小的数,找到后挖出此数填前一个坑a[i]中。
3.i++由前向后找比它大的数,找到后也挖出此数填到前一个坑a[j]中。
4.再重复执行2,3二步,直到i==j,将基准数填入a[i]中。
..
相关推荐
快速排序快速排序 快速排序 快速排序 快速排序 快速排序
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年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有...
冒泡排序和快速排序的时间性能 冒泡排序和快速排序的时间性能 冒泡排序和快速排序的时间性能 冒泡排序和快速排序的时间性能 冒泡排序和快速排序的时间性能
知道快速排序算法的思想,但是一直都没有动手写,今天写了下,发现还不是那么容易
按所推荐的程序在IE下跑了下,的确,排序耗时很小。 代码如下: [removed] /* * 洗牌 */ function ... /* * 快速排序,按某个属性,或按“获取排序依据的函数”,来排序. * @method soryBy * @static * @
快速排序算法是当前使用最多的排序算法之一,它的基本思想是分治法,选择一个划分元,将小于划分元的元素放在左边,将大于划分元的元素放在右边,针对左右子序列重复此过程,直到序列为空或者只有一个元素,这是基本...