快速排序 采用了数组排序和 list集合排序 两种方式，其中 以num 来排序处理。
import java.util.ArrayList;
import java.util.List;
public class QuickSortTest {
/* 测试的入口 未完待续*/
public static void main(String[] args) {
QuickBean q1 = new QuickBean(25, "哈哈");
QuickBean q2 = new QuickBean(2, "哈哈1");
QuickBean q3 = new QuickBean(89, "哈哈2");
QuickBean q4 = new QuickBean(-5, "哈哈0");
QuickBean q5 = new QuickBean(28, "哈哈3");
QuickBean q6 = new QuickBean(0, "哈哈4");
QuickBean q7 = new QuickBean(25, "哈哈");
QuickBean[] ss = {q1, q2, q3, q4, q5, q6};//获取一个数组
FastSort(ss,0,5);
for (int i = 0; i < ss.length; i++) {
System.out.println(ss[i].toString());
}
List<QuickBean> list=new ArrayList<>();
list.add(q1);
list.add(q2);
list.add(q3);
list.add(q4);
list.add(q5);
list.add(q6);
list.add(q7);
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i).toString());
}
FastSortList(list,0,6);
System.out.println("\n \n \n\n");
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i).toString());
}
}
public static void setValue(StringBuilder str){
str = new StringBuilder("sss111");
}
public static void setValue2(StringBuilder str){
str.append("sss222");
}
public static void setValue(String ss){
ss="adfasdfa";
}
public static void setValueInt(int ss){
ss=8888;
}
public static class QuickBean {
int qucikNum;//定义一个数据
String name;//名称
public QuickBean(int qucikNum, String name) {
this.qucikNum = qucikNum;
this.name = name;
}
@Override
public String toString() {
return "QuickBean{" +
"qucikNum=" + qucikNum +
", name='" + name + '\'' +
'}';
}
public int getQucikNum() {
return qucikNum;
}
public void setQucikNum(int qucikNum) {
this.qucikNum = qucikNum;
}
}
public static void FastSortList( List<QuickBean> list, int low, int high) {
if (low > high) {
return;
}
int start = low;
int end = high;
QuickBean qb;
while (start != end) {
//顺序很重要，要从右边开始找
while (list.get(end).qucikNum >=list.get(low).qucikNum && start < end) {
end--;
}
while (list.get(start).qucikNum <= list.get(low).qucikNum && start < end) {
start++;
}
//交换
if (start < end) {
qb = list.get(start);
// list.add(start,list.get(end)) ;
// list.remove(start + 1);
// list.add(end,qb) ;
// list.remove(end + 1);
list.set(start,list.get(end));
list.set(end,qb);
}
}
//最终将基准数归位,将start 和 low 互换
qb = list.get(start);
// list.add(start,list.get(low)) ;
// list.remove(start + 1);
// list.add(low,qb) ;
// list.remove(low + 1);
list.set(start,list.get(low));
list.set(low,qb);
FastSortList( list,low, start-1);//继续处理左边的
FastSortList( list, start+1, high);//继续处理右边的
return;
}
public static void FastSort(QuickBean[] ss, int low, int high) {
if (low > high) {
return;
}
int start = low;
int end = high;
QuickBean qb;
while (start != end) {
//顺序很重要，要从右边开始找
while (ss[end].qucikNum >= ss[low].qucikNum && start < end) {
end--;
}
while (ss[start].qucikNum <= ss[low].qucikNum && start < end) {
start++;
}
//交换
if (start < end) {
qb = ss[start];
ss[start] = ss[end];
ss[end] = qb;
}
}
//最终将基准数归位,将start 和 low 互换
qb = ss[start];
ss[start] = ss[low];
ss[low] = qb;
FastSort( ss,low, start-1);//继续处理左边的
FastSort( ss, start+1, high);//继续处理右边的
return;
}
}
思考
- 为什么要从右向左排序?
将 快速排序的过程,一步一步实现的过程中发现,从小到大排序的过程中,前
期都是与排序要比较的值eg.要把A放在合适的位置,要让其左边比他小,右边
比他大.从两头开始比较,右边找小的值,左边找小的值( 条件:如果两个位置角
标左边比右边大),找到之后,两个互换位置,达到效果 :大的放在后面,小的放在
前面,最后会有一个比较的终点,就是 两边重合的时候.当最后一个位置需要和 排序的比较的值A比较,因为左边是小于A 的值,所以其一般要换位置,要找个小的值比较,所以从右边循环排序.如果找到大的值,其位置就会固定,不会进行互换.
考虑 一下情景 ,基准归位: 从右开始遍历 如果剩余一个是5(E),剩余两个是 5(E)6(R)
1.1 中间剩余两个值都相同 5,6 的位置(理解为角标),以及其对应的值 E R
两值会互换,5(R) 6(E)继续往下遍历,会找到5的值 和A互换,继续遍历
1.2 剩余一个小于A 的值
5(E),会走到5 的位置,E 和 A 互换值.
1.3 剩余一个大于A的值 5是大的值
4(C)5(E),会走到4 的位置,C 和 A 互换值.
1.4 两两交换,最后交换完了 5,6 互换完,会走到5 小的值那边
4(C)5(E)6(R),会走到5 的位置,E 和 A 互换值.
1.5 第一个是 最大的值
0(A) end(B), B 和A 互换值
1.6 第一个是最小的值
0(A) end(B), 会直接走到 A ,A 不换值
