快速排序使用分治法策略来把一个串行分为两个子串行。
步骤为:
1. 从数列中挑出一个元素,称为“基准”(pivot),
2。重新排列数列,小的在基准前,大的在基准后,基准位于中间,称为分区(partition)操作
3。递归排列两个分区
最好的情况下,每次排列分区操作将数列分为等长的两个部分,这时调用次数为O(logn);
最坏的情况下,每次选中的基准为最小数或最大数,每次排列后的两部分的长度为N-i-1和1(i为次数),则调用次数为O(N)
因为每次调用都有n次比较,时间复杂度为O(n),所以时间复杂度为 O(nlogn) ~ O(n2).
在递归函数调用返回之前,使用的空间是固定的,但是每一层调用都要分配一定的空间进行分界点信息的保存。
每次调用都会有1的空间,所以空间复杂度为O(logn)~O(n)
在最坏的情况下,需要进行O(n)次的函数调用,就需要占用O(n)的空间。而在最好的情况下,需要进行O(logn)次的函数调用,那么需要占用的空间的量为O(logn)。
package com.longshine.arthmetic.sort; import java.util.ArrayList; import java.util.List; import com.longshine.arthmetic.Util; /** * 快速排序 * @author skymr * */ public class QuickSort { private List<SortElement> sortList; public QuickSort(List<SortElement> sortList) { this.sortList = sortList; } public void sort() { sort(0, sortList.size() - 1); } private void sort(int left, int right) { if (left >= right ) return; int pivotIndex = left + (right - left) / 2; SortElement pivot = sortList.get(pivotIndex); int i = left; int j = right; //分区操作 while (i < j ) { while (i < pivotIndex && sortList.get(i).compareTo(pivot) <= 0) { i ++; } Util.swap(this.sortList, i, pivotIndex); pivotIndex = i; while(pivotIndex < j && sortList.get(j).compareTo(pivot) > 0){ j --; } Util.swap(this.sortList, j, pivotIndex); pivotIndex = j; } sort(left, pivotIndex - 1); sort(pivotIndex + 1, right); } public void print(){ System.out.println(this.sortList); } public static void main(String[] args) { int[] data = new int[] {5,8,1,20,15,13,7,6,30,45,3}; List<SortElement> lists = new ArrayList<SortElement>(); for (int d : data) { lists.add(new NumSortElement(d,"")); } QuickSort sort = new QuickSort(lists); sort.print(); sort.sort(); sort.print(); } }
以上是我自己实现的排序,教科书上可不是这么写的
package com.longshine.arthmetic.sort; import java.util.ArrayList; import java.util.List; import com.longshine.arthmetic.Util; public class NormalQuickSort { private List<SortElement> sortList; public NormalQuickSort(List<SortElement> sortList) { this.sortList = sortList; } public void sort() { sort(0, sortList.size() - 1); } private void sort(int left, int right) { if (left >= right ) return; SortElement pivot = sortList.get(left); int i = left; int j = right; //分区操作 while (i < j ) { while (i < j && sortList.get(j).compareTo(pivot) >= 0){ j --; } Util.swap(this.sortList, i, j); while (i < j && sortList.get(i).compareTo(pivot) <= 0) { i ++; } Util.swap(this.sortList, i, j); } this.print(); sort(left, i - 1); sort(i + 1, right); } public void print(){ System.out.println(this.sortList); } public static void main(String[] args) { int[] data = new int[] {5,8,1,20,15,13,7,6,30,45,3}; List<SortElement> lists = new ArrayList<SortElement>(); for (int d : data) { lists.add(new NumSortElement(d,"")); } NormalQuickSort sort = new NormalQuickSort(lists); sort.print(); sort.sort(); sort.print(); } }
不一样的地方是分区操作部分,但我那样的也可以将数列分成两相部分
另一样分区算法:原地分区(In-Place)
public static int partition(int[] data, int left, int right) { // i为小于等于A[q]数组的最大下标 int i = left - 1; int key = data[right]; for (int j = left; j <= right; j++) { if (data[j] <= key) { i++; Util.swap(data, i, j); } } return i; }
完整代码:
package com.longshine.arthmetic.sort; import com.longshine.arthmetic.Util; public class QuickSort2 { public static void main(String[] args) { int[] a = { 5, 8, 1, 20, 15, 13, 7, 6, 30, 45, 3 }; quickSort(a, 0, a.length - 1); Util.printArray(a); } public static void quickSort(int[] data, int left, int right) { if (left < right) { // 进行分组 int q = partition(data, left, right); // 对剩下的两组迭代分组 if (q - 1 >= 0) { quickSort(data, left, q - 1); quickSort(data, q + 1, right); } } } /** * 分区方法,将数组A[p..r]划分为两个可能为空的子数组A[p..q-1]和A[q+1..r], * 使得A[p..q-1]中的每个元素都小于等于A(q),而且小于等于A[q+1..r]中的元素 * * @param a * 要划分的数组 * @param p * 开始索引 * @param r * 结束索引 * @return 关键字A(q)的索引值q */ public static int partition(int[] data, int left, int right) { // i为小于等于A[q]数组的最大下标 int i = left - 1; int key = data[right]; for (int j = left; j <= right; j++) { if (data[j] <= key) { i++; Util.swap(data, i, j); } } return 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 * @
快速排序算法是当前使用最多的排序算法之一,它的基本思想是分治法,选择一个划分元,将小于划分元的元素放在左边,将大于划分元的元素放在右边,针对左右子序列重复此过程,直到序列为空或者只有一个元素,这是基本...