七星彩网投网站建设,建设环境工程技术中心网站,网站关闭公告代码,h5页面网站模板提供了以下排序#xff1a; 冒泡排序选择排序插入排序希尔排序快速排序归并排序桶排序堆排序package com.xingej.algorithm.sort;import java.util.ArrayList;
import java.util.Collections;/*** 排序工具类* * author erjun 2017年12月13日 上午8:38:22*/public class SortU… 提供了以下排序 冒泡排序选择排序插入排序希尔排序快速排序归并排序桶排序堆排序 package com.xingej.algorithm.sort;import java.util.ArrayList;
import java.util.Collections;/*** 排序工具类* * author erjun 2017年12月13日 上午8:38:22*/public class SortUtils {// 私有构造器禁止外界创建对象private SortUtils() {}// --------1、冒泡排序------/*** * 冒泡排序核心1、从数组的最后一个元素开始比较2、两两比较满足条件的话就需要进行位置的互换* * 实际生活中小学时需要根据身高进行座位排序就可以使用冒泡排序进行。* */public static void bubbleSort(int[] arr) {int temp;// 4 3 2 1按冒泡排序的话需要进行3轮比较可以了for (int i 0; i arr.length - 1; i) {// 每一轮比较找出本轮的最小值for (int j arr.length - 1; j i; j--) {// 后面的/下面的水泡 小于 上面的水泡就移位if (arr[j] arr[j - 1]) {// java 是引用传递temp arr[j];arr[j] arr[j - 1];arr[j - 1] temp;}}}}// --------2、选择排序------/*** * 选择排序的核心:* * 扫描所有的元素得到最小的元素并将最小的元素与左边第一个元素进行交换。再次扫描除* * 第一位置的所有元素得到最小的元素与左边第二个元素进行交换。依次类推* * 选择排序是建立在冒泡排序的基础之上的* * 冒泡排序的缺点每一轮交换的次数太多了为了解决这个问题出现选择排序* * 解决思路很明显既然冒泡排序每一轮的交换次数太多那就每一轮最多交换依次就是说每一轮只将最小值* * 找出来进行交换* * 按照这个思路去写选择排序* */public static void selectSort(int[] arr) {int minIndex 0; // 每次两两比较时如ab那么minIndex就是b的下标int value;for (int i 0; i arr.length - 1; i) {minIndex i;value arr[minIndex]; // 每一轮未排序元素的第一个值// 这个for每一次都会找出未排序元素的最小下标for (int j i 1; j arr.length; j) {if (arr[minIndex] arr[j]) {minIndex j;// 将最小下标赋值给minIndex}}// 将最小值与第一个元素进行交换arr[i] arr[minIndex];arr[minIndex] value;}}// --------3、插入排序------/*** 插入排序的思想跟冒泡排序和选择排序不同* * 使用场景很像打牌时每抓到一个张牌按照大小插入到已经排序好的牌里* * 实际应用场景有排序好的元素还有一些未排序的元素这个时候可以考虑插入排序* * 其实将待排序的元素插入到已经排序好的元素时* * 可以使用别的排序方法来进行不必循序查询比较排序可以使用快速排序* * param arr*/public static void insertSort(int[] arr) {// right表示未排序的元素for (int right 1; right arr.length; right) {int temp arr[right]; // 做备份int left right - 1;// left 表示 左边已经排序好的元素// 比方说左边已经排序好的元素有 1 2 4 6// 待排序元素为3// 将3依次跟6,4,2,1进行比较直到找到合适的位置// 也就是找到合适的数组下标leftwhile (left 0 arr[left] temp) {arr[left 1] arr[left];left--;}// 为什么left1呢// 因为上面的while循环中left 减 1 之后 不满足循环条件的// 因此需要将temp值放到left1的位置上去arr[left 1] temp;}}// --------4、希尔排序------public static void shellSort(int[] arr) {int left; // 左边下标表示已经排序好的元素int right; // 右边下标表示待排序元素/就是没有排序的元素int temp; // 临时存储int h 1; // 初始间隔为1// 计算最大间隔while (h arr.length / 3) {h 3 * h 1;}while (h 0) {// 表示循环待排序的元素for (right h; right arr.length; right) {temp arr[right]; // 先将待排序的元素进行缓存一下left right; //// 为什么是lefth-1,// 目前我认为是保证arr[left-h] 得有值不能为空或者说报空指针异常吧while (left h - 1 arr[left - h] temp) {arr[left] arr[left - h];left left - h;}// 这里千万不要写成下面的形式, 不能再left-h因为上面的while()循环已经减去了// arr[left - h] temp;arr[left] temp;}// 重新调整排序间隔h (h - 1) / 3;}}// --------5、快速排序------public static void quickSort(int arr[]) {recQuickSort(arr, 0, arr.length - 1);}// 使用递归和划分技术进行快速排序private static void recQuickSort(int arr[], int left, int right) {int size right - left 1;if (size 10) {insertSort(arr, left, right);} else {int median medianof3(arr, left, right);int partition partitionIt(arr, left, right, median);recQuickSort(arr, left, partition - 1);recQuickSort(arr, partition 1, right);}}// 划分方法返回分割点的索引private static int partitionIt(int arr[], int left, int right, int pivot) {int leftPtr left;int rightPtr right - 1;while (true) {// 从左往右找大于特定值的while (arr[leftPtr] pivot); // 循环结束就代表找到一个大于特定值的数据项// 从右向左找小于特定值while (arr[--rightPtr] pivot);if (leftPtr rightPtr) {break; // 结束时leftPtr rightPtr} else {swap(arr, leftPtr, rightPtr); // 交换}}swap(arr, leftPtr, right - 1);return leftPtr;}// 找出中间值// 索引为leftright以及中间值的 进行排序private static int medianof3(int arr[], int left, int right) {int centerIndex (left right) / 2;if (arr[left] arr[centerIndex]) {swap(arr, left, centerIndex);}if (arr[left] arr[right]) {swap(arr, left, right);}if (arr[centerIndex] arr[right]) {swap(arr, centerIndex, right);}swap(arr, centerIndex, right - 1);return arr[right - 1];}private static void insertSort(int arr[], int left, int right) {int in, out;int temp; // 临时缓存待存储的元素for (out left 1; out right; out) {temp arr[out];in out;while (in left arr[in - 1] temp) {arr[in] arr[in - 1];in--;}arr[in] temp;}}private static void swap(int arr[], int left, int right) {int temp arr[left];arr[left] arr[right];arr[right] temp;}// --------6、归并排序------// 归并两个已经有序的数组// 首先将数组拆分成两部分左边做成有序的同样右边也做成有序的。// 将这两个有序的数组组合生成第3个有序的数组// 时间复杂度O(N*logN)// 缺点消耗内存public static void mergeSort(int arr[]) {// 生成临时的缓存数组用于临时排序int[] workSpace new int[arr.length];recMergeSort(arr, workSpace, 0, arr.length - 1);}// lowerBoundupperBound 全是数组下标private static void recMergeSort(int arr[], int workSpace[], int lowerBound, int upperBound) {if (lowerBound upperBound) {return;} else {int mid (lowerBound upperBound) / 2;// 递归前半部分recMergeSort(arr, workSpace, lowerBound, mid);// 递归后半部分recMergeSort(arr, workSpace, mid 1, upperBound);// 进行合并merge(arr, workSpace, lowerBound, mid 1, upperBound);}}/*** * param arr* 被排序的数组* param workSpace* 临时缓存进行排序的* param lowPtr* 前半部分最小下标* param highPtr* 后半部分最小下标* param upperBound* 后半部分最大下标*/private static void merge(int arr[], int workSpace[], int lowPtr, int highPtr, int upperBound) {int i 0;int lowerBound lowPtr;// 前半部分的最小下标进行缓存int mid highPtr - 1;int n upperBound - lowerBound 1;while (lowPtr mid highPtr upperBound) {if (arr[lowPtr] arr[highPtr]) {workSpace[i] arr[lowPtr];} else {workSpace[i] arr[highPtr];}}// 前半部分或者后半部分可能还存在未排序的元素需要写到workSpace里while (lowPtr mid) {workSpace[i] arr[lowPtr];}while (highPtr upperBound) {workSpace[i] arr[highPtr];}// 将排序好的元素数组workSpace重新赋值到arr数组里for (i 0; i n; i) {arr[lowerBound i] workSpace[i];}}// --------7、桶排序------/*** 使用场景* * 1、桶排序可使用于最大最小值相差较大的数据情况如{2,100,200,198,3,87}* * 2、被排序的数据元素最好分配均匀否则可能会导致数据都集中到一个桶中如{102,108,111,204,3000}* * 基本步骤* * 1.找出待排序数组中的最大值max、最小值min* * 2.我们使用 动态数组ArrayList 作为桶桶里放的元素也用 ArrayList存储。桶的数量为(max-min)/arr.length1* * 3.遍历数组 arr计算每个元素 arr[i] 放的桶* * 4.每个桶各自排序* * 5.遍历桶数组把排序好的元素放进输出数组* */public static void bucketSort(int arr[]) {int max Integer.MIN_VALUE; // 先赋值成最小值int min Integer.MAX_VALUE;// 一次循环将该数组的最大值最小值求出来for (int i 0; i arr.length; i) {max Math.max(max, arr[i]);min Math.min(min, arr[i]);}// 求桶数int bucketNum (max - min) / (arr.length) 1;// 初始化每个桶ArrayListArrayListInteger bucketArr new ArrayList();for (int i 0; i bucketNum; i) {bucketArr.add(new ArrayList());}// 遍历数组将每个元素放入桶中for (int i 0; i arr.length; i) {int bucketIndex (arr[i] - min) / (arr.length);bucketArr.get(bucketIndex).add(arr[i]);}// 对每个桶元素进行排序for (int i 0; i bucketArr.size(); i) {Collections.sort(bucketArr.get(i));}// 将已经排序好的元素重新赋值到arr数组里int j 0;// 遍历每个桶将每个桶的元素赋值到arr数组里for (int i 0; i bucketArr.size(); i) {ArrayListInteger arrayList bucketArr.get(i);for (Integer key : arrayList) {arr[j] key;}}}// --------8、堆排序------// 堆特点// 1、它是完全的二叉树除了树的最后一层节点不需要是满的其他的每一层从左到右都完全是满的// 2、它常常是用一个数组来实现堆的// 3、堆中的每一个节点都满足的条件是父节点的关键字要大于所有的子节点public static void heapSort(int arr[]) {int size arr.length;Heap heap new Heap(size);for (int i 0; i size; i) {Node node new Node(arr[i]);heap.insertAt(i, node);heap.incrementSize();// 数量递增}// 从最后一个元素的父节点开始向下调整一直到根// 调整完后就变成标准的堆了for (int j size / 2 - 1; j 0; j--) {heap.trickleDown(j);}// 通过循环删除最大项再把删除的数据数组中的指定的位置如从后往前方// 结果就是从小到大排序for (int j size - 1; j 0; j--) {Node biggestNode heap.remove();// 取出最大的数据项heap.insertAt(j, biggestNode);}System.out.println(----打印排序后的堆----);heap.displayArray();}// 堆排序// 堆是二叉树因此需要创建这个节点来存储数据// 堆的特点父节点的值要大于子节点左右子节点大小无关系不要求左子节点小于右子节点static class Node {private int iData;public Node(int key) {iData key;}public int getKey() {return iData;}public void setKey(int id) {iData id;}}// 创建堆static class Heap {private Node[] heapArray;private int maxSize;private int currentSize;public Heap(int mx) {maxSize mx;currentSize 0;heapArray new Node[maxSize];}public boolean isEmpty() {return currentSize 0;}// 插入指定的位置public void insertAt(int index, Node node) {heapArray[index] node;}public void incrementSize() {currentSize;}public Node remove() {Node root heapArray[0];heapArray[0] heapArray[--currentSize];// 把最后一个元素赋值到根元素上trickleDown(0);// 开始向下调整return root;}// 向下调整public void trickleDown(int index) {int largerChild;Node top heapArray[index];while (index currentSize / 2) {int leftChild 2 * index 1;int rightChild leftChild 1;if (rightChild currentSize heapArray[leftChild].getKey() heapArray[rightChild].getKey()) {largerChild rightChild;} else {largerChild leftChild;}if (top.getKey() heapArray[largerChild].getKey()) {break;}heapArray[index] heapArray[largerChild];index largerChild;}heapArray[index] top;}// 树状的方式显示堆public void displayHeap() {int nBlanks 32;int itemsPerRow 1;// 层数判断int column 0;int j 0;String dots -------------------------;System.out.println(dots dots);while (currentSize 0) {if (column 0) {for (int k 0; k nBlanks; k) {System.out.print( );}System.out.print(heapArray[j].getKey());if (j currentSize) {break;// 所有的数据项全部显示完毕了}if (column itemsPerRow) {nBlanks / 2;itemsPerRow * 2;column 0;System.out.println();} else {for (int k 0; k nBlanks * 2 - 2; k) {System.out.print( );}}}}System.out.println(\n dots dots);}// 以数组的方式来显示堆public void displayArray() {for (int j 0; j maxSize; j) {System.out.print(heapArray[j].getKey() );}System.out.println();}}
} 测试用例 package com.xingej.algorithm.sort;import org.junit.Before;
import org.junit.Test;public class SortTest {private int max 20;private int[] arr new int[max];// 初始化数组Beforepublic void initArray() {for (int i 0; i max; i) {arr[i] (int) (Math.random() * 100 1);}System.out.println(------排序前-----);show(arr);}// -----打印输出/*** 打印输出数组* * param arr*/private void show(int[] arr) {for (int i 0; i max; i) {System.out.print(arr[i] );}System.out.println();}// -----冒泡排序Testpublic void testByBubbleSort() {SortUtils.bubbleSort(arr);System.out.println(------排序后-----);show(arr);}// -----选择排序Testpublic void testBySelectionSort() {SortUtils.selectSort(arr);System.out.println(------排序后-----);show(arr);}// -----插入排序Testpublic void testByInsertSort() {SortUtils.insertSort(arr);System.out.println(------排序后-----);show(arr);}// -----希尔排序Testpublic void testByShellSort() {SortUtils.shellSort(arr);System.out.println(------排序后-----);show(arr);}// -----快速排序Testpublic void testByQuickSort() {SortUtils.quickSort(arr);System.out.println(------排序后-----);show(arr);}// -----归并排序Testpublic void testByMergeSort() {SortUtils.mergeSort(arr);System.out.println(------排序后-----);show(arr);}// -----桶排序Testpublic void testByBucketSort() {SortUtils.bucketSort(arr);System.out.println(------排序后-----);show(arr);}// -----堆排序,时间复杂度是O(logN)Testpublic void testByHeapSort() {SortUtils.heapSort(arr);}} 代码已经上传到了git上https://github.com/xej520/xingej-algorithm 本文转自故新51CTO博客原文链接 http://blog.51cto.com/xingej/2056881如需转载请自行联系原作者
