排序算法主要包括：冒泡排序、快速排序、希尔排序、插入排序、选择排序、堆排序、归并排序、基数排序、桶排序
（1）.冒泡排序：
/** * 冒泡排序 * * @param array * @return */ public int[] bubbleSort(int[] array){ if(array.length==0) return array; int temp=0; for(int i=0;i<array.length;i++){ for(int j=0;j<array.length-i;j++){ if (array[j + 1] < array[j]) { temp = array[j + 1]; array[j + 1] = array[j]; array[j] = temp; } } } }
（2）.快速排序
快速排序的原理：选择一个关键值作为基准值，比基准值小的在左边序列，比基准值大的在右边序列（一般左右都是无序的），一般选择序列的第一个元素。
一次循环：从后往前比较，用基准值和最后一个值比较，如果比基准值小的就交换位置，如果没有就继续比较下一个，直到找到第一个比基准值小的数才交换，找到这个值之后，又从前往后开始比较，如果有比基准值大的就交换位置，没有就继续比较下一个，直到找到第一个比基准值大的值才交换，直到从前往后的比较索引>从后往前比较的索引，结束第一次循环，此时，对于基准值 来说，左右两边就是有序的了。
public void sort(int[] a,int low,int high){ int start = low; int end = high; int key = a[low]; while(end>start){ //从后往前比较 while(end>start&&a[end]>=key) //如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较 end--; if(a[end]<=key){ int temp = a[end]; a[end] = a[start]; a[start] = temp; } //从前往后比较 while(end>start&&a[start]<=key) //如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置 start++; if(a[start]>=key){ int temp = a[start]; a[start] = a[end]; a[end] = temp; } //此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的 值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用 } //递归 if(start>low) sort(a,low,start-1);//左边序列。第一个索引位置到关键值索引-1 if(end<high) sort(a,end+1,high);//右边序列。从关键值索引+1到最后一个 } }
（3）.插入排序
通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入。 插入排序非常类似于整扑克牌。在开始摸牌时，左手是空的，牌面朝下放在桌上。接着，一次从 桌上摸起一张牌，并将它插入到左手一把牌中的正确位置上。为了找到这张牌的正确位置，要将 它与手中已有的牌从右到左地进行比较。无论什么时候，左手中的牌都是排好序的。
如果输入数组已经是排好序的话，插入排序出现最佳情况，其运行时间是输入规模的一个线性函 数。如果输入数组是逆序排列的，将出现最坏情况。平均情况与最坏情况一样，其时间代价是(n2)。
1 public void sort(int arr[]) 2 { 3 for(int i =1; i<arr.length;i++) 4 { 5 //插入的数 6 int insertVal = arr[i]; 7 //被插入的位置(准备和前一个数比较) 8 int index = i-1; 9 //如果插入的数比被插入的数小 10 while(index>=0&&insertVal<arr[index]) 11 { 12 //将把arr[index] 向后移动 13 arr[index+1]=arr[index]; 14 //让index向前移动 15 index--; 16 } 17 //把插入的数放入合适位置 18 arr[index+1]=insertVal; 19 } 20 }
（4）.希尔排序
基本思想：先将若干待排序的记录序列分成若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行依次直接插入排序。
1 private void shellSort(int[] a) { 2 int dk = a.length/2; 3 while( dk >= 1 ){ 4 ShellInsertSort(a, dk); 5 dk = dk/2; 6 } 7 } 8 private void ShellInsertSort(int[] a, int dk) { 9 //类似插入排序，只是插入排序增量是1，这里增量是dk,把1换成dk就可以了 10 for(int i=dk;i<a.length;i++){ 11 if(a[i]<a[i-dk]){ 12 int j; 13 int x=a[i];//x为待插入元素 14 a[i]=a[i-dk]; 15 for(j=i-dk; j>=0 && x<a[j];j=j-dk){ 16 //通过循环，逐个后移一位找到要插入的位置。 17 a[j+dk]=a[j]; 18 } 19 a[j+dk]=x;//插入 20 } 21 } 22 }
（5）.归并排序算法
归并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列 分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
1 public class MergeSortTest { 2 public static void main(String[] args) { 3 int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 }; 4 print(data); 5 mergeSort(data); 6 System.out.println("排序后的数组："); 7 print(data); 8 } 9 public static void mergeSort(int[] data) { 10 sort(data, 0, data.length - 1); 11 } 12 public static void sort(int[] data, int left, int right) { 13 if (left >= right) 14 return; 15 // 找出中间索引 16 int center = (left + right) / 2; 17 // 对左边数组进行递归 18 sort(data, left, center); 19 // 对右边数组进行递归 20 sort(data, center + 1, right); 21 // 合并 22 merge(data, left, center, right); 23 print(data); 24 } 25 /** 26 * 将两个数组进行归并，归并前面2个数组已有序，归并后依然有序 27 28 29 * 30 * @param data 31 * 数组对象 32 * @param left 33 * 左数组的第一个元素的索引 34 * @param center 35 * 左数组的最后一个元素的索引，center+1是右数组第一个元素的索引 36 * @param right 37 * 右数组最后一个元素的索引 38 */ 39 public static void merge(int[] data, int left, int center, int right) { 40 // 临时数组 41 int[] tmpArr = new int[data.length]; 42 // 右数组第一个元素索引 43 int mid = center + 1; 44 // third 记录临时数组的索引 45 int third = left; 46 // 缓存左数组第一个元素的索引 47 int tmp = left; 48 while (left <= center && mid <= right) { 49 // 从两个数组中取出最小的放入临时数组 50 if (data[left] <= data[mid]) { 51 tmpArr[third++] = data[left++]; 52 } else { 53 tmpArr[third++] = data[mid++]; 54 } 55 } 56 // 剩余部分依次放入临时数组（实际上两个while只会执行其中一个） 57 while (mid <= right) { 58 tmpArr[third++] = data[mid++]; 59 60 61 } 62 while (left <= center) { 63 tmpArr[third++] = data[left++]; 64 } 65 // 将临时数组中的内容拷贝回原数组中 66 // （原left-right范围的内容被复制回原数组） 67 while (tmp <= right) { 68 data[tmp] = tmpArr[tmp++]; 69 } 70 } 71 public static void print(int[] data) { 72 for (int i = 0; i < data.length; i++) { 73 System.out.print(data[i] + "\t"); 74 } 75 System.out.println(); 76 } 77 }
（6）.桶排序算法
桶排序的基本思想是：把数组arr划分为n个大小相同子区间（桶），每个子区间各自排序，最后合并，基数排序是桶排序的一种特殊情况，可以把基数排序当成每个桶里只有一个元素的情况。
1 public static void bucketSort(int[] arr){ 2 int max = Integer.MIN_VALUE; 3 int min = Integer.MAX_VALUE; 4 for(int i = 0; i < arr.length; i++){ 5 max = Math.max(max, arr[i]); 6 min = Math.min(min, arr[i]); 7 } 8 //创建桶 9 int bucketNum = (max - min) / arr.length + 1; 10 ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum); 11 for(int i = 0; i < bucketNum; i++){ 12 bucketArr.add(new ArrayList<Integer>()); 13 } 14 //将每个元素放入桶 15 for(int i = 0; i < arr.length; i++){ 16 int num = (arr[i] - min) / (arr.length); 17 bucketArr.get(num).add(arr[i]); 18 } 19 //对每个桶进行排序 20 for(int i = 0; i < bucketArr.size(); i++){ 21 Collections.sort(bucketArr.get(i)); 22 }
（7）.基数排序算法
将所有的比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零，然后从最低位开始，依次进行一次排序，这样从最低位一直到最高位排序完成以后，数列就变成一个有序序列。
1 public class radixSort { 2 inta[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,101,56,17,18,23,34,15,35,2 5,53,51}; 3 public radixSort(){ 4 sort(a); 5 for(int i=0;i<a.length;i++){ 6 System.out.println(a[i]); 7 } 8 } 9 public void sort(int[] array){ 10 11 //确定排序的趟数 12 for(int i=1;i<array.length;i++){ 13 if(array[i]>max){ 14 max=array[i]; 15 } 16 } 17 int time=0; 18 //判断位数; 19 while(max>0){ 20 max/=10; 21 time++; 22 } 23 //建立10个队列; 24 List<ArrayList> queue=newArrayList<ArrayList>(); 25 for(int i=0;i<10;i++){ 26 ArrayList<Integer>queue1=new ArrayList<Integer>(); 27 queue.add(queue1); 28 } 29 //进行time次分配和收集; 30 for(int i=0;i<time;i++){ 31 //分配数组元素; 32 for(intj=0;j<array.length;j++){ 33 //得到数字的第time+1位数; 34 int x=array[j]%(int)Math.pow(10,i+1)/(int)Math.pow(10, i); 35 ArrayList<Integer>queue2=queue.get(x); 36 queue2.add(array[j]); 37 queue.set(x, queue2); 38 } 39 int count=0;//元素计数器 40 //收集队列元素; 41 for(int k=0;k<10;k++){ 42 while(queue.get(k).size()>0){ 43 ArrayList<Integer>queue3=queue.get(k); 44 array[count]=queue3.get(0); 45 queue3.remove(0); 46 count++; 47 } 48 } 49 } 50 } 51 }
原文：https://www.cnblogs.com/Mr-RanX/p/11318059.html