排序算法,快速排序与冒泡排序

用java实现排序算法.

在算法的实现过程中是用的ArrayList.从该类的实现方面来看,对算法的执行效率也是有影响的.在这里仅仅记录以下自己的学习过程及结果.

1,快速排序

代码的实现如下,该类是一个测试类方法 quickSortMethod()就是快速排序的实现,他的实现使用的是一个递归算法,

ArrayList的实现是一个数组,而且数组的大小是10,如果元素大于10个就会申请新的空间,大小为原来的1.5倍, int newCapacity = oldCapacity + (oldCapacity >> 1);从底层的代码可以看出他为了提高效率使用移位来提高效率.

为了进可能的减少arrayList的数据机构的影响,这里使用foreach遍历数组.由于这里测试的数据比较大,而ArrayLIst的初始大小为10,而且每次增长为原来的二倍,让后把旧的数据复制到新的数组里面.

总之这样来写一个算法多少是有些影响的.

 1 package com.test.sort;
 2 
 3 import java.util.ArrayList;
 4 import java.util.Arrays;
 5 import java.util.List;
 6 
 7 public class QuickSort {
 8 
 9     public List quickSortMethod(List<Integer> parentList){//quickSort
10         List<Integer> leftList = new ArrayList<Integer>();
11         List<Integer> rightList = new ArrayList<Integer>();
12         List<Integer> resultList ;
13         if (parentList.size() <= 1) {
14             return parentList;
15         }
16         Integer qInteger = parentList.get(0);
17         Boolean first = true;
18         for (Integer temp : parentList) {
19             if(first) {
20                 first = !first;
21                 continue;
22             }
23             if (temp > qInteger) {
24                 rightList.add(temp);
25             }else {
26                 leftList.add(temp);
27             }
28             
29         }
30         resultList = this.quickSortMethod(leftList);
31         resultList.add(qInteger);
32         resultList.addAll(this.quickSortMethod(rightList));
33         return resultList;   
35     }
36     
37     public static void main(String[] args) {
38         List<Integer> results;
39         QuickSort qSort = new QuickSort();
40         List<Integer> list = new ArrayList();
41         int elemCount = 100000;
42         for(int i = 0; i<elemCount; i++) {
43             list.add((int) (Math.random()*elemCount));
44         }
45         Long startTime = System.currentTimeMillis();
46         results = qSort.quickSortMethod(list);
47         Long endTime = System.currentTimeMillis();
48         Long totalTime =  endTime - startTime;
49         System.out.println(startTime);
50         System.out.println(endTime);
51         System.out.println("quick Sort Time = " + totalTime );
52         //qSort.log(results);
53         
54         //bubble Sort
55         startTime = System.currentTimeMillis();
56         results = qSort.bubbleSort(list);
57         endTime = System.currentTimeMillis();
58         totalTime =  endTime - startTime;
59         System.out.println(startTime);
60         System.out.println(endTime);
61         System.out.println("dubble sort Time = " + totalTime );
62         //qSort.log(results);        
63     }
64     
65     
66     public List bubbleSort(List<Integer> parentList) {
67         if (parentList == null || parentList.size() == 0) {
68             System.err.println("List isn't elem");
69             return null;
70         }
71         
72         for (int i = 0,listSize = parentList.size(); i < listSize; i++) {
73             for(int j = 0; j < listSize - i - 1; j++){
74                 if (parentList.get(j) > parentList.get(j+1)) {
75                     int temp = parentList.get(j);
76                     parentList.set(j, parentList.get(j+1));
77                     parentList.set(j+1, temp);
78                 }
79             }
80         }
81         return parentList;
82     }
83     
84     public void log(List<Integer> parentList){
85         for (Integer  elem: parentList) {
86             System.out.println(elem);
87         }
88         System.out.println("==================================");
89     }
90 }

2 冒泡排序.

冒泡的排序算法 bubbleSort(),这个算法的实现是通过两层循环来实现的.这个算法ArrayList通过api get来得到一个元素,foreach代码会被编译为 Iterator 的形式来迭代.当list是数组的时候差别不大.当List的结构是链表的时候就差别打了.

3 运行结果.

以上的这些仅仅是学习中的笔记

排序算法,快速排序与冒泡排序

用java实现排序算法.

推荐阅读