文章目錄

• 計(jì)數(shù)排序
• • java代碼實(shí)現(xiàn)
  • 單元測試
• 桶排序
• • java代碼實(shí)現(xiàn)
  • 單元測試

計(jì)數(shù)排序

java代碼實(shí)現(xiàn)

package csdn.dreamzuora.sort;import java.util.List;/*** Title: 抽象出排序類* Description:** @version 1.0* @author: weijie* @date: 2020/10/22 17:59*/ public abstract class Sort<E> {public void sort(List<E> array){};public void sort(List<E> array, int left, int right){};} package csdn.dreamzuora.sort;import java.util.ArrayList; import java.util.List;/*** Title: 計(jì)數(shù)排序* Description:* 思想：犧牲空間換取時間 計(jì)數(shù)排序需要占用大量空間，它僅適用于數(shù)據(jù)比較集中的情況* @version 1.0* @author: weijie* @date: 2020/10/26 23:30*/ public class CountSort extends Sort<Integer> {@Overridepublic void sort(List<Integer> array) {int size = array.size();Integer max = array.get(0);Integer min = array.get(0);//找出最大值，最小值for (int i = 1; i < size; i++){Integer val = array.get(i);if (max < val){max = val;}if (min > val){min = val;}}//計(jì)算空間占用int len = max - min;//數(shù)值偏移量int offset = min;//利用最大值和最小值分配空間int [] tempList = new int[len + 1];for (int i = 0; i < size; i++){Integer val = array.get(i) - offset;Integer count = tempList[val];if (count == null){count = 0;}tempList[val] = ++count;}int k = 0;for (int i = 0; i < len; i++){Integer count = tempList[i];if (count != null){while (count != 0){array.set(k++, i + offset);count --;}}}} }

單元測試

package csdn.dreamzuora.sort;import org.junit.Test; import org.junit.jupiter.api.Assertions;import java.util.Arrays; import java.util.List;import static org.junit.Assert.*;/*** Title:* Description:** @version 1.0* @author: weijie* @date: 2020/10/27 12:12*/ public class CountSortTest {@Testpublic void sort() {CountSort countSort = new CountSort();List<Integer> list = Arrays.asList(4, 8, 4, 6, 2, 10);List<Integer> expectList = Arrays.asList(2, 4, 4, 6, 8, 10);countSort.sort(list);Assertions.assertEquals(expectList, list);} }

桶排序

java代碼實(shí)現(xiàn)

package csdn.dreamzuora.sort;import java.util.ArrayList; import java.util.Collections; import java.util.LinkedList; import java.util.List;/*** Title: 桶排序* Description: 注意和計(jì)數(shù)排序區(qū)別* 桶排序可用于最大最小值相差較大的數(shù)據(jù)情況，比如[9012,19702,39867,68957,83556,102456]。** 思想：把數(shù)組 arr 劃分為n個大小相同子區(qū)間（桶），每個子區(qū)間各自排序，最后合并* 計(jì)數(shù)排序是桶排序的一種特殊情況** @url:https://www.cnblogs.com/qq1452753919/p/10506114.html** @version 1.0* @author: weijie* @date: 2020/10/22 17:52*/ public class BucketSort extends Sort<Integer>{@Overridepublic void sort(List<Integer> array) {if (array == null || array.isEmpty()){return;}int max = array.get(0);int min = array.get(0);int size = array.size();for (int i = 0; i < size; i++){max = Math.max(array.get(i), max);min = Math.min(array.get(i), min);}int offset = max - min;int bucketSize = (max - min) / size + 1;List<LinkedList<Integer>> bucketList = new ArrayList<>(bucketSize);//桶初始化for (int i = 0; i < bucketSize; i++){bucketList.add(new LinkedList<>());}//將每個元素放入桶中for (int i= 0; i < size; i++){int val = array.get(i);// 3 17 20 48 45/5=9+1=10int num = (array.get(i) - min) * (bucketSize - 1) / offset;bucketList.get(num).add(val);}List<Integer> sortList = new ArrayList<>();//對每個桶進(jìn)行排序for (int i = 0; i < bucketSize; i++){Collections.sort(bucketList.get(i));}//輸出全部元素int index = 0;for (LinkedList<Integer> itemList : bucketList){for (Integer val : itemList){sortList.set(index++ , val);}}} }

單元測試

package csdn.dreamzuora.sort;import org.junit.Test; import org.junit.jupiter.api.Assertions;import java.util.*;import static org.junit.Assert.*;/*** Title:* Description:** @version 1.0* @author: weijie* @date: 2020/10/27 23:45*/ public class BucketSortTest {BubbleSort bubbleSort = new BubbleSort();@Testpublic void sort() {List<Integer> list = Arrays.asList(4, 8, 4, 6, 2, 10);List<Integer> expectList = Arrays.asList(2, 4, 4, 6, 8, 10);bubbleSort.sort(list);Assertions.assertEquals(expectList, list);}@Testpublic void sort2() {Random random = new Random();List<Integer> actuallyList = Arrays.asList(random.nextInt(100), random.nextInt(100), random.nextInt(100), random.nextInt(100), random.nextInt(100), random.nextInt(100));List<Integer> expectList = new ArrayList<>(actuallyList);Collections.sort(expectList);bubbleSort.sort(actuallyList);Assertions.assertEquals(expectList, actuallyList);} }

總結(jié)

以上是生活随笔為你收集整理的计数排序和桶排序 java代码实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。