经典的排序算法java实现版
/**2*
3* @author yuzhiping
4* @version 1.0
5* 功能说明:计算机领域经典的算法
6*
7*/
8 public class sortAlgorithm<T extends Comparable<T>> {
9
10 //交换索引i和索引j的值
11 private void swap(T [] data ,int i,int j){
12 T tmp;
13 tmp=data;
14 data=data;
15 data=tmp;
16 }
17
18
19 //-----堆排序 时间复杂度O(nlogn)-----
20
21 public void heapSort(T [] data){
22 int arrayLength=data.length;
23 //循环件堆
24 for(int i=0;i<arrayLength-1;i++){
25 // 建堆
26 builMaxdHeap(data, arrayLength - 1 - i);
27 // 交换堆顶和最后一个元素
28 swap(data, 0, arrayLength - 1 - i);
29
30 }
31 }
32
33 // 对data数组从0到lastIndex建大顶堆
34 private void builMaxdHeap(T[] data, int lastIndex) {
35 // 从lastIndex处节点（最后一个节点）的父节点开始
36 for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
37 // k保存当前正在判断的节点
38 int k = i;
39 // 如果当前k节点的子节点存在
40 while (k * 2 + 1 <= lastIndex) {
41 // k节点的左子节点的索引
42 int biggerIndex = 2 * k + 1;
43 // 如果biggerIndex小于lastIndex，即biggerIndex + 1
44 // 代表的k节点的右子节点存在
45 if (biggerIndex < lastIndex) {
46 // 如果右子节点的值较大
47 if (data.compareTo(data) < 0) {
48 // biggerIndex总是记录较大子节点的索引
49 biggerIndex++;
50 }
51 }
52 // 如果k节点的值小于其较大子节点的值
53 if (data.compareTo(data) < 0) {
54 // 交换它们
55 swap(data, k, biggerIndex);
56 // 将biggerIndex赋给k，开始while循环的下一次循环，
57 // 重新保证k节点的值大于其左、右子节点的值。
58 k = biggerIndex;
59 } else {
60 break;
61 }
62 }
63 }
64 }
65
66 //-----冒泡排序法 时间复杂度O(n^2)-----
67 public void bubbleSort(T[] data){
68 int i,j;
69 for(i=0;i<data.length-1;i++){
70 for(j=0;j<data.length-i-1;j++){
71 if(data.compareTo(data) > 0){
72 swap(data,j+1,j);
73 }
74 }
75 }
76 }
77
78 //-----选择排序法 时间复杂度O(n^2)-----
79 public void selectSort(T[] data){
80 int i,j;
81
82 for(i=0;i<data.length-1;i++){
83 for(j=i+1;j<data.length;j++){
84 if (data.compareTo(data) > 0){
85 swap(data,i,j);
86 }
87 }
88 }
89 }
90
91 //-----快速排序法时间复杂度为O(log2n)-----
92 public void quickSort(T[] data){
93 subQuickSort(data,0,data.length-1);
94 }
95
96 private void subQuickSort(T[] data,int start,int end){
97 if( start < end ){
98 //以第一个元素作为分界值
99 T base = data;
100 //i从左边开始搜索大于分界值元素的索引
101 int i = start;
102 //j从右边开始搜索小于分界值元素的索引
103 int j = end + 1;
104 while(true){
105 //左边跳过比base小的元素
106 while(i < end && data[++i].compareTo(base) <= 0);
107 //右边跳过比base大的元素
108 while(j > start && data[--j].compareTo(base) >= 0);
109
110 if(j > i){
111 swap(data,i,j);
112 }else{
113 break;
114 }
115 }
116 //将分界值还原
117 swap(data,start,j);
118
119 //递归左边序列
120 subQuickSort(data,start,j-1);
121 //递归右边序列
122 subQuickSort(data,j+1,end);
123 }
124 }
125
126 //-----插入排序法 时间复杂度O(n^2)-----
127 public void insertSort(T[] data){
128 int arrayLength = data.length;
129
130 for(int i=1;i<arrayLength;i++){
131 //当整体后移时保证data的值不会丢失
132 T tmp = data;
133 //i索引处的值已经比前面所有值都大,表明已经有序,无需插入
134 //i-1处索引之前的数值已经有序,i-1处索引处元素的值也是最大值
135 if(data.compareTo(data) < 0){
136 int j = i-1;
137 //整体后移一个
138 while(j>=0 && data.compareTo(tmp) > 0){
139 data = data;
140 j--;
141 }
142 data = tmp;
143 }
144 }
145 }
146
147 //-----折半插入排序法 时间复杂度-----
148 public void binaryInsertSort(T[] data) {
149 int arrayLength = data.length;
150
151 for (int i = 1; i < arrayLength; i++) {
152 if (data.compareTo(data) > 0) {
153 // 缓存i处的元素值
154 T tmp = data;
155
156 // 记录搜索范围的左边界
157 int low = 0;
158 // 记录搜索范围的右边界
159 int high = i - 1;
160
161 while (high >= low) {
162 // 记录中间位置
163 int mid = (high + low) / 2;
164 // 比较中间位置数据和i处数据大小，以缩小搜索范围
165
166 if (tmp.compareTo(data) > 0) {
167 low = mid + 1;
168 } else {
169 high = mid - 1;
170 }
171 }
172 // 将low~i处数据整体向后移动1位
173 for (int j = i; j > low; j--) {
174 data = data;
175 }
176 data = tmp;
177
178 }
179 }
180 }
181
182 //-----希尔排序法 时间复杂度O(nlogn)O(n^2)具体看h的值-----
183 public void shellSort(T[] data){
184 int arrayLength = data.length;
185 //h保存可变增量
186
187 int h = 1;
188 while(h<=arrayLength/3){
189 h = h * 3 + 1;
190 }
191
192 while(h > 0){
193 //System.out.println(Arrays.toString( data )+"h="+h);
194
195 for(int i=h;i<arrayLength;i++){
196 //当整体后移时,保证data的值不丢失
197 T tmp = data;
198 //i索引处的值已经比前面所有的值大
199 //(i-1索引之前的值已经有序的,i-1索引处元素的值就是最大值)
200 if(data.compareTo(data) < 0){
201 int j = i-h;
202 //整体后移一格
203 while(j>=0 && data.compareTo(tmp) > 0){
204 data = data;
205 j-=h;
206 }
207
208 //最后将tmp值插入合适的位置
209 data = tmp;
210 }
211 }
212 h = (h-1)/3;
213 }
214
215 }
216
217 //-----归并排序法 时间复杂度为O(nlog2n)-----
218 public void mergeSort(T[] data){
219 subMergeSort(data,0,data.length-1);
220 }
221
222 private void subMergeSort(T[] data,int left,int right){
223 if(right > left){
224 //找出中间索引
225 //System.out.println(Arrays.toString(data) );
226 int center = (left + right)/2;
227 //对左边数组进行递归
228 subMergeSort(data,left,center);
229 //对右边数组进行递归
230 subMergeSort(data,center+1,right);
231 //合并
232 merge(data,left,center,right);
233 }
234 }
235
236 @SuppressWarnings("unchecked")
237 private void merge(T[] data, int left, int center, int right) {
238 Object[] tmpArr = new Object;
239 int mid = center + 1;
240 // third记录中间处索引
241 int third = left;
242 int tmp = left;
243
244 while (left <= center && mid <= right) {
245 // 从两个数组中取出最小的放入中间数组
246 if (data.compareTo(data) <= 0) {
247 tmpArr = data;
248 } else {
249 tmpArr = data;
250 }
251 }
252
253 // 剩余部分依次放入中间数组
254 while (mid <= right) {
255 tmpArr = data;
256 }
257 while (left <= center) {
258 tmpArr = data;
259 }
260
261 // 将中间数组的内容复制拷回原数组
262 // (原left~right范围内德内容被复制回原数组)
263 while (tmp <= right) {
264 data = (T) tmpArr;
265 }
266 }
267
268
269
270 public static void main(String[] args) {
271 // TODO Auto-generated method stub
272
273 }
274
275 }
页:
[1]