排序是计算机内常常进行的一种操做，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。份内部排序和外部排序。若整个排序过程不须要访问外存便能完成，则称此类排序问题为内部排序。反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。html
稳定排序：假设在待排序的文件中，存在两个或两个以上的记录具备相同的关键字，在用某种排序法排序后，若这些相同关键字的元素的相对次序仍然不变，则这种排序方法是稳定的。java
冒泡，插入，基数，归并属于稳定排序git
选择，快速，希尔，堆属于不稳定排序。算法
就地排序：若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间为O(1),则称为就地排序。shell
冒泡排序(Bubble Sort)数组
一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，若是他们的顺序错误就把他们交换过来。走访数列的工做是重复地进行直到没有再须要交换，也就是说该数列已经排序完成。这个算法的名字由来是由于越小的元素会经由交换慢慢“浮”到数列的顶端。数据结构
算法步骤：
1)比较相邻的元素。若是第一个比第二个大，就交换他们两个。
2)对每一对相邻元素做一样的工做，从开始第一对到结尾的最后一对。这步作完后，最后的元素会是最大的数。
3)针对全部的元素重复以上的步骤，除了最后一个。
4)持续每次对愈来愈少的元素重复上面的步骤，直到没有任何一对数字须要比较。架构
图解：ide
优势：稳定，简单oop
缺点：慢，每次只移动相邻的两个元素。
时间复杂度：
理想状况下(数组原本就是有序的)，此时最好的时间复杂度为o(n),
最坏的时间复杂度(数据反序的)，此时的时间复杂度为o(n*n) 。
冒泡排序的平均时间负责度为o(n*n).
快速排序
由东尼·霍尔所发展的一种排序算法。
算法步骤：
1)从数列中挑出一个元素，称为 “基准”(pivot)，
2)从新排序数列，全部元素比基准值小的摆放在基准前面，全部元素比基准值大的摆在基准的后面(相同的数能够到任一边)。在这个分区退出以后，该基准就处于数列的中间位置。这个称为分区(partition)操做。
3)递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，可是这个算法总会退出，由于在每次的迭代(iteration)中，它至少会把一个元素摆到它最后的位置去。
图解：
时间复杂度：
在平均情况下，排序 n 个项目要Ο(n log n)次比较。
在最坏情况下则须要Ο(n2)次比较，但这种情况并不常见。
事实上，快速排序一般明显比其余Ο(n log n) 算法更快，由于它的内部循环(inner loop)能够在大部分的架构上颇有效率地被实现出来。
直接插入排序
插入排序是一种最简单直观的排序算法，它的工做原理是经过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
算法步骤：
1)将第一待排序序列第一个元素看作一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
2)从头至尾依次扫描未排序序列，将扫描到的每一个元素插入有序序列的适当位置。(若是待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。)
图解：
希尔排序
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的如下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操做时， 效率高， 便可以达到线性排序的效率
插入排序通常来讲是低效的， 由于插入排序每次只能将数据移动一位
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
算法步骤：
1)选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2)按增量序列个数k，对序列进行k 趟排序；
3)每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列做为一个表来处理，表长度即为整个序列的长度。
图解：
简单选择排序
算法步骤：
1)首先在未排序序列中找到最小(大)元素，存放到排序序列的起始位置
2)再从剩余未排序元素中继续寻找最小(大)元素，而后放到已排序序列的末尾。
3)重复第二步，直到全部元素均排序完毕。
图解：
时间复杂度：
简单选择排序过程当中，所需移动记录的次数比较少。
最好状况下，即待排序记录初始状态就已是正序排列了，则不须要移动记录。
最坏状况下，即待排序记录初始状态是按逆序排列的，则须要移动记录的次数最多为3(n-1)。
简单选择排序过程当中须要进行的比较次数与初始状态下待排序的记录序列的排列状况无关。
共须要进行的比较次数是(n-1)+(n-2)+…+2+1=n(n-1)/2，即进行比较操做的时间复杂度为O(n^2)，进行移动操做的时间复杂度为O(n)。
堆排序
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似彻底二叉树的结构，并同时知足堆积的性质：即子结点的键值或索引老是小于(或者大于)它的父节点。
算法步骤：
1)建立一个堆H[0..n-1]
2)把堆首(最大值)和堆尾互换
3)把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置
4) 重复步骤2，直到堆的尺寸为1
图解：
时间复杂度：
平均时间复杂度为Ο(nlogn) 。
归并排序
归并排序是创建在归并操做上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个很是典型的应用。将已有序的子序列合并，获得彻底有序的序列；即先使每一个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
算法步骤：
1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针达到序列尾
5. 将另外一序列剩下的全部元素直接复制到合并序列尾
图解：
基数排序(radix sort)
基数排序(radix sort)属于“分配式排序”(distribution sort)，又称“桶子法”(bucket sort)或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的做用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采起的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不一样的数字，而后按每一个位数分别比较。因为整数也能够表达字符串(好比名字或日期)和特定格式的浮点数，因此基数排序也不是只能使用于整数。
桶排序算法思想：是将阵列分到有限数量的桶子里。每一个桶子再个别排序(有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种概括结果。当要被排序的阵列内的数值是均匀分配的时候，桶排序使用线性时间(Θ(n))。但桶排序并非比较排序，他不受到 O(n log n) 下限的影响。简单来讲，就是把数据分组，放在一个个的桶中，而后对每一个桶里面的在进行排序。
例如要对大小为[1..1000]范围内的n个整数A[1..n]排序
首先，能够把桶设为大小为10的范围，具体而言，设集合B[1]存储[1..10]的整数，集合B[2]存储 (10..20]的整数，……集合B[i]存储( (i-1)*10, i*10]的整数，i = 1,2,..100。总共有 100个桶。
而后，对A[1..n]从头至尾扫描一遍，把每一个A[i]放入对应的桶B[j]中。 再对这100个桶中每一个桶里的数字排序，这时可用冒泡，选择，乃至快排，通常来讲任 何排序法均可以。
最后，依次输出每一个桶里面的数字，且每一个桶中的数字从小到大输出，这 样就获得全部数字排好序的一个序列了。
假设有n个数字，有m个桶，若是数字是平均分布的，则每一个桶里面平均有n/m个数字。若是对每一个桶中的数字采用快速排序，那么整个算法的复杂度是O(n + m * n/m*log(n/m)) = O(n + nlogn – nlogm)
从上式看出，当m接近n的时候，桶排序复杂度接近O(n)
固然，以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的 ，实际应用中效果并无这么好。若是全部的数字都落在同一个桶中，那就退化成通常的排序了。
前面说的几大排序算法 ，大部分时间复杂度都是O(n2)，也有部分排序算法时间复杂度是O(nlogn)。而桶式排序却能实现O(n)的时间复杂度。但桶排序的缺点是：
1)首先是空间复杂度比较高，须要的额外开销大。排序有两个数组的空间开销，一个存放待排序数组，一个就是所谓的桶，好比待排序值是从0到m-1，那就须要m个桶，这个桶数组就要至少m个空间。
2)其次待排序的元素都要在必定的范围内等等。
java 源码：
冒泡排序
1 packagecom.zhd.sort;2
3 //冒泡排序
4 public classSwapSortBubbleApp {5
6 public static voidmain(String[] args) {7 int[] test = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1};8 showArray(test);9 doSort(test);10 showArray(test);11 }12
13 //小->大
14 static void doSort(int[] arr) {15 bubbleSort(arr);16 }17
18 private static void bubbleSort(int[] arr) {19 for(int out = arr.length - 1; out > 0; out--) {20 for(int in = 0; in < out; in++) {21 if(arr[in] > arr[in+1]) swap(in, in+1, arr);22 }23 //System.out.println(out);showArray(arr);
24 }25 }26 private static void swap(int one, int two, int[] arr) {27 int tmp =arr[one];28 arr[one] =arr[two];29 arr[two] =tmp;30 }31
32 private static void showArray(int[] arr) {33 System.out.print("[ ");34 for(int i = 0; i < arr.length; i++) {35 System.out.print(arr[i] + " ");36 }37 System.out.println("]");38 }39 }
快速排序
1 packagecom.zhd.sort;2
3 //快速排序(基于交换)
4 public classSwapSortQuickApp {5
6 public static voidmain(String[] args) {7 int[] test = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1};8 showArray(test);9 doSort(test);10 showArray(test);11 }12
13 //小->大
14 static void doSort(int[] arr) {15 quickSort(arr, 0, arr.length-1);16 }17 private static void quickSort(int[] arr, int left, intright) {18 intdp;19 if(left = pivot) right--;29 if(left < right) n[left++] =n[right];30 while(left < right && n[left] <= pivot) left++;31 if(left < right) n[right--] =n[left];32 }33 n[left] =pivot;34 returnleft;35 }36
37 private static void showArray(int[] arr) {38 System.out.print("[ ");39 for(int i = 0; i < arr.length; i++) {40 System.out.print(arr[i] + " ");41 }42 System.out.println("]");43 }44 }
(非递归写法)
1 packagecom.zhd.sort;2
3 importjava.util.LinkedList;4
5
6 //快速排序(基于交换)
7 public classSwapSortQuickNonRecursionApp {8
9 public static voidmain(String[] args) {10 int[] test = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1};11 showArray(test);12 doSort(test);13 showArray(test);14 }15
16 //小->大
17 static void doSort(int[] arr) {18 quickSort(arr, 0, arr.length-1);19 quickSort2(arr, 0, arr.length-1);20 }21 private static void quickSort(int[] arr, int left, intright) {22 intdp;23 LinkedList stack = new LinkedList();24 if(left dp+1) {31 stack.push(dp+1);32 stack.push(right);33 }34 }35
36 while(!stack.isEmpty()) {37 int r =stack.pop();38 int l =stack.pop();39 dp =partition(arr, l, r);40 if(l < dp-1) {41 stack.push(l);42 stack.push(dp-1);43 }44 if(r > dp+1) {45 stack.push(dp+1);46 stack.push(r);47 }48 }49 }50 private static void quickSort2(int[] arr, int left, intright) {51 if(left > right) return;52
53 intdp;54 LinkedList stack = new LinkedList();55 do{56 if(!stack.isEmpty()) {57 right =stack.pop();58 left =stack.pop();59 }60
61 dp =partition(arr, left, right);62 if (left < dp - 1) {63 stack.push(left);64 stack.push(dp - 1);65 }66 if (right > dp + 1) {67 stack.push(dp + 1);68 stack.push(right);69 }70
71 } while(!stack.isEmpty());72 }73 private static int partition(int[] n, int left, intright) {74 int pivot =n[left];75 while(left = pivot) right--;77 if(left < right) n[left++] =n[right];78 while(left < right && n[left] <= pivot) left++;79 if(left < right) n[right--] =n[left];80 }81 n[left] =pivot;82 returnleft;83 }84
85 private static void showArray(int[] arr) {86 System.out.print("[ ");87 for(int i = 0; i < arr.length; i++) {88 System.out.print(arr[i] + " ");89 }90 System.out.println("]");91 }92 }
直接插入排序
1 packagecom.zhd.sort;2
3 //直接插入排序
4 public classInsertSortDirectApp {5
6 public static voidmain(String[] args) {7 int[] test = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1};8 showArray(test);9 doSort(test);10 showArray(test);11 }12
13 //基本有序下，效率最优O(n); 基本反序，效率最差O(n*n)
14 static void doSort(int[] arr) {15 directInsertSort(arr);16 }17
18 private static void directInsertSort(int[] arr) {19 for(int out = 1; out < arr.length; out++) {20 int tmp = arr[out], in =out;21 for(; in > 0 && arr[in-1] >= tmp; --in)22 arr[in] = arr[in-1];23 arr[in] =tmp;24 //System.out.println(out);showArray(arr);
25 }26 }27
28 private static void showArray(int[] arr) {29 System.out.print("[ ");30 for(int i = 0; i < arr.length; i++) {31 System.out.print(arr[i] + " ");32 }33 System.out.println("]");34 }35 }
希尔排序
1 packagecom.zhd.sort;2
3 //shell 排序
4 public classInsertSortShellApp {5
6 public static voidmain(String[] args) {7 int[] test = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1, 0};8 showArray(test);9 doSort(test);10 showArray(test);11 System.exit(0);12 }13
14 static void doSort(int[] arr) {15 shellSort(arr);16 }17
18 //最好，最坏状况下，效率相差不大
19 private static void shellSort(int[] arr) {20 int h = 1;21 while(h <= arr.length/3) h = h*3+1;22
23 while(h>0) {24 for(int out = h; out < arr.length; out++) {25 int tmp = arr[out], in =out;26 for(; in > h-1 && arr[in-h] >= tmp; in -=h) {27 arr[in] = arr[in-h];28 }29 arr[in] =tmp;30 //System.out.println("out=" + out + " h=" + h);showArray(arr);
31 }32 h = (h-1)/3;33 }34 }35
36 private static void showArray(int[] arr) {37 System.out.print("[ ");38 for(int i = 0; i < arr.length; i++) {39 System.out.print(arr[i] + " ");40 }41 System.out.println("]");42 }43 }
简单选择排序
1 packagecom.zhd.sort;2
3 //简单选择排序
4 public classSelectSortSimpleApp {5
6 public static voidmain(String[] args) {7 //int[] test = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1};
8 int[] test = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1, 8, 7, 6, 5, 4, 3, 2, 1, 8, 7, 6, 5, 4, 3, 2, 1};9 showArray(test);10 doSort(test);11 showArray(test);12 }13
14 static void doSort(int[] arr) {15 simpleSelectSort(arr);16 }17
18 private static void simpleSelectSort(int[] arr) {19 for(int out = 0; out < arr.length; out++) {20 int min =out;21 for(int in = out + 1; in < arr.length; in++)22 if(arr[in] < arr[min]) min =in;23 swap(out, min, arr);24 //System.out.println(out);showArray(arr);
25 }26 }27 private static void swap(int one, int two, int[] arr) {28 int tmp =arr[one];29 arr[one] =arr[two];30 arr[two] =tmp;31 }32
33 private static void showArray(int[] arr) {34 System.out.print("[ ");35 for(int i = 0; i < arr.length; i++) {36 System.out.print(arr[i] + " ");37 }38 System.out.println("]");39 }40 }
堆排序
1 packagecom.zhd.sort;2
3 //改进选择排序(堆排序)
4 public classSelectSortHeapApp {5
6 public static voidmain(String[] args) {7 //int[] test = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
8 int[] test = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 8, 7, 6, 5, 4, 3, 2, 1, 0, 8, 7, 6, 5, 4, 3, 2, 1, 0, 8, 7, 6, 5, 4, 3, 2, 1, 0};9 showArray(test);10 doSort(test);11 showArray(test);12 System.exit(0);13 }14
15 static void doSort(int[] arr) {16 heapSort(arr);17 }18
19 private static void heapSort(int[] arr) {20 buildHeap(arr, arr.length);21 for(int i = arr.length - 1; i > 0; --i) {22 swap(i, 0, arr);23 heapAdjust(arr, 0, i);24 }25 }26 private static void heapAdjust(int[] arr, int s, int len) { //构建大根堆
27 int tmp = arr[s], child = 2*s+1;28 while(child 0; --i)43 heapAdjust(arr, i, len);44 }45
46 private static void swap(int one, int two, int[] arr) {47 int tmp =arr[one];48 arr[one] =arr[two];49 arr[two] =tmp;50 }51
52 private static void showArray(int[] arr) {53 System.out.print("[ ");54 for(int i = 0; i < arr.length; i++) {55 System.out.print(arr[i] + " ");56 }57 System.out.println("]");58 }59 }
归并排序
1 packagecom.zhd.sort;2
3 public classMergeSortApp {4
5 public static voidmain(String[] args) {6 //int[] test = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1};
7 int[] test = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1, 8, 7, 6, 5, 4, 3, 2, 1, 8, 7, 6, 5, 4, 3, 2, 1, 8, 7, 6, 5, 4, 3, 2, 1};8 showArray(test);9 doSort(test);10 showArray(test);11 System.exit(0);12 }13
14 static void doSort(int[] arr) {15 mergeSort(arr, 0, arr.length-1);16 }17
18 private static void mergeSort(int[] array, int left, intright) {19 if (left >=right)20 return;21 int center = (left + right) / 2;//找出中间索引
22 mergeSort(array, left, center);//对左边数组进行递归
23 mergeSort(array, center + 1, right);//对右边数组进行递归
24 merge(array, left, center, right);//合并25 //showArray(array);
26 }27 private static void merge(int[] array, int left, int center, intright) {28 int[] tmpArr = new int[array.length];29 int mid = center + 1;30 int third =left;31 int tmp =left;32 while (left <= center && mid <=right) {33 if (array[left] <=array[mid]) {34 tmpArr[third++] = array[left++];35 } else{36 tmpArr[third++] = array[mid++];37 }38 }39 //剩余部分依次放入临时数组(实际上两个while只会执行其中一个)
40 while (mid <=right) {41 tmpArr[third++] = array[mid++];42 }43 while (left <=center) {44 tmpArr[third++] = array[left++];45 }46 //将临时数组中的内容拷贝回原数组中 (原left-right范围的内容被复制回原数组)
47 while (tmp <=right) {48 array[tmp] = tmpArr[tmp++];49 }50 }51
52
53 private static void showArray(int[] arr) {54 System.out.print("[ ");55 for(int i = 0; i < arr.length; i++) {56 System.out.print(arr[i] + " ");57 }58 System.out.println("]");59 }60 }
三大线性排序(计数排序，桶排序，基排序)
计数排序的基本思想是：统计一个数序列中小于某个元素a的个数为n,则直接把该元素a放到第n+1个位置上。当有几个元素相同时要作适当的调整，由于不能把全部的元素放到同一个位置上。计数排序假设输入的元素都是0到k之间的整数。
Java源码：
1 packagecom.zhd.sort;2
3 public classLinearSortCountApp {4
5 public static voidmain(String[] args) {6 //int[] test = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1};
7 int[] test = new int[]{5, 4, 3, 2, 1, 9, 8, 7, 6, 77, -1};8 showArray(test);9 doSort(test);10 showArray(test);11 }12 static void doSort(int[] arr) {13 countSort(arr);14 }15
16 //计数排序(要求待排数据是整数)
17 private static void countSort(int[] arr) {18 int[] b = new int[arr.length];19 int max = 0, min = 0;20 for(int i = 1; i < arr.length; i++) {21 if(arr[i] > arr[max]) max =i;22 if(arr[i] < arr[min]) min =i;23 }24
25 int k = arr[max] - arr[min] + 1; //这里k的大小是要排序的数组中，元素大小的极值差+1
26 int[] c = new int[k]; //优化过的地方，减少了数组c的大小
27 for(int i = 0; i < arr.length; ++i) {28 c[arr[i]-arr[min]] += 1;29 }30 for(int i = 1; i < c.length; ++i) {31 c[i] = c[i] + c[i-1];32 }33 for(int i = arr.length-1; i >= 0; --i) {34 b[--c[arr[i]-arr[min]]] = arr[i]; //按存取的方式取出c的元素
35 }36
37 for(int i = arr.length-1; i >= 0; --i) arr[i] =b[i];38 }39
40 private static void showArray(int[] arr) {41 System.out.print("[ ");42 for(int i = 0; i < arr.length; i++) {43 System.out.print(arr[i] + " ");44 }45 System.out.println("]");46 }47 }
桶排序
桶排序：桶排序的思想是把区间[0,1)划分红n个相同大小的子区间，称为桶。而后将n个输入数分布到各个桶中去。由于输入数均匀且独立分布在[0,1)上，因此，通常不会有不少数落在一个桶中的状况。为了获得结果，先对各个桶中的数进行排序，而后按次序把各桶中的元素列出来。
桶排序的时间复杂度为O(n) ，如有n个待排数据，m个桶，空间复杂度为O(n+m)
桶排序时间，空间复杂度分析：
桶排序的平均时间复杂度为线性的O(N+C)，其中C=N*(logN-logM)。
若是相对于一样的N，桶数量M越大，其效率越高，最好的时间复杂度达到O(N)。
桶排序的空间复杂度 为O(N+M)，
若是输入数据很是庞大，而桶的数量也很是多，则空间代价无疑是昂贵的。
桶排序是稳定的。
Java源码：
1 packagecom.zhd.sort;2
3 importjava.util.Collections;4 importjava.util.Iterator;5 importjava.util.LinkedList;6
7 public classLinearSortBucketApp {8
9 public static voidmain(String[] args) {10 //int[] test = new int[]{5, 4, 3, 2, 1, 9, 8, 7, 6, 77, -1};
11 double[] test = { 0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68};12 showArray(test);13 doSort(test);14 showArray(test);15 }16 static void doSort(double[] arr) {17 bucketSort(arr);18 }19
20 @SuppressWarnings({ "rawtypes", "unchecked"})21 private static void bucketSort(double[] arr) {22 int len =arr.length;23 LinkedList[] lls = newLinkedList[len];24 //划分桶并填元素
25 for(int i = 0; i < len; i++) {26 int tmp = (int) Math.floor(10 * arr[i]); //0.7到0.79放在第8个桶里,编号7；第一个桶放0到0.09
27 if (null == lls[tmp]) lls[tmp] = newLinkedList();28 lls[tmp].add(arr[i]);29 }30 //对每一个桶中的数进行排序
31 for(int i = 0; i < len; i++) {32 if (null !=lls[i]) {33 Collections.sort(lls[i]); //Collections和Arrays里的sort 是调优后的快排
34 }35 }36 //输出相似鸽巢排序
37 int count = 0;38 for(int i = 0; i < len; i++) {39 if (null !=lls[i]) {40 Iterator iter =lls[i].iterator();41 while(iter.hasNext()) {42 arr[count++] =(Double)iter.next();43 }44 }45 }46 }47
48 //private static void showArray(int[] arr) {49 //System.out.print("[ ");50 //for(int i = 0; i < arr.length; i++) {51 //System.out.print(arr[i] + " ");52 //}53 //System.out.println("]");54 //}
55 private static void showArray(double[] arr) {56 System.out.print("[ ");57 for(int i = 0; i < arr.length; i++) {58 System.out.print(arr[i] + " ");59 }60 System.out.println("]");61 }62 }
基数排序
基数排序也不是基于比较和元素移位的,
本文是基于计数排序的基数排序，只介绍最低位优先(Least Significant Digit First)
LSD(Least Significant Digit First)：就是从数字的最低位逐个比较，比较的趟数就是最大数字的位数digit，所以须要先用countDigit方法求出位数digit。(是否是有语病，看完就知道了)
优劣：
本算法是稳定的，LSD须要使用稳定的算法，
因为按位比较，所以须要整数，
和计数排序不一样的是，整数能够是负数(各类排序均可以正负混合)，待排序数值也能够很大。
图解：
Java源码：
1 packagecom.zhd.sort;2
3 importjava.util.Arrays;4
5 public classLinearSortRadixApp {6
7 public static voidmain(String[] args) {8 int[] test = new int[]{5, 4, 3, 2, 1, 9, 8, 7, 6, 77, 890, 222, 64, 89};9 showArray(test);10 doSort(test);11 showArray(test);12 }13 private static void doSort(int[] arr) {14 radixSort(arr);15 }16
17 private static void radixSort(int[] arr) {18 int digit = countDigit(arr); //digit 表明排序元素的位数，实际意义是排序趟数
19 int radix = 10; //radix 表明基数，实际就是几个数字，那就是10喽
20 radixSort(arr, radix, digit);21 }22 private static void radixSort(int[] arr, int radix, intdigit) {23 int len =arr.length;24 int[] res = new int[len];25 int[] c = new int[radix];26 int divide = 1;27
28 for(int i = 0; i < digit; i++) {29 res =Arrays.copyOf(arr, len);30 Arrays.fill(c, 0);31
32 //计数排序(稳定)
33 for(int j = 0; j < len; j++) {34 int key = (res[j]/divide) %radix;35 c[key]++;36 }37 for(int j = 1; j < radix; j++) {38 c [j] = c[j] + c[j-1];39 }40 for(int j = len - 1; j >= 0; j--) {41 int key = (res[j]/divide) %radix;42 arr[c[key]-1] =res[j];43 c[key]--;44 }45 divide = divide *radix;46 }47 }48 private static int countDigit(int[] arr) {49 int max = arr[0];50 for (int i = 1; i < arr.length; i++) {51 if (arr[i] >max) {52 max =arr[i];53 }54 }55 int time = 0;56 while (max > 0) {57 max /= 10;58 time++;59 }60 returntime;61 }62
63 private static void showArray(int[] arr) {64 System.out.print("[ ");65 for(int i = 0; i < arr.length; i++) {66 System.out.print(arr[i] + " ");67 }68 System.out.println("]");69 }70 }
参考url
url:http://www.cricode.com/3212.html
url:http://my.oschina.net/mkh/blog/341172
url:http://www.cnblogs.com/wolf-sun/p/4312475.html
url:http://blog.csdn.net/hguisu/article/details/7776068
url:http://m.blog.csdn.net/blog/likaiwalkman/23713373
url:http://www.cnblogs.com/kkun/archive/2011/11/23/2260312.html
url:http://www.cnblogs.com/hxsyl/p/3214379.html
url:http://www.cnblogs.com/hxsyl/p/3210647.html
url:http://blog.csdn.net/qeshine/article/details/9821567
url:http://my.oschina.net/liyixiangBlog/blog/266175
交换排序(冒泡排序,快速排序)
插入排序(直接插入排序,希尔排序)
选择排序(简单选择排序,堆排序)
归并排序