for spend some off hours, I decide to study some algorithm, the arithmetic of sort is a good choice. since sort algorithm bring forwand long time ago. but it's alway found the more efficienty method.
first, basic algorithm: bubble, insert, selection. just apply array to compare value between 2 number.
second, mergesort. apply recursive to separate split problem.
third, quick, find a middle value as "pivot", and split all value by pivot. and then recursive pivot, split, it's high-efficient sort algorithm.
other..., I will study it when I'm in dawdle. haha
package algorithm.sort;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
/**
* quick sort algorithm<br />
* 1. select a element as "pivot"<br />
* 2. re-sort all element, all the element that less than pivot replace to front,<br />
* all the element that more than pivot replace to the back,<br />
* and set the pivot to middle, these action called by "partition" operate<br />
* 3. recursive, process less array and greater array
* @author YS
*/
public class QuickSort {
/**
* implement by myself, implement the original concept whick get from wiki,<br />
* need extra space for store
* @param param
*/
public static void sort_implement_myself(Float[] param){
System.out.println(Arrays.toString(param));
int len=param.length;
if(len<=1)
return;
//get pivot
int middle=len/2;
float pivot=param[middle];
List<Float> l1=new LinkedList<Float>();
List<Float> l2=new LinkedList<Float>();
for(int i=0;i<len/2;i++){
if(param[i]<pivot)
l1.add(param[i]);
else
l2.add(param[i]);
}
for(int i=len/2+1;i<len;i++){
if(param[i]<pivot)
l1.add(param[i]);
else
l2.add(param[i]);
}
Float[] f1=l1.toArray(new Float[0]);
Float[] f2=l2.toArray(new Float[0]);
sort_implement_myself(f1);
sort_implement_myself(f2);
List<Float> l=new LinkedList<Float>();
l.addAll(Arrays.asList(f1));
l.add(pivot);
l.addAll(Arrays.asList(f2));
param=l.toArray(param);
}
/**
* quick sort with inplace
* @param param
* @param start
* @param last
*/
public static void sort_inplace_implement_myself(float[] param, int start, int last){
float pivot=param[last];
int i=start, j=last-1, middle=(last+start)/2;
for(;i<middle;i++){
if(param[i]>pivot){
for(;j>=middle;j--){
if(param[j]<param[i]){
float tmp=param[i];
param[i]=param[j];
param[j]=tmp;
break;
}
}
}
}
if(param[last]<param[middle]){
param[last]=param[middle];
param[middle]=pivot;
}
int flag=last-start+1;
if(flag>=3){
sort_inplace_implement_myself(param, 0, middle);
sort_inplace_implement_myself(param, middle+1, last);
}
}
public static void main(String[] args) {
float[] param={1, 8, 4, 3, 7, 5, 6, 8, 9, 2, 5, 3, 1, 8, 7, 3, 6};
// float[] param={1,2,4,7,5,3};
Float[] f=new Float[param.length];
for(int i=0;i<param.length;i++){
f[i]=Float.valueOf(param[i]);
}
sort_inplace_implement_myself(param, 0, param.length-1);
System.out.println(Arrays.toString(param));
}
}
分享到:
相关推荐
jcifs_java_implement_cifs jcifs_java_implement_cifs jcifs_java_implement_cifs jcifs_java_implement_cifs jcifs_java_implement_cifs jcifs_java_implement_cifs
While most C programmers use APIs and the libraries that implement them in almost every application they write, relatively few programmers create and disseminate new, widely applicable APIs....
Planing to Implement Service Management
7.4.1 Packet Tracer - Implement DHCPv4 Cisco Packet Tracer 思科模拟器 正确答案文件 由于程序问题无法保存激活DHCP端口配置 另加满分步骤截图 可直接上交正确答案文件 本答案版权归mewhaku所有,严禁再次...
1.6.1 Packet Tracer - Implement a Small Network Cisco Packet Tracer 思科模拟器 正确答案文件 可直接上交正确答案文件 本答案版权归mewhaku所有,严禁再次转载!!! Copyright @mewhaku 2022 All Rights ...
Java中extend与implement区别.doc
3.6.1 Packet Tracer - Implement VLANs and Trunking Cisco Packet Tracer 思科模拟器 正确答案文件 可直接上交正确答案文件 本答案版权归mewhaku所有,严禁再次转载!!! Copyright @mewhaku 2022 All Rights ...
By the end of this book, you should be ready to implement advanced, effective and efficient CNN models at your professional project or personal initiatives by working on complex image and video ...
6.4.1 Packet Tracer - Implement Etherchannel Cisco Packet Tracer 思科模拟器 正确答案文件 可直接上交正确答案文件 本答案版权归mewhaku所有,严禁再次转载!!! Copyright @mewhaku 2022 All Rights ...
C++ 针对 文件 操作 英文习题 Read the content of a file, and output to the screen. Every time after output 10 lines, ask users if they want to stop the program.
非完美pdf版本,但是可以看 非完美pdf版本,但是可以看
BI Design and implementation, BI Design and implementation, BI Design and implementation, BI Design and implementation,
Implement with Class and Collection a List Collection with add and remove data elements.
eclipse implementor 插件
一本操作系统领域的经典经典教程,英文版的,享受吧
Teradata Cookbook Over 85 recipes to implement efficient data warehousing solutions 英文epub 本资源转载自网络,如有侵权,请联系上传者或csdn删除 查看此书详细信息请在美国亚马逊官网搜索此书
SELinux_System_Administration_Implement_mandatory_access_control.epub
R Data Mining Implement data mining techniques through practical use cases and real world datasets 英文mobi 本资源转载自网络,如有侵权,请联系上传者或csdn删除 查看此书详细信息请在美国亚马逊官网搜索...
Joins in Hadoop has always been a problem for its users: the Map/Reduce framework seems to be specifically designed for group-by aggregation tasks rather than across-table op- erations;...
Design_and_Implement_Any_Filter_in_Less_than_60_Seconds