Java常用算法总结（转） - Hua暖风

• Z时代
• 2024-01-10
• 分类：综合

Java常用算法总结（转）

交换排序

冒泡排序

将最后一个元素与倒数第二个元素对比，如果最后一个元素比倒数第二个小，则交换两个元素的位置，再用倒数第二个元素与倒数第三个元数对比，直到比到第一个元素，这样经过第一趟排序后得到第一个最小元素。如此反复几过N（N=length-1）次后可得到排序结果。

Java代码 

1. package sort; 
2.  
3. import java.util.Comparator; 
4.  
5. /**
6. * 冒泡排序算法
7. * @author jzj
8. * @date 2009-12-9
9. *
10. * @param <E>
11. */ 
12. publicclass BubbleSort<E extends Comparable<E>> extends Sort<E> { 
13.  
14.     /**
15.      * 排序算法的实现，对数组中指定的元素进行排序
16.      * @param array 待排序的数组
17.      * @param from 从哪里开始排序
18.      * @param end 排到哪里
19.      * @param c 比较器
20.      */ 
21.     publicvoid sort(E[] array, int from, int end, Comparator<E> c) { 
22.         //需array.length - 1轮比较 
23.         for (int k = 1; k < end - from + 1; k++) { 
24.             //每轮循环中从最后一个元素开始向前起泡，直到i=k止，即i等于轮次止 
25.             for (int i = end - from; i >= k; i--) { 
26.                 //按照一种规则（后面元素不能小于前面元素）排序 
27.                 if (c.compare(array[i], array[i - 1]) < 0) { 
28.                     //如果后面元素小于了（当然是大于还是小于要看比较器实现了）前面的元素，则前后交换 
29.                     swap(array, i, i - 1); 
30.                 } 
31.             } 
32.         } 
33.     } 
34.  
35.     /**
36.     * 测试
37.     * @param args
38.     */ 
39.     publicstaticvoid main(String[] args) { 
40.         Integer[] intgArr = { 7, 2, 4, 3, 12, 1, 9, 6, 8, 5, 11, 10 }; 
41.         BubbleSort<Integer> sort = new BubbleSort<Integer>(); 
42.         BubbleSort.testSort(sort, intgArr); 
43.         BubbleSort.testSort(sort, null); 
44.     } 
45. } 

快速排序

快速排序采用了分治法的思想，把大的问题分解为同类型的小问题。 一般分如下步骤： 1）选择一个中枢元素（有很多选法，我的实现里使用第一个元素为中枢的简单方法） 2）以该中枢元素为基准点，将小于中枢的元素放在中枢后集合的前部分，比它大的在集合后部分，待集合基本排序完成后（此时前部分元素小于后部分元素），把中枢元素放在合适的位置。 3）根据中枢元素最后确定的位置，把数组分成三部分，左边的，右边的，枢纽元素自己，对左边的，右边的分别递归调用快速排序算法即可。
这里的重点与难点在于第二步，实现的方式有很多种，我这里实现了三种。 第一种实现（partition1方法）： 以第一个元素为中枢元素，在中枢元素后面集合中从前往后寻找第一个比中枢元素小的元素，并与第一个元素交换，然后从剩余的元素中寻找第二个比中枢元素小的 元素，并与第二位元素交换，这样直到所有小于中枢元素找完为止，并记下最后一次放置小于中枢的元素位置minIndex（即小于中枢与大于中枢的分界）， 并将中枢元素与minIndex位置元素互换，然后对中枢元素两边的序列进行同样的操作。 此种实现最为简洁，处理过程中不需要把中枢元素移来移去，只是在其它元素完成基本排序后（前部分小于后部分元素）再把中枢元素放置到适当的位置 第二种实现（partition2方法）： 以第一个元素为中枢元素，刚开始时使用低指针指向中枢元素。当中枢元素在低指针位置时，此时我们判断高指针指向的元素是否小于中枢元素，如果大于中枢元素 则高指针继续向头移动，如果小于则与中枢元素交换，此时中枢元素被移到了高指针位置；当中枢元素在高指针位置时，我们此时判断低指针指向的元素是否大于中 枢元素，如果小于中枢元素则低指针继续向尾移动，如果大于则与中枢元素交换，此时中枢元素又回到了低指针位置；这时是拿高还是低指针所指向的元素与中枢比 较时根据前面逻辑来处理，直到高低指针指向同一位置则完成一轮排序，然后再对中枢元素两边的序列进行同样的操作直到排序完成 此种实现逻辑比较好理解，中枢元素的永远在低指针或指针所指向的位置，每次找到需处理的元 素后，要与中枢交换，中枢就像皮球一样从这里踢到那里，又从那里踢到这里。但此种实现会频繁地交换中枢元素，性能可能不如第一种 第三种实现（partition3方法）： 此种方式与前两种方式不太一样，同时移动高低指针，低指针向尾找出大于等于中枢的元素，而高向头找出小于中枢的元素，待两者都找出后交换高低指针所指向的 元素，直到高低指针指向同一位置止，然后比较中枢与高低指针所指向的元素大小，如果中枢元素大，则直接与高低指针元素交换，如果中枢元素小于等于高低指针 元素，则中枢元素与高低指针前一元素交换，完成一轮比较，然后再对中枢元素两边的序列进行同样的操作直到排序完成

此种方式有点难度，在移动元素时要注意的是：与中枢相等的元素也要向集合后部移动，不然的话如[3,3,0,3,3]第一轮排序结果不准确，虽然最后结果 正确。当中枢后面的元素集合移动完成后，还得要把中枢元素放置在集合中的合适位置，这就需要找准集合中前部分与后部分的边界，最后只能把中枢元素与最后一 个小于中枢的元素进位置互换。但此种实现方式与第一种有点像，也不需要把中枢元素调来调去的，而是待后面集合排序完成后将中枢放入适当位置

Java代码 

1. package sort; 
2.  
3. import java.util.Arrays; 
4. import java.util.Comparator; 
5.  
6. /**
7. * 快速排序算法
8. * @author jzj
9. * @date 2009-12-9
10. *
11. * @param <E>
12. */ 
13. publicclass QuickSort<E extends Comparable<E>> extends Sort<E> { 
14.  
15.     /**
16.      * 排序算法的实现，对数组中指定的元素进行排序
17.      * @param array 待排序的数组
18.      * @param from 从哪里开始排序
19.      * @param end 排到哪里
20.      * @param c 比较器
21.      */ 
22.     publicvoid sort(E[] array, int from, int end, Comparator<E> c) { 
23.         quickSort(array, from, end, c); 
24.     } 
25.  
26.     /**
27.      * 递归快速排序实现
28.      * @param array 待排序数组
29.      * @param low 低指针
30.      * @param high 高指针
31.      * @param c 比较器
32.      */ 
33.     privatevoid quickSort(E[] array, int low, int high, Comparator<E> c) { 
34.         /*
35.          * 如果分区中的低指针小于高指针时循环；如果low=higth说明数组只有一个元素，无需再处理；
36.          * 如果low > higth，则说明上次枢纽元素的位置pivot就是low或者是higth，此种情况
37.          * 下分区不存，也不需处理
38.          */ 
39.         if (low < high) { 
40.             //对分区进行排序整理 
41.             int pivot = partition1(array, low, high, c); 
42.             /*
43.              * 以pivot为边界，把数组分成三部分[low, pivot - 1]、[pivot]、[pivot + 1, high]
44.              * 其中[pivot]为枢纽元素，不需处理，再对[low, pivot - 1]与[pivot + 1, high]
45.              * 各自进行分区排序整理与进一步分区
46.              */ 
47.             quickSort(array, low, pivot - 1, c); 
48.             quickSort(array, pivot + 1, high, c); 
49.         } 
50.  
51.     } 
52.  
53.     /**
54.      * 实现一
55.      *
56.      * @param array 待排序数组
57.      * @param low 低指针
58.      * @param high 高指针
59.      * @param c 比较器
60.      * @return int 调整后中枢位置
61.      */ 
62.     privateint partition1(E[] array, int low, int high, Comparator<E> c) { 
63.         E pivotElem = array[low];//以第一个元素为中枢元素 
64.         //从前向后依次指向比中枢元素小的元素，刚开始时指向中枢，也是小于与大小中枢的元素的分界点 
65.         int border = low; 
66.  
67.         /*
68.          * 在中枢元素后面的元素中查找小于中枢元素的所有元素，并依次从第二个位置从前往后存放
69.          * 注，这里最好使用i来移动，如果直接移动low的话，最后不知道数组的边界了，但后面需要
70.          * 知道数组的边界
71.          */ 
72.         for (int i = low + 1; i <= high; i++) { 
73.             //如果找到一个比中枢元素小的元素 
74.             if (c.compare(array[i], pivotElem) < 0) { 
75.                 swap(array, ++border, i);//border前移，表示有小于中枢元素的元素 
76.             } 
77.         } 
78.         /*
79.          * 如果border没有移动时说明说明后面的元素都比中枢元素要大，border与low相等，此时是
80.          * 同一位置交换，是否交换都没关系；当border移到了high时说明所有元素都小于中枢元素，此
81.          * 时将中枢元素与最后一个元素交换即可，即low与high进行交换，大的中枢元素移到了 序列最
82.          * 后；如果 low <minIndex< high，表 明中枢后面的元素前部分小于中枢元素，而后部分大于
83.          * 中枢元素，此时中枢元素与前部分数组中最后一个小于它的元素交换位置，使得中枢元素放置在
84.          * 正确的位置
85.          */ 
86.         swap(array, border, low); 
87.         return border; 
88.     } 
89.  
90.     /**
91.      * 实现二
92.      *
93.      * @param array 待排序数组
94.      * @param low 待排序区低指针
95.      * @param high 待排序区高指针
96.      * @param c 比较器
97.      * @return int 调整后中枢位置
98.      */ 
99.     privateint partition2(E[] array, int low, int high, Comparator<E> c) { 
100.         int pivot = low;//中枢元素位置，我们以第一个元素为中枢元素 
101.         //退出条件这里只可能是 low = high 
102.         while (true) { 
103.             if (pivot != high) {//如果中枢元素在低指针位置时，我们移动高指针 
104.                 //如果高指针元素小于中枢元素时，则与中枢元素交换 
105.                 if (c.compare(array[high], array[pivot]) < 0) { 
106.                     swap(array, high, pivot); 
107.                     //交换后中枢元素在高指针位置了 
108.                     pivot = high; 
109.                 } else {//如果未找到小于中枢元素，则高指针前移继续找 
110.                     high--; 
111.                 } 
112.             } else {//否则中枢元素在高指针位置 
113.                 //如果低指针元素大于中枢元素时，则与中枢元素交换 
114.                 if (c.compare(array[low], array[pivot]) > 0) { 
115.                     swap(array, low, pivot); 
116.                     //交换后中枢元素在低指针位置了 
117.                     pivot = low; 
118.                 } else {//如果未找到大于中枢元素，则低指针后移继续找 
119.                     low++; 
120.                 } 
121.             } 
122.             if (low == high) { 
123.                 break; 
124.             } 
125.         } 
126.         //返回中枢元素所在位置，以便下次分区 
127.         return pivot; 
128.     } 
129.  
130.     /**
131.      * 实现三
132.      *
133.      * @param array 待排序数组
134.      * @param low 待排序区低指针
135.      * @param high 待排序区高指针
136.      * @param c 比较器
137.      * @return int 调整后中枢位置
138.      */ 
139.     privateint partition3(E[] array, int low, int high, Comparator<E> c) { 
140.         int pivot = low;//中枢元素位置，我们以第一个元素为中枢元素 
141.         low++; 
142.         //----调整高低指针所指向的元素顺序，把小于中枢元素的移到前部分，大于中枢元素的移到后面部分 
143.         //退出条件这里只可能是 low = high 
144.  
145.         while (true) { 
146.             //如果高指针未超出低指针 
147.             while (low < high) { 
148.                 //如果低指针指向的元素大于或等于中枢元素时表示找到了，退出，注：等于时也要后移 
149.                 if (c.compare(array[low], array[pivot]) >= 0) { 
150.                     break; 
151.                 } else {//如果低指针指向的元素小于中枢元素时继续找 
152.                     low++; 
153.                 } 
154.             } 
155.  
156.             while (high > low) { 
157.                 //如果高指针指向的元素小于中枢元素时表示找到，退出 
158.                 if (c.compare(array[high], array[pivot]) < 0) { 
159.                     break; 
160.                 } else {//如果高指针指向的元素大于中枢元素时继续找 
161.                     high--; 
162.                 } 
163.             } 
164.             //退出上面循环时 low = high 
165.             if (low == high) { 
166.                 break; 
167.             } 
168.  
169.             swap(array, low, high); 
170.         } 
171.  
172.         //----高低指针所指向的元素排序完成后，还得要把中枢元素放到适当的位置 
173.         if (c.compare(array[pivot], array[low]) > 0) { 
174.             //如果退出循环时中枢元素大于了低指针或高指针元素时，中枢元素需与low元素交换 
175.             swap(array, low, pivot); 
176.             pivot = low; 
177.         } elseif (c.compare(array[pivot], array[low]) <= 0) { 
178.             swap(array, low - 1, pivot); 
179.             pivot = low - 1; 
180.         } 
181.  
182.         //返回中枢元素所在位置，以便下次分区 
183.         return pivot; 
184.     } 
185.  
186.     /**
187.     * 测试
188.     * @param args
189.     */ 
190.     publicstaticvoid main(String[] args) { 
191.         Integer[] intgArr = { 3, 1, 1, 1, 1, 1, 1 }; 
192.         QuickSort<Integer> sort = new QuickSort<Integer>(); 
193.         QuickSort.testSort(sort, intgArr); 
194.         QuickSort.testSort(sort, null); 
195.     } 
196. }  

归并排序

Java代码 

1. package sort; 
2.  
3. import java.lang.reflect.Array; 
4. import java.util.Comparator; 
5.  
6. /**
7. * 归并排序算法
8. * @author jzj
9. * @date 2009-12-11
10. *
11. * @param <E>
12. */ 
13. publicclass MergeSort<E extends Comparable<E>> extends Sort<E> { 
14.  
15.     /**
16.      * 排序算法的实现，对数组中指定的元素进行排序
17.      * @param array 待排序的数组
18.      * @param from 从哪里开始排序
19.      * @param end 排到哪里
20.      * @param c 比较器
21.      */ 
22.     publicvoid sort(E[] arr, int from, int end, Comparator<E> c) { 
23.         partition(arr, from, end, c); 
24.     } 
25.  
26.     /**
27.      * 递归划分数组
28.      * @param arr
29.      * @param from
30.      * @param end
31.      * @param c void
32.      */ 
33.     privatevoid partition(E[] arr, int from, int end, Comparator<E> c) { 
34.         //划分到数组只有一个元素时才不进行再划分 
35.         if (from < end) { 
36.             //从中间划分成两个数组 
37.             int mid = (from + end) / 2; 
38.             partition(arr, from, mid, c); 
39.             partition(arr, mid + 1, end, c); 
40.             //合并划分后的两个数组 
41.             merge(arr, from, end, mid, c); 
42.         } 
43.     } 
44.  
45.     /**
46.      * 数组合并，合并过程中对两部分数组进行排序
47.      * 前后两部分数组里是有序的
48.      * @param arr
49.      * @param from
50.      * @param end
51.      * @param mid
52.      * @param c void
53.      */ 
54.     privatevoid merge(E[] arr, int from, int end, int mid, Comparator<E> c) { 
55.         E[] tmpArr = (E[]) Array.newInstance(arr[0].getClass(), end - from + 1); 
56.         int tmpArrIndex = 0;//指向临时数组 
57.         int part1ArrIndex = from;//指向第一部分数组 
58.         int part2ArrIndex = mid + 1;//指向第二部分数组 
59.  
60.         //由于两部分数组里是有序的，所以每部分可以从第一个元素依次取到最后一个元素，再对两部分 
61.         //取出的元素进行比较。只要某部分数组元素取完后，退出循环 
62.         while ((part1ArrIndex <= mid) && (part2ArrIndex <= end)) { 
63.             //从两部分数组里各取一个进行比较，取最小一个并放入临时数组中 
64.             if (c.compare(arr[part1ArrIndex], arr[part2ArrIndex]) < 0) { 
65.                 //如果第一部分数组元素小，则将第一部分数组元素放入临时数组中，并且临时数组指针 
66.                 //tmpArrIndex下移一个以做好下次存储位置准备，前部分数组指针part1ArrIndex 
67.                 //也要下移一个以便下次取出下一个元素与后部分数组元素比较 
68.                 tmpArr[tmpArrIndex++] = arr[part1ArrIndex++]; 
69.             } else { 
70.                 //如果第二部分数组元素小，则将第二部分数组元素放入临时数组中 
71.                 tmpArr[tmpArrIndex++] = arr[part2ArrIndex++]; 
72.             } 
73.         } 
74.         //由于退出循环后，两部分数组中可能有一个数组元素还未处理完，所以需要额外的处理，当然不可 
75.         //能两部分数组都有未处理完的元素，所以下面两个循环最多只有一个会执行，并且都是大于已放入 
76.         //临时数组中的元素 
77.         while (part1ArrIndex <= mid) { 
78.             tmpArr[tmpArrIndex++] = arr[part1ArrIndex++]; 
79.         } 
80.         while (part2ArrIndex <= end) { 
81.             tmpArr[tmpArrIndex++] = arr[part2ArrIndex++]; 
82.         } 
83.  
84.         //最后把临时数组拷贝到源数组相同的位置 
85.         System.arraycopy(tmpArr, 0, arr, from, end - from + 1); 
86.     } 
87.  
88.     /**
89.      * 测试
90.      * @param args
91.      */ 
92.     publicstaticvoid main(String[] args) { 
93.         Integer[] intgArr = { 5, 9, 1, 4, 1, 2, 6, 3, 8, 0, 7 }; 
94.         MergeSort<Integer> insertSort = new MergeSort<Integer>(); 
95.         Sort.testSort(insertSort, intgArr); 
96.         Sort.testSort(insertSort, null); 
97.     } 
98. }  

基数排序

基数排序的主要思路是,将所有待比较数值(注意,必须是正整数)统一为同样的数位长度,数位较短的数前面补零. 然后, 从最低位开始, 依次进行一次稳定排序.这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列.

它的理论比较容易理解，但实现却有一点绕。

Java代码 

1. package sort; 
2.  
3. import java.util.Arrays; 
4.  
5. publicclass RadixSort { 
6.  
7.     /**
8.      * 取数x上的第d位数字
9.      * @param x 数
10.      * @param d 第几位，从低位到高位
11.      * @return
12.      */ 
13.     publicint digit(long x, long d) { 
14.  
15.         long pow = 1; 
16.         while (--d > 0) { 
17.             pow *= 10; 
18.         } 
19.         return (int) (x / pow % 10); 
20.     } 
21.  
22.     /**
23.      * 基数排序实现，以升序排序（下面程序中的位记录器count中，从第0个元素到第9个元素依次用来
24.      * 记录当前比较位是0的有多少个..是9的有多少个数，而降序时则从第0个元素到第9个元素依次用来
25.      * 记录当前比较位是9的有多少个..是0的有多少个数）
26.      * @param arr 待排序数组
27.      * @param digit 数组中最大数的位数
28.      * @return
29.      */ 
30.     publiclong[] radixSortAsc(long[] arr) { 
31.         //从低位往高位循环 
32.         for (int d = 1; d <= getMax(arr); d++) { 
33.             //临时数组，用来存放排序过程中的数据 
34.             long[] tmpArray = newlong[arr.length]; 
35.             //位记数器，从第0个元素到第9个元素依次用来记录当前比较位是0的有多少个..是9的有多少个数 
36.             int[] count = newint[10]; 
37.             //开始统计0有多少个，并存储在第0位，再统计1有多少个，并存储在第1位..依次统计到9有多少个 
38.             for (int i = 0; i < arr.length; i++) { 
39.                 count[digit(arr[i], d)] += 1; 
40.             } 
41.             /*
42.              * 比如某次经过上面统计后结果为：[0, 2, 3, 3, 0, 0, 0, 0, 0, 0]则经过下面计算后 结果为：
43.              * [0, 2, 5, 8, 8, 8, 8, 8, 8, 8]但实质上只有如下[0, 2, 5, 8, 0, 0, 0, 0, 0, 0]中
44.              * 非零数才用到，因为其他位不存在，它们分别表示如下：2表示比较位为1的元素可以存放在索引为1、0的
45.              * 位置，5表示比较位为2的元素可以存放在4、3、2三个(5-2=3)位置，8表示比较位为3的元素可以存放在
46.              * 7、6、5三个(8-5=3)位置
47.              */ 
48.             for (int i = 1; i < 10; i++) { 
49.                 count[i] += count[i - 1]; 
50.             } 
51.  
52.             /*
53.              * 注，这里只能从数组后往前循环，因为排序时还需保持以前的已排序好的 顺序，不应该打
54.              * 乱原来已排好的序，如果从前往后处理，则会把原来在前面会摆到后面去，因为在处理某个
55.              * 元素的位置时，位记数器是从大到到小（count[digit(arr[i], d)]--）的方式来处
56.              * 理的，即先存放索引大的元素，再存放索引小的元素，所以需从最后一个元素开始处理。
57.              * 如有这样的一个序列[212,213,312]，如果按照从第一个元素开始循环的话，经过第一轮
58.              * 后（个位）排序后，得到这样一个序列[312,212,213]，第一次好像没什么问题，但问题会
59.              * 从第二轮开始出现，第二轮排序后，会得到[213,212,312]，这样个位为3的元素本应该
60.              * 放在最后，但经过第二轮后却排在了前面了，所以出现了问题
61.              */ 
62.             for (int i = arr.length - 1; i >= 0; i--) {//只能从最后一个元素往前处理 
63.                 //for (int i = 0; i < arr.length; i++) {//不能从第一个元素开始循环 
64.                 tmpArray[count[digit(arr[i], d)] - 1] = arr[i]; 
65.                 count[digit(arr[i], d)]--; 
66.             } 
67.  
68.             System.arraycopy(tmpArray, 0, arr, 0, tmpArray.length); 
69.         } 
70.         return arr; 
71.     } 
72.  
73.     /**
74.      * 基数排序实现，以降序排序（下面程序中的位记录器count中，从第0个元素到第9个元素依次用来
75.      * 记录当前比较位是0的有多少个..是9的有多少个数，而降序时则从第0个元素到第9个元素依次用来
76.      * 记录当前比较位是9的有多少个..是0的有多少个数）
77.      * @param arr 待排序数组
78.      * @return
79.      */ 
80.     publiclong[] radixSortDesc(long[] arr) { 
81.         for (int d = 1; d <= getMax(arr); d++) { 
82.             long[] tmpArray = newlong[arr.length]; 
83.             //位记数器，从第0个元素到第9个元素依次用来记录当前比较位是9的有多少个..是0的有多少个数 
84.             int[] count = newint[10]; 
85.             //开始统计0有多少个，并存储在第9位，再统计1有多少个，并存储在第8位..依次统计 
86.             //到9有多少个，并存储在第0位 
87.             for (int i = 0; i < arr.length; i++) { 
88.                 count[9 - digit(arr[i], d)] += 1; 
89.             } 
90.  
91.             for (int i = 1; i < 10; i++) { 
92.                 count[i] += count[i - 1]; 
93.             } 
94.  
95.             for (int i = arr.length - 1; i >= 0; i--) { 
96.                 tmpArray[count[9 - digit(arr[i], d)] - 1] = arr[i]; 
97.                 count[9 - digit(arr[i], d)]--; 
98.             } 
99.  
100.             System.arraycopy(tmpArray, 0, arr, 0, tmpArray.length); 
101.         } 
102.         return arr; 
103.     } 
104.  
105.     privateint getMax(long[] array) { 
106.         int maxlIndex = 0; 
107.         for (int j = 1; j < array.length; j++) { 
108.             if (array[j] > array[maxlIndex]) { 
109.                 maxlIndex = j; 
110.             } 
111.         } 
112.         return String.valueOf(array[maxlIndex]).length(); 
113.     } 
114.  
115.     publicstaticvoid main(String[] args) { 
116.         long[] ary = newlong[] { 123, 321, 132, 212, 213, 312, 21, 223 }; 
117.         RadixSort rs = new RadixSort(); 
118.         System.out.println("升 - " + Arrays.toString(rs.radixSortAsc(ary))); 
119.  
120.         ary = newlong[] { 123, 321, 132, 212, 213, 312, 21, 223 }; 
121.         System.out.println("降 - " + Arrays.toString(rs.radixSortDesc(ary))); 
122.     } 
123. } 

时间复杂度与空间复杂度对比表

原文：http://jiangzhengjun.iteye.com/blog/547735

以上是 Java常用算法总结（转） - Hua暖风 的全部内容， 来源链接： utcz.com/z/394150.html