排序算法小结

 1 public class SelectionSort { 2     /* 选择排序算法 3      * 基本思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换； 4      *        　　然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。 5      * 例子:  57 68 52 6      *  1.　最小值为52,与第一个交换 7      *  2.　最小值为57,与第二个交换 8      *  ３．68为最小值,无需交互 9      *  10      *  简单选择排序是不稳定的排序,时间复杂度 O(n^2)。11      */12     public static void sort(int[] arrs) {13         for (int i = 0;i<arrs.length;i++){14             int min = arrs[i];15             int j =0;16             for(j = i+1;j<arrs.length;j++){17                 if (arrs[j]< min){18                     min = arrs[j];19                 }20             }21             arrs[j] = arrs[i];22             arrs[i] = min;23         }24     }25 26 }

 1 public class HeapSort { 2      3     /* 堆排序 4      * 堆排序是一种树形选择排序，是对直接选择排序的有效改进。 5      * 堆的定义下：具有n个元素的序列 （h1,h2,...,hn); 6      * 当且仅当满足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1） (i=1,2,...,n/2)时称之为堆。 7      * 在这里只讨论满足前者条件的堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项（大顶堆）。 8      * 完全二叉树可以很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。 9      * 思想:10      *     初始时把要排序的数的序列看作是一棵顺序存储的二叉树，11      *     调整它们的存储序，使之成为一个堆，这时堆的根节点的数最大。12      *     然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。13      *     依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。14      *     从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。15      *     所以堆排序有两个函数组成。16      *         一是建堆的渗透函数，17      *      二是反复调用渗透函数实现排序的函数。18      *      19      *  堆排序是一种不稳定的排序算法,堆排序的最坏时间复杂度为O(nlogn)20      */21     public static void sort(int[] arr){22         int len = arr.length;23         for(int i =0;i<len;i++){ //循环建堆24             buildheap(arr,0,len-1-i);    //建堆25             swap(arr,0,len-1-i);    // 交换根节点和最后一个节点26         }27     }28     29     public static void swap(int[] arr,int start,int tar){30         int temp = arr[tar];31         arr[tar] = arr[start];32         arr[start] = temp;33     }34     35     public static void buildheap(int[] arr,int start,int end){36         //从最后一节点的父节点开始建堆37         for(int i = (end-1)/2;i>=0;i--){38             int k =i;  39             //k节点的左右子节点为　2k+1,2k+2 (索引从0开始)40             while(k*2+1<=end){41                 int bigchild = 2*k+1;42                 if(bigchild<end){ //右节点存在43                     if(arr[bigchild]<arr[bigchild+1]){44                         bigchild++;  //找出最大的子节点45                     }46                 }47                 if(arr[k]<arr[bigchild]){48                     swap(arr,k,bigchild);49                     k = bigchild;50                 }else{break;}51             }52         }53     }54 }

 1 public class BubbleSort { 2      3     /* 冒泡排序 4      * 基本思想： 5      * 在要排序的一组数中，对当前还未排好序的范围内的全部数， 6      * 自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。 7      * 即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。 8      * 例子： 9      *         32,74,1310      *     一趟冒泡排序后　变成 : 32,13,7411      * 12      * 冒泡排序是一种稳定的排序方法,平均时间复杂度为O(n^2)。13      */14     public static void sort(int[] arrs) {15         for (int i=0;i<arrs.length;i++){16             for(int j=0;j<(arrs.length-i-1);j++){17                 if (arrs[j]>arrs[j+1]){18                     int tmp = arrs[j];19                     arrs[j] = arrs[j+1];20                     arrs[j+1] = tmp;21                 }22             }23         }24     }25 26 }

 1 public class QuickSort { 2     /* 快速排序 3      * 基本思想： 4      * 选择一个基准元素,通常选择第一个元素或者最后一个元素, 5      * 通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素, 6      * 此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。 7      *  8      * 例子: 9      *   57, 68 ,19, 32   //选取57 为key10      *   一趟: 57, 68 ,19, 32 -> 32, 68, 19, 57 -> 19,32,68,57 11      *   12      * 快速排序是不稳定的排序。时间复杂度为O(nlogn)。13      */14     public static void sort(int[] arrs,int start,int end){15         int key = start;16         int i =start;17         int j=end;18         if (start<end){19             while(i<j){20                 while(arrs[i]<arrs[key]){21                     i++;22                 }23                 swap(arrs,key,i);24                 while(arrs[j]>arrs[key]){25                     j--;26                 }27                 swap(arrs,key,j);28             }29             sort(arrs,start,i);30             sort(arrs,i+1,end);31         }32     }33     34     public static void swap(int[] arrs,int key,int tar){35         int tmp = arrs[key];36         arrs[key] = arrs[tar];37         arrs[tar] = tmp;38     }39 40 }

 1 public class MergeSort { 2      3     /* 归并排序 4      * 基本思想: 5      * 归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表， 6      * 即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。 7      * 例子: 8      * 57 68 59 52 72 28 96 33 9      * 1) --> [57 68] [52 59] [28 72] [33 96]10      * 2) --> [52 57 59 68] [28 33 72 96]11      * 3) --> [28 33 52 57 59 68 72 96]12      * 13      * 时间复杂度为O(nlogn),是稳定的排序方法。14      */15     public static void sort(int[] arrs,int start,int end){16         if (start<end){17             int middle = (start+end)/2;18             sort(arrs,start,middle);19             sort(arrs,middle+1,end);20             merge(arrs,middle,start,end);21         }22     }23     24     public static void merge(int[] arrs,int middle,int start,int end){25         int[] newarr = new int[arrs.length];26         int mid = middle+1; //右边的起始位置27         int tmp = start;28         int third = start;29         while(start<=middle && mid<=end){30             //从两个数组中选取较小的数放入中间数组31             if(arrs[start]<=arrs[mid]){32                 newarr[third] = arrs[start];33                 start++;34             }else{35                 newarr[third] = arrs[mid];36                 mid++;37             }38             third++;39         }40         //将剩余的部分放入中间数组41         while(start<=middle){42             newarr[third] = arrs[start];43             third++;44             start++;45         }46         while(mid<=end){47             newarr[third] = arrs[mid];48             third++;49             mid++;50         }51         //将中间数组复制回原数组52         while(tmp<=end){53             arrs[tmp] = newarr[tmp];54             tmp++;55         }56     }57 }

 1 import java.util.ArrayList; 2 import java.util.List; 3  4 public class radixSort { 5      6     /* 基数排序 7      * 基本思想： 8      * 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。 9      * 然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。10      * 11      * 例子:12      *  [135 242 192 93 345 11 24 19] //基数为1013      *  14      *  1) 个位排序　[11 242 192 93 24 135 345 19]15      *  2) 十位排序　[11 19 24 135 242 345 192 93]16      *  3) 百位排序　[11 19 24 93 135 192 242 345]17      *  18      *  基数排序是稳定的排序算法,基数排序的时间复杂度为O(d(n+r)),d为位数，r为基数。19      */20     21     public static void sort(int[] arr){22         int max = arr[0];23         for(int i=0;i<arr.length;i++){24             if (arr[i]>max){25                 max = arr[i];26             }27         }28         int times= 0;29         while(max>0){30             max= max/10;31             times++;32         }33         List<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();34         for(int i=0;i<10;i++){35             ArrayList<Integer> tmplist = new ArrayList<Integer>();36             list.add(tmplist);37         }38         for(int i= 0;i<times;i++){39             for(int j=0;j<arr.length;j++){40                 int x = arr[j]%(int)Math.pow(10, i+1)/(int)Math.pow(10, i);41                 ArrayList<Integer> tmp = list.get(x);42                 tmp.add(arr[j]);43                 list.set(x, tmp);44             }45             int count = 0;46             for(ArrayList<Integer> tmp : list){47                 if(!tmp.isEmpty()){48                     for(Integer num: tmp){49                         arr[count] = num;50                         count++;51                     }52                 }53             }54             for(ArrayList<Integer> tmp : list){55                 tmp.clear();56             }57         }58         59     }60 61 }

 1 import java.util.*; 2 public class sorttest { 3      4     public static void arrayprint(int[] arrs){ 5         int leng = arrs.length; 6         for (int i = 0;i<leng;i++) 7         { 8             System.out.println("element "+ i+" -> "+arrs[i]); 9         }10     }11     12     public static void main(String[] args) {13         Scanner sc = new Scanner(System.in);14         List<Integer> ints = new ArrayList<Integer>();15         System.out.println("input array elements,use <ctrl> + <d> to end the input!");16         while(sc.hasNextInt()){17             int tmp = sc.nextInt();18             System.out.println("add to array: "+tmp);19             ints.add(tmp);20         }21         sc.close();22         int[] arrs = new int[ints.size()];23         for(int i = 0;i<ints.size();i++){24             arrs[i] = ints.get(i);25         }26         System.out.println("before array sorted...");27         sorttest.arrayprint(arrs);28         /*29          * here use sort function for parameter: arrs30          */31         System.out.println("after array sorted...");32         sorttest.arrayprint(arrs);33     }34 35 }