快速排序是一个
分治和递归的一个思想。
快速排序思想是折半查找,从最右边开始查找,找到一个比k值小的然后对换,再从左边开始查找,找到一个比k值大的,然后对换。继续循环就完成第一次排序。拿到返回的位置后,左右两边开始递归。
package quicksort;
import java.util.Arrays;
/**
* @author liyu
*
*/
public class Sort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int arr[] = {11, 2, 6, 15 , 16 ,8 ,9 ,3, 19, 20};
//int arr[] = {11, 2, 6, 15 , 16 ,8,8 ,9 ,3, 19, 20};
QuickSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
private static void QuickSort(int[] arr, int i, int j) {
// TODO Auto-generated method stub
int p = 0;
if(i<j){
p = partion(arr,i,j);
QuickSort(arr, p+1, j);
QuickSort(arr, i, p-1);
}
}
public static int partion(int[] arr,int i, int j){
//11 2 6 15 16 8 9 3 19 20 --->11 |3 2 6 15 16 8 9 _ 19 20 ----> 11 |3 2 6 _ 16 8 9 15 19 20-->11 |3 2 6 9 16 8 _ 15 19 20
//-->11 |3 2 6 9 _ 8 16 15 19 20-->11 |3 2 6 9 8 11 16 15 19 20
int k = arr[i];
while(i<j){
//从右边边开始寻找一个比k小的值
while (i<j&&arr[j]>=k) j--;
//找到比k小的值后替换位置
arr[i] = arr[j];
while(i<j&&arr[i]<k) i++;
arr[j] = arr[i];
}
arr[i] = k;
return i;
}
}
分享到:
相关推荐
最快的排序算法 谁才是最强的排序算法:快速排序-归并排序-堆排序,排序算法数据结构
快速排序 非递归实现方式的完整源代码和测试结果。
快速排序-flash演示 可自己输入数据.......
归并排序,排序等算法,数据结构,快速排序,链表排序归并排序,排序等算法,数据结构,快速排序,链表排序
典型排序算法的c语言实现
冒泡排序---选择,插入和快速排序 简单实用,非常棒的一个java工具类.
选择排序 冒泡排序 插入排序 合并排序 快速排序算法原理及代码实现 不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 当面临巨大数据量的排序的时候,还是优先选择合并排序算法和快速排序算法。...
算法-理论基础- 排序- 快速排序(包含源程序).rar
Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...
快速排序快速排序 快速排序 快速排序 快速排序 快速排序
快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序...快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序
procedure qsort(l,r:longint); var k,t,i,j:longint; begin k:=(l+r)div 2; t:=a[k]; i:=l; j:=r; repeat
多线程实现排序算法的比较:希尔排序、快速排序、堆排序。用java语言实现,很经典,需要的可以下载看看!
数据结构--快速排序C++源代码,自己编写调试,代码简单易懂,不长
算法设计与分析课程,算法实验报告,基于python。涉及快速排序及其改进算法:三路快排。设置"重复率的参数",通过实验可以看到,重复率越高,改进性能越好。
各种排序算法,包括希尔算法,快速排序,堆排序-A variety of sorting algorithms, including the Hill algorithm, quick sort, heap sort
实验内容及要求: 输入n个整数,分别用希尔排序、快速排序、堆排序和归并排序实现由小到大排序并输出排序结果。要求n=10,15,20进行三组排序实验。 实验目的:掌握希尔排序、快速排序、堆排序、归并排序算法。
java代码-快速排序-----
java代码-使用java解决java排序之-快速排序的问题的源代码 ——学习参考资料:仅用于个人学习使用!
快速排序算法c语言