排序是什么 所谓排序就是按照其中的某个或某些关键字的大小，按照升序或者降序的方式把他们排列起来的操作。
冒泡排序 冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 /* * 冒泡排序 * 比较相邻的元素。如果第一个比第二个大，就交换他们两个。 * 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 * 针对所有的元素重复以上的步骤，除了最后一个。 * 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 * @param numbers 需要排序的整型数组 */ public static void bubbleSort(int[] numbers) { int temp = 0; int size = numbers.length; for(int i = 0 ; i < size-1; i ++) { for(int j = 0 ;j < size-1-i ; j++) { //交换两数位置 if(numbers[j] > numbers[j+1]) { temp = numbers[j]; numbers[j] = numbers[j+1]; numbers[j+1] = temp; } } } }
选择排序 先定义一个记录最小元素的下标，然后循环一次后面的，找到最小的元素，最后将他放到前面排序好的序列。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 public static void main(String[] args) { int a[]=new int[]{3,1,4,1,5,9,2,6,5,3,5,8,9}; for (int i = 0; i < a.length-1; i++) { int index=i;//标记第一个为待比较的数 for (int j = i+1; j < a.length; j++) { //然后从后面遍历与第一个数比较 if (a[j]<a[index]) { //如果小,就交换最小值 index=j;//保存最小元素的下标 } } //找到最小值后，将最小的值放到第一的位置，进行下一遍循环 int temp=a[index]; a[index]=a[i]; a[i]=temp; } }
插入排序 定义一个待插入的数，再定义一个待插入数的前一个数的下标，然后拿待插入数与前面的数组一一比较，最后交换。
1 2 3 4 5 6 7 8 9 10 11 12 int a[]=new int[]{3,1,4,1,5,9,2,6,5,3,5,8,9}; for (int i = 1; i < a.length; i++) { //长度不减1，是因为要留多一个位置方便插入数 //定义待插入的数 int insertValue=a[i]; //找到待插入数的前一个数的下标 int insertIndex=i-1; while (insertIndex>=0 && insertValue <a[insertIndex]) {//拿a[i]与a[i-1]的前面数组比较 a[insertIndex+1]=a[insertIndex]; insertIndex--; } a[insertIndex+1]=insertValue; }
希尔排序 如果我们要插入一个元素2 ，在直接插入排序中是依次对比，比2大的元素挨个向后移动。直接插入排序的问题就在此：如果在后面来了一个特别小的元素，需要全部移动，那么排序的效率特别低。
接下来我们介绍一种更加高效率的插入排序方法：希尔排序。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 public class ShellSort { public static void main(String[] args) { int[] arr =new int[]{3,1,4,1,5,9,2,6,5,3,5,8,9}; shellSort(arr); System.out.println(Arrays.toString(arr)); } //希尔排序 public static void shellSort(int[] arr){ //挨个遍历步长，缩短步长，直到步长为零 for(int gap =arr.length/2;d>0;gap=gap/2){ //遍历所有的元素 for(int i=gap;i<arr.length;i++){ //遍历本组中所有的元素,从第一个元素开始 for(int j=i-gap;j>=0;j=j-gap){//本组前面的那个元素 //如果当前元素大于加上步长之后的那个元素,（前面的比后面的大了）交换 if(arr[j]>arr[j+gap]){ int temp = arr[j]; arr[j]=arr[j+gap]; arr[j+gap]=temp; } } } } } }
快速排序 它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
1 2 3 4 首先设定一个分界值，通过该分界值将数组分成左右两部分； 将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值； 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 public class Quick { /* 比较v元素是否大于等于w元素 */ private static boolean greater(Comparable v, Comparable w){ return v.compareTo(w) >= 0; } /* 数组元素i和j交换位置 */ private static void exch(Comparable[] args, int i,int j){ Comparable temp; temp = args[i]; args[i] = args[j]; args[j] = temp; } // 对数组内的元素进行排序 public static void quickSort(Comparable[] args) { quickSort(args, 0, args.length - 1); } public static void quickSort(Comparable[] args, int left, int right) { // 安全性校验 if (right < left){ return; } // 取第一个数为基准值 Comparable key = args[left]; int i = left, j = right; while (i < j){ // 先从右往左扫描，找到一个比基准值小的元素 while (greater(args[j], key) && j > i) j --; // 再从左往右扫描，找一个比基准值大的元素 while (greater(key, args[i]) && i < j) i ++; if (i < j) exch(args, i, j); } // 交换基准值与i、j相遇位置的元素 exch(args, left, i); // 对分成的左边部分进行排序 quickSort(args, left, i - 1); // 对分成的右边部分进行排序 quickSort(args, i + 1, right); } }
归并排序 归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
1 2 3 尽可能的一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数是 1为止； 将相邻的两个子组进行合并成一个有序的大组； 不断的重复步骤2，直到最终只有一个组为止。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 public class Merge { // 归并所需要的辅助数组 private static Comparable[] assistTemp; /* 对数组 args 中的元素进行排序 */ public static void mergeSort(Comparable[] args) { // 初始化辅助数组 assistTemp assistTemp = new Comparable[args.length]; mergeSort(args, 0, args.length - 1, assistTemp); } public static void mergeSort(Comparable[] args, int left, int right, Comparable[] assistTemp) { // 分解 if (left < right) { int mid = (left+right) / 2; // 向左递归进行分解 mergeSort(args, left, mid, assistTemp); // 向右递归进行分解 mergeSort(args, mid + 1, right, assistTemp); // 每分解一次便合并一次 merge(args, left, right, mid, assistTemp); } } /* 合并 */ private static void merge(Comparable[] args, int left, int right, int mid, Comparable[] assistTemp) { // 用于合并数组的下标，即操作 assistTemp 下标 int tempIndex = 0; int i = left, j = mid + 1; while(i <= mid && j <= right){ // 当 args[i] <= args[j] 时，将 args[i] 加入 assistTemp if(greater(args[j], args[i])){ assistTemp[tempIndex ++] = args[i ++]; } else{ assistTemp[tempIndex ++] = args[j ++]; } } // 将未遍历完的数组直接放入 assistTemp while(i <= mid){ assistTemp[tempIndex ++] = args[i ++]; } while(j <= right){ assistTemp[tempIndex ++] = args[j ++]; } // 将 assistTemp 的元素赋值给 args for(i = right; i >= left; --i){ args[i] = assistTemp[--tempIndex]; } } /* 比较 v元素 是否大于 w元素 */ private static boolean greater(Comparable v, Comparable w){ return v.compareTo(w) > 0; } }
快速排序和归并排序的区别：
计数排序 计数排序是一个基于非比较的排序算法，元素从未排序状态变成已排序状态的过程，是由额外空间的计数和元素本身的值决定的。
排序步骤：
1 2 3 4 找出待排序的数组array中最大的元素max 统计数组中每个值为 i 的元素出现的次数，存入数组 count 的第 i 项 对所有的计数累加（从 count中的第一个元素开始，每一项和前一项相加） 反向填充目标数组：将每个元素 i 放在新数组的第 count [i] 项，每放一个元素就将 count [i] 减去
如果该方法可用的情况下，一般是最快的方式，但是使用条件比较苛刻。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 public class Count { public static void countSort(Comparable[] args) { // 获取最大值，以便确定 countArray 大小 int countLen =(int) findMaxElement(args) + 1; int[] countArray = new int[countLen]; // 开始计数 for (Comparable t: args) countArray[(int) t] ++; int idx = 0; for (int i = 0; i < countLen; ++i){ while (countArray[i] > 0){ args[idx ++] = i; countArray[i] --; } } } /* 比较v元素是否大于w元素 */ private static boolean greater(Comparable v, Comparable w){ return v.compareTo(w) > 0; } /* 返回数组最大值 */ private static Comparable findMaxElement(Comparable[] args) { if (args.length == 0) return null; Comparable max = args[0]; for (Comparable t: args){ if (greater(t, max)) max = t; } return max; } }
Arrays常用方法 Arrays.toString()方法 方法作用：快速输出数组内容。
1 2 int[] a = {1,2,3,4,5}; System.out.println(Arrays.toString(a));
Arrays.sort()方法 方法运用:给数组排序，默认升序
1 2 3 int[] a = new int[5]{5，4，3，2，1}; Arrays.sort(a); // 1 2 3 4 5
Arrays.equals()方法 Arrays.equals()方法
1 2 3 int[] a = {1,2,3}; int[] b = {1,2,3}; boolean isSame = Arrays.equals(a,b);
Arrays.equals()是比较数组内容，而a.equals(b) 这样的方法是比较地址值
Arrays.copyOf() 方法作用：拷贝数组
1 2 int[] arr1 = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int[] arr2 = Arrays.copyOf(arr1, 7);
