公众号merlinsea
- 排序的基本概念
- 排序： 排序就是将原本无序序列重新排列成有序序列的过程，这个序列的中的每一项都可以是单独的数据元素或者是一条记录（比如一个学生记录是由学号、年龄、姓名、年龄等数据元素组成）。
- 排序的稳定性：稳定性是指待排序的序列中有两个或者两个以上相同的关键字的时，排序前后这些相等关键字的相对位置没有发生变化就是稳定排序，如果发生了相对变化，就称之为不稳定排序。 注意，这里的没有发生变化是不论初始的无序序列是如何排列的，在排序后都必须是相等关键字都不发生相对位置的变化，只要有一次相对位置发生了变化就是不稳定排序。
- 排序算法的分类
- 插入类排序是对新的关键字进行找位置的排序方式，找到位置以后直接进行插入即可，常见的插入类排序有直接插入排序、折半插入排序和希尔排序。
- 选择类排序的核心是"选择"，即每一趟都选出一个最大关键字或最小关键字和待排序序列的最后一个和第一个进行交换位置。
- 交换类排序的核心是“交换”，即通过一系列交换操作，将新的关键字排到他正确的位置上，常见的交换类排序有快速排序和对排序。
- 归并类排序是将两个或者两个以上的有序序列合并成一个新的有序序列的过程，常见的有二路归并排序算法。
- 基数类排序不同于其他排序算法的比较和移动这两个操作，基数类排序是基于多关键字的排序思想，比如对一副去掉大小王的扑克牌进行基数排序，首先可以将牌按照花色分为4堆，然后对每一堆牌按照A-K再分为13堆，最后依次取出这13堆牌即得到有序的牌。
- 直接插入排序
- 直接插入排序是把无序的序列里的数据插入到有序的序列中去，在遍历无序序列的时候，首先拿无序序列里的第一个元素跟有序序列里的每一个元素比较，并且插入到合适的位置，一直到无序序列里的所有元素插入完毕为止。
public class Main { public static void main(String[] args) { int[] array = new int[]{4,2,6,1,3,8,7}; System.out.println("排序前："); for(int i=0;i<array.length;i++){ System.out.printf("%d \t",array[i]); } System.out.println(); insertSort(array); System.out.println("排序后："); for(int i=0;i<array.length;i++){ System.out.printf("%d \t",array[i]); } System.out.println(); } // 直接插入排序 public static void insertSort(int[] array){ for(int i=1;i<array.length;i++){ // 待插入待元素是array[i], array[0,i-1] int target = array[i]; int j = i-1; for(j=i-1;j>=0;j--){ if(target<array[j]){ // 保证了是个稳定排序 array[j+1]=array[j]; //array[j]= target; }else{ break; } } array[j+1]=target; } }
- 希尔排序
- 希尔排序是通过记录按下标的一定增量来进行分组，对每一组使用直接插入排序的算法进行排序；随着增量的变小，每组所包含的关键词也会越来越多，当增量变成1的时候，整个都恰好的被分成了一组，排序完后就终止了。
- 希尔排序相当于跨步长的直接插入排序。
public class Main { public static void main(String[] args) { int[] array = new int[]{4,2,6,1,3,8,7}; System.out.println("排序前："); for(int i=0;i<array.length;i++){ System.out.printf("%d \t",array[i]); } System.out.println(); shellSort(array); System.out.println("排序后："); for(int i=0;i<array.length;i++){ System.out.printf("%d \t",array[i]); } System.out.println(); } // 希尔排序 public static void shellSort(int[] array){ int[] steps = {5,2,1}; for(int step : steps){ // 下面这个for循环表示步长为step所有组完成了排序， for(int i=0;i<step;i++){ // 比如步长为2， 我们下面待for循环只是完成了步长2的其中一组排序 for(int j=i+step;j<array.length;j=j+step){ // 当前待插入待元素是array[k]; int target = array[j]; for(int k=j-step;k>=i;k = k-step){ // 需要让target和array[k]比较 if(array[k]>target){ // 需要让target和array[k】交换位置 array[k+step] = array[k]; array[k] = target; }else{ break; } } } System.out.printf("step = %d 中的 第%d组完成了排序\n",step,i+1); for(int a: array){ System.out.printf("%d \t",a); } System.out.println(); } } }
- 冒泡排序
- 冒泡排序（Bubble Sort），它是一种最为基础的交换排序。相信都喝过汽水吧，小气泡比二氧化碳要轻所有小气泡上浮。之所以叫冒泡排序，是因为这一种排序算法的每一个元素可以根据自身的大小，一点点的向着一侧来移动。
public class Main { public static void main(String[] args) { int[] array = new int[]{4,2,6,1,3,8,7}; System.out.println("排序前："); for(int i=0;i<array.length;i++){ System.out.printf("%d \t",array[i]); } System.out.println(); bubbleSort(array); System.out.println("排序后："); for(int i=0;i<array.length;i++){ System.out.printf("%d \t",array[i]); } System.out.println(); } // 冒泡排序, 是否是稳定排序 ---》 稳定排序 public static void bubbleSort(int[] array){ for(int i=0;i<array.length;i++){ boolean isSwap = false; for(int j=0;j<array.length-i-1;j++){ if(array[j]>array[j+1]){ // 交换位置 int temp = array[j]; array[j] = array[j+1]; array[j+1] = temp; isSwap = true; } } if(!isSwap){ // 我们当前轮全程没交换 return; } } } }
- 快速排序
- 快速排序是对冒泡排序的一种改良版，通过一趟排序，把要排序的序列分割成两个部分，一部分的所有数据要比另一部分的数据都小，然后再根据这两部分的数据来进行快速排序。以此来达到整一个数据都变成了有序序列。
- 首先快速排序要选取一个基准值pivot，以基准值为分割，把比该基准值小的放左边，基准值大的放右边。然后得出来的序列再进行快速排序。
public class Main { public static void main(String[] args) { int[] array = new int[]{49,38,65,97,76,13,27,49}; System.out.println("排序前："); for(int i=0;i<array.length;i++){ System.out.printf("%d \t",array[i]); } System.out.println(); quickSort(array,0,array.length-1); System.out.println("排序后："); for(int i=0;i<array.length;i++){ System.out.printf("%d \t",array[i]); } System.out.println(); } public static void quickSort(int[] arr,int left,int right){ if(left>=right){ //递归的终点 return; } int pivot = arr[left]; int l = left; int r = right; while(l<r){ //右指针向左移动 while(l<r && arr[r]>=pivot){ r--; } if(l<r){ arr[l] = arr[r]; arr[r] = pivot; l++; } // pivot 位于r的位置 //左指针向右移动 while(l<r && arr[l]<pivot){ l++; } if(l<r){ arr[r]=arr[l]; arr[l]=pivot; r--; } // pivo位于l位置 } //当推出循环的时候，pivot位于arr[l]处 quickSort(arr,left,l-1); quickSort(arr,l+1,right); } }
- 归并排序
- 归并排序是利用了归并这种思想来实现的排序方法，这种算法采用的是经典的分治策略，将问题分成小问题然后进行求解，很像递归求解。然后将分出来的阶段再合在一起。
public class Main { public static void main(String[] args) { int[] array = new int[]{17,4,2,6,9,3,2,1}; System.out.println("排序前："); for(int i=0;i<array.length;i++){ System.out.printf("%d \t",array[i]); } System.out.println(); mergeSort(array,0,array.length-1); System.out.println("排序后："); for(int i=0;i<array.length;i++){ System.out.printf("%d \t",array[i]); } System.out.println(); } public static void mergeSort(int[] arr,int left,int right){ if(left>=right){ return; } int mid = (left+right)/2; // 分 mergeSort(arr,left,mid); mergeSort(arr,mid+1,right); //治 merge(arr,left,mid,mid+1,right); } public static void merge(int[] arr,int l1,int r1,int l2,int r2){ int len = r2-l1+1; // 每次归并都会开辟一个额外的temp空间，导致空间复杂度比较高 int[] temp = new int[len]; int i = l1; int j = l2; int idx = 0; while(i<=r1 && j<=r2){ if(arr[i] < arr[j]){ temp[idx] = arr[i]; i++; }else{ temp[idx] = arr[j]; j++; } idx++; } //下面两个while至多执行一个while while(i<=r1){ temp[idx] = arr[i]; i++; idx++; } while(j<=r2){ temp[idx] = arr[j]; j++; idx++; } //将temp倒回去 for(idx=0;idx<len;idx++){ arr[idx+l1] = temp[idx]; } } }
- 基数排序
- 基数排序也称之为桶排序，其思想是基于多关键字进行排序的，其核心的思想是“分配”和“收集”操作。举个去掉了大小王的扑克牌的例子，首先将扑克牌按牌值分配到A-K的13个桶子中，然后将扑克牌收集起来；接着将收集起来的扑克牌按照花色分配到4个不同的桶中，然后将其手机起来，这样就可以得到整体上是按照花色进行排序，同一种花色按照牌的值进行排序的新牌了。
- 基数排序的特点
- 基数排序中的桶是一个先进先出的数据结构， 用队列来表示这个桶
- 基数排序的第一轮分发和收集以后，输出的整体结果是按照第一轮的关键关键字【即牌值】进行排序的
- 基数排序的第二轮分发和收集以后，输出的整体结果是按照第二轮的关键字【即花色】进行排序的，同时每一种花色内又是按照第一轮的关键字进行排序的。
- 因此我们可以得到特点是：基数排序中，越往后的“分发”和“收集”的关键字的排序权重越高。 比如在本例子中，我们可以发现花色的排序权重要高于牌值的权重，因为最终结果是所有的红心牌都排在了方块牌的前面，在花色一样的情况下，我们才按照牌值进行排序。
public class Solution { public static void main(String[] args) { int[] array = new int[]{278,109,63,930,12,32,8,21,344}; System.out.println("排序前"); for(int k : array){ System.out.printf("%d\t",k); } System.out.println(); bucketSort(array); System.out.println("排序后"); for(int k : array){ System.out.printf("%d\t",k); } System.out.println(); } // 基数排序，桶排序 // 时间复杂度： cnt*n = n public static void bucketSort(int[] array){ if(array.length <= 1){ return; } int cnt = count(array); int bit = 1; for(int i=0;i<cnt;i++){ // 分配 List<Queue<Integer>> list = allocate(array,bit); // 收集 collect(list,array); bit = bit*10; } } public static void collect(List<Queue<Integer>> list,int[] array){ int idx = 0; for(int i=0;i<list.size();i++){ Queue<Integer> qu = list.get(i); while(!qu.isEmpty()){ int k = qu.poll(); array[idx] = k; idx++; } } return; } public static List<Queue<Integer>> allocate(int[] array,int bit){ List<Queue<Integer>> list = new ArrayList<>(10); for(int i=0;i<10;i++){ // set 一定是对有过元素的位置进行set //list.set(i,new LinkedList<>()); list.add(new LinkedList<>()); } for(int k : array){ int token = k/bit%10; list.get(token).offer(k); } return list; } // 统计需要进行多少次分配和收集 private static int count(int[] array){ int cnt = 0; for(int k : array){ int curCnt = 0; while(k>0){ curCnt++; k = k/10; } cnt = Math.max(cnt,curCnt); } return cnt; } }
- java中的sort函数使用
- Arrays.sort()函数的的基本认识
- 自定义类型自己实现Comparable接口
- sort()方法传入实现了Comparator接口的示例对象
- 注意当返回值大于0时发生交换
- 当对数字数组进行排序时，默认是按照数字进行升序排列
- 当对字符串数组进行排序时，默认是按照字典升序排列
- 当对自定义类型的数组进行排序时
- 对数字进行排序代码
public class Main { public static void main(String[] args) { int[] array = new int[]{14,3,21,17,67,55,32,12,5,7,6,44}; System.out.println("排序前："); for(int i=0;i<array.length;i++){ System.out.printf("%d \t",array[i]); } System.out.println(); Arrays.sort(array); System.out.println("排序后："); for(int i=0;i<array.length;i++){ System.out.printf("%d \t",array[i]); } System.out.println(); } }
- 对字符串进行排序代码
public class Main2 { public static void main(String[] args) { String[] array = new String[]{"abc","abb","abca","bca","bba","abce"}; System.out.println("排序前"); for(String s : array){ System.out.printf("%s \t",s); } System.out.println(); Arrays.sort(array); System.out.println("排序后"); // abb abc abca abce bba bca for(String s : array){ System.out.printf("%s \t",s); } System.out.println(); } }
- 对自定义类型进行排序代码
- 要求对学生类进行排序，按分数从高到低输出，当分数相同时，按名字的字典顺序输出
// 分数从高到低进行排序，在分数相同的情况下按name进行排序 class Student{ int score; String name; public Student(int score,String name){ this.name = name; this.score = score; } @Override public String toString() { return "Student{" + "score=" + score + ", name='" + name + '\'' + '}'; } } public class Solution { public static void main(String[] args) { Student[] array = {new Student(100,"lili"),new Student(119,"zhangsan"), new Student(88,"hong"),new Student(100,"lile"),new Student(120,"lili")}; for(Student stu : array){ System.out.printf("%s \t",stu); } Arrays.sort(array, new Comparator<Student>() { // 如果comapre返回大于0 就进行交换 // O1在前 O2在后 @Override public int compare(Student o1, Student o2) { if(o1.score<o2.score){ return o2.score - o1.score; }else if(o1.score == o2.score){ // 在分数相同的情况下，那个名字小就放前面 // o1.name.compareTo(o2.name)--> o1.name - o2.name >0 ---> 说明o2的name字典排序小 ---》 o2应该和o1交换位置 --》 返回一个大于0的数 return o1.name.compareTo(o2.name); }else{ return o2.score - o1.score; } } }); System.out.println(); System.out.println("排序后"); for(Student stu : array){ System.out.printf("%s \t",stu); } } }
