【code】java兑现十种常见内部排序

【code】java实现十种常见内部排序

常见的内部排序：

import java.util.*;class DataWrap implements Comparable<DataWrap>{int data;String flag;public DataWrap(int data, String flag){this.data = data;this.flag = flag;}public String toString(){return data + flag;}public int compareTo(DataWrap dw){return this.data > dw.data ? 1 : (this.data == dw.data ? 0 : -1);}}public class SelectSort2{public static void selectSort(DataWrap[] data) {System.out.println("开始排序");int arrayLength = data.length;//依次进行n－1趟比较, 第i趟比较将第i大的值选出放在i位置上。for (int i = 0; i < arrayLength - 1 ; i++ ){//minIndex永远保留本趟比较中最小值的索引int minIndex = i ;//第i个数据只需和它后面的数据比较for (int j = i + 1 ; j < arrayLength ; j++ ){//如果第minIndex位置的数据 > j位置的数据if (data[minIndex].compareTo(data[j]) > 0){//将j的值赋给minIndexminIndex = j;}}//每趟比较最多交换一次if (minIndex != i){DataWrap tmp = data[i];data[i] = data[minIndex];data[minIndex] = tmp;}System.out.println(java.util.Arrays.toString(data));}}public static void main(String[] args){DataWrap[] data = {new DataWrap(21 , ""),new DataWrap(30 , ""),new DataWrap(49 , ""),new DataWrap(30 , "*"),new DataWrap(16 , ""),new DataWrap(9 , "")};System.out.println("排序之前：\n"+ java.util.Arrays.toString(data));selectSort(data);System.out.println("排序之后：\n" + java.util.Arrays.toString(data));}}//时间复杂度：n的平方//空间复杂度：1//稳定性：不稳定

import java.util.*;//定义一个数据包装类class DataWrap implements Comparable<DataWrap>{int data;String flag;public DataWrap(int data, String flag){this.data = data;this.flag = flag;}public String toString(){return data + flag;}//根据data实例变量来决定两个DataWrap的大小public int compareTo(DataWrap dw){return this.data > dw.data ? 1 : (this.data == dw.data ? 0 : -1);}}public class HeapSort{public static void heapSort(DataWrap[] data) {System.out.println("开始排序");int arrayLength = data.length;//循环建堆for (int i = 0; i < arrayLength - 1 ; i++ )//n-1次循环{//建堆builMaxdHeap(data , arrayLength - 1 - i);//交换堆顶和最后一个元素swap(data , 0 , arrayLength - 1 - i);System.out.println(java.util.Arrays.toString(data));}}//对data数组从0到lastIndex建大顶堆private static void builMaxdHeap(DataWrap[] data , int lastIndex){//从lastIndex处节点（最后一个节点）的父节点开始for (int i = (lastIndex - 1) / 2 ; i >= 0 ; i--){//k保存当前正在判断的节点int k = i;//如果当前k节点的子节点存在while (k * 2 + 1 <= lastIndex){//k节点的左子节点的索引int biggerIndex = 2 * k + 1; //如果biggerIndex小于lastIndex，即biggerIndex + 1//代表的k节点的右子节点存在if (biggerIndex < lastIndex){ //如果右子节点的值较大if(data[biggerIndex].compareTo(data[biggerIndex + 1]) < 0){//biggerIndex总是记录较大子节点的索引biggerIndex++; }}//如果k节点的值小于其较大子节点的值if(data[k].compareTo(data[biggerIndex]) < 0){//交换它们swap(data , k , biggerIndex);//将biggerIndex赋给k，开始while循环的下一次循环，//重新保证k节点的值大于其左、右子节点的值。k = biggerIndex;}else{break;}}}}//交换data数组中i、j两个索引处的元素private static void swap(DataWrap[] data , int i , int j){DataWrap tmp = data[i];data[i] = data[j];data[j] = tmp;}public static void main(String[] args){DataWrap[] data = {new DataWrap(21 , ""),new DataWrap(30 , ""),new DataWrap(49 , ""),new DataWrap(30 , "*"),new DataWrap(21 , "*"),new DataWrap(16 , ""),new DataWrap(9 , "")};System.out.println("排序之前：\n"+ java.util.Arrays.toString(data));heapSort(data);System.out.println("排序之后：\n" + java.util.Arrays.toString(data));}}//时间复杂度：nlog2n//空间复杂度：1//稳定性：不稳定

快速排序

import java.util.*;//定义一个数据包装类class DataWrap implements Comparable<DataWrap>{int data;String flag;public DataWrap(int data, String flag){this.data = data;this.flag = flag;}public String toString(){return data + flag;}//根据data实例变量来决定两个DataWrap的大小public int compareTo(DataWrap dw){return this.data > dw.data ? 1 : (this.data == dw.data ? 0 : -1);}}public class QuickSort{//将指定数组的i和j索引处的元素交换 private static void swap(DataWrap[] data, int i, int j) { DataWrap tmp; tmp = data[i]; data[i] = data[j]; data[j] = tmp; }//对data数组中从start～end索引范围的子序列进行处理//使之满足所有小于分界值的放在左边，所有大于分界值的放在右边private static void subSort(DataWrap[] data, int start , int end){//需要排序if (start < end){//以第一个元素作为分界值DataWrap base = data[start];//i从左边搜索，搜索大于分界值的元素的索引int i = start;//j从右边开始搜索，搜索小于分界值的元素的索引int j = end + 1;while(true){//找到大于分界值的元素的索引，或i已经到了end处while(i < end && data[++i].compareTo(base) <= 0);//找到小于分界值的元素的索引，或j已经到了start处while(j > start && data[--j].compareTo(base) >= 0);if (i < j){swap(data , i , j);}else{break;}}swap(data , start , j);//递归左子序列subSort(data , start , j - 1);//递归右边子序列subSort(data , j + 1, end);}}public static void quickSort(DataWrap[] data) {subSort(data , 0 , data.length - 1);}public static void main(String[] args){DataWrap[] data = {new DataWrap(9 , ""),new DataWrap(-16 , ""),new DataWrap(21 , "*"),new DataWrap(23 , ""),new DataWrap(-30 , ""),new DataWrap(-49 , ""),new DataWrap(21 , ""),new DataWrap(30 , "*"),new DataWrap(13 , "*")};System.out.println("排序之前：\n"+ java.util.Arrays.toString(data));quickSort(data);System.out.println("排序之后：\n" + java.util.Arrays.toString(data));}}//时间复杂度：n的平方//空间复杂度：1//稳定性：稳定

import java.util.*;//定义一个数据包装类class DataWrap implements Comparable<DataWrap>{int data;String flag;public DataWrap(int data, String flag){this.data = data;this.flag = flag;}public String toString(){return data + flag;}//根据data实例变量来决定两个DataWrap的大小public int compareTo(DataWrap dw){return this.data > dw.data ? 1 : (this.data == dw.data ? 0 : -1);}}public class ShellSort{public static void shellSort(DataWrap[] data) {System.out.println("Shell\n开始排序：");int arrayLength = data.length;//h变量保存可变增量int h = 1;//按h * 3 + 1得到增量序列的最大值while(h <= arrayLength / 3){h = h * 3 + 1;}while(h > 0){System.out.println("===h的值:" + h + "===");for (int i = h ; i < arrayLength ; i++ ){//当整体后移时，保证data[i]的值不会丢失DataWrap tmp = data[i];//i索引处的值已经比前面所有值都大，表明已经有序，无需插入//（i-1索引之前的数据已经有序的，i-1索引处元素的值就是最大值）if (data[i].compareTo(data[i - h]) < 0){int j = i - h;//整体后移h格for ( ; j >= 0 && data[j].compareTo(tmp) > 0 ; j-=h){data[j + h] = data[j];}//最后将tmp的值插入合适位置data[j + h] = tmp;}System.out.println(java.util.Arrays.toString(data));}h = (h - 1) / 3;}}public static void main(String[] args){DataWrap[] data = {new DataWrap(9 , ""),new DataWrap(-16 , ""),new DataWrap(21 , "*"),new DataWrap(23 , ""),new DataWrap(-30 , ""),new DataWrap(-49 , ""),new DataWrap(21 , ""),new DataWrap(30 , "*"),new DataWrap(30 , ""),};System.out.println("排序之前：\n"+ java.util.Arrays.toString(data));shellSort(data);System.out.println("排序之后：\n" + java.util.Arrays.toString(data));}}//时间复杂度：//空间复杂度：1//稳定性：稳定

class DataWrap implements Comparable<DataWrap>{int data;String flag;public DataWrap(int data, String flag){this.data = data;this.flag = flag;}public String toString(){return data + flag;}//根据data实例变量来决定两个DataWrap的大小public int compareTo(DataWrap dw){return this.data > dw.data ? 1 : (this.data == dw.data ? 0 : -1);}}public class MergeSort {//利用归并排序算法对数组data进行排序 public static void mergeSort(DataWrap[] data) {//归并排序 sort(data , 0 , data.length - 1);}/** * 将索引从left到right范围的数组元素进行归并排序 * @param data 待排序的数组 * @param left 待排序的数组的第一个元素索引 * @param right 待排序的数组的最后一个元素的索引 */ private static void sort(DataWrap[] data , int left, int right) { if (left < right) {//找出中间索引int center = (left + right) / 2;//对左边数组进行递归sort(data, left, center); //对右边数组进行递归sort(data, center + 1, right); //合并merge(data, left, center, right); } } /** * 将两个数组进行归并，归并前两个数组已经有序，归并后依然有序。 * @param data 数组对象 * @param left 左数组的第一个元素的索引 * @param center 左数组的最后一个元素的索引，center+1是右数组第一个元素的索引 * @param right 右数组的最后一个元素的索引 */ private static void merge(DataWrap[] data, int left, int center, int right) {//定义一个与待排序序列长度相同的临时数组 DataWrap[] tmpArr = new DataWrap[data.length];int mid = center + 1;//third记录中间数组的索引int third = left; int tmp = left; while (left <= center && mid <= right) { //从两个数组中取出小的放入中间数组 if (data[left].compareTo(data[mid]) <= 0) { tmpArr[third++] = data[left++]; } else{tmpArr[third++] = data[mid++]; }} //剩余部分依次放入中间数组 while (mid <= right) { tmpArr[third++] = data[mid++]; } while (left <= center) { tmpArr[third++] = data[left++]; } //将中间数组中的内容复制拷回原数组//(原left～right范围的内容复制回原数组) while (tmp <= right){data[tmp] = tmpArr[tmp++]; }} public static void main(String[] args){DataWrap[] data = {new DataWrap(9 , ""),new DataWrap(-16 , ""),new DataWrap(21 , "*"),new DataWrap(23 , ""),new DataWrap(-30 , ""),new DataWrap(-49 , ""),new DataWrap(21 , ""),new DataWrap(30 , "*"),new DataWrap(30 , "")};System.out.println("排序之前：\n"+ java.util.Arrays.toString(data));mergeSort(data);System.out.println("排序之后：\n" + java.util.Arrays.toString(data));}}//时间复杂度：//空间复杂度：//稳定性：稳定桶式排序

import java.util.Arrays;class DataWrap implements Comparable<DataWrap>{int data;String flag;public DataWrap(int data, String flag){this.data = data;this.flag = flag;}public String toString(){return data + flag;}//根据data实例变量来决定两个DataWrap的大小public int compareTo(DataWrap dw){return this.data > dw.data ? 1 : (this.data == dw.data ? 0 : -1);}}public class BucketSort{public static void bucketSort(DataWrap[] data , int min , int max){System.out.println("开始排序：");//arrayLength记录待排序数组的长度int arrayLength = data.length;DataWrap[] tmp = new DataWrap[arrayLength];//buckets数组相当于定义了max - min个桶，//buckets数组用于记录待排序元素的信息int[] buckets = new int[max - min];//计算每个元素在序列出现的次数for(int i = 0 ; i < arrayLength ; i++){//buckets数组记录了DataWrap出现的次数buckets[data[i].data - min]++;}System.out.println( Arrays.toString(buckets));//计算“落入”各桶内的元素在有序序列中的位置for(int i = 1 ; i < max - min; i++){//前一个bucket的值 + 当前bucket的值 -> 当前bucket新的值buckets[i] = buckets[i] + buckets[i - 1];}//循环结束后，buckets数组元素记录了“落入”前面所有桶和 //“落入”当前bucket中元素的总数，//也就说：buckets数组元素的值代表了“落入”当前桶的元素在有序序列中的位置System.out.println( Arrays.toString(buckets));//将data数组中数据完全复制到tmp数组中缓存起来。System.arraycopy(data, 0, tmp, 0, arrayLength);//根据buckets数组中的信息将待排序列的各元素放入相应的位置。for(int k = arrayLength - 1 ; k >= 0 ; k--)//从高位开始可以保证排序的稳定性{data[--buckets[tmp[k].data - min]] = tmp[k];}}public static void main(String[] args){DataWrap[] data = {new DataWrap(9 , ""),new DataWrap(5, ""),new DataWrap(-1, ""),new DataWrap(8 , ""),new DataWrap(5 , "*"),new DataWrap(7 , ""),new DataWrap(3 , ""),new DataWrap(-3, ""),new DataWrap(1 , ""),new DataWrap(3 , "*")};System.out.println("排序之前：\n"+ java.util.Arrays.toString(data));bucketSort(data , -3 , 10);System.out.println("排序之后：\n" + java.util.Arrays.toString(data));}}//时间复杂度：小//空间复杂度：大//稳定性：稳定?基数排序

import java.util.Arrays;public class MultiKeyRadixSort{/** * @param data 待排序的数组 * @param radix 指定关键字拆分的进制。如radix=10，表明按10进制拆分 * @param d 指定将关键字拆分成几个子关键字 */public static void radixSort(int[] data, int radix, int d) {System.out.println("开始排序：");int arrayLength = data.length;//需要一个临时数组int[] tmp = new int[arrayLength];//buckets数组是桶式排序必须buckets数组int[] buckets = new int[radix];//依次从最高位的子关键字对待排数据进行排序//下面循环中rate用于保存当前计算的位（比如十位时rate=10）for(int i = 0 , rate = 1 ; i < d ; i++){//重置count数组，开始统计第二个关键字Arrays.fill(buckets, 0);//将data数组的元素复制到temporary数组中进行缓存System.arraycopy(data, 0, tmp, 0, arrayLength);//计算每个待排序数据的子关键字for(int j = 0 ; j < arrayLength ; j++){//计算数据指定位上的子关键字int subKey = (tmp[j] / rate) % radix;buckets[subKey]++;}for(int j = 1 ; j < radix ; j++){buckets[j] = buckets[j] + buckets[j-1];}//按子关键字对指定数据进行排序for(int m = arrayLength - 1 ; m >= 0 ; m--){int subKey = (tmp[m] / rate) % radix;data[--buckets[subKey]] = tmp[m];}System.out.println("对" + rate + "位上子关键字排序：" + java.util.Arrays.toString(data));rate *= radix;}}public static void main(String[] args){int[] data = {1100 , 192 , 221 , 12 , 13};System.out.println("排序之前：\n"+ java.util.Arrays.toString(data));radixSort(data , 10 , 4);System.out.println("排序之后：\n" + java.util.Arrays.toString(data));}}?

【code】java兑现十种常见内部排序

热点推荐