算法之排序(Java版)-持续更新补充
开始复习排序，主要是按照《轻松学算法》这本书的目录来学习，同时搜索网上的博客文章来辅助，参考的来源均在文章底部标明。同样，本文持续更新，代码书上只给了基础排序代码（我称之为原始排序代码），扩展的都是我自己写的，均通过测试，如果你觉得有写得不好或者能够优化的地方，非常欢迎留言评论或者私聊QQ我，大家交流学习，共同进步~~ 排序 一、桶排序 n为待排序的元素，m为桶的个数。排序只需要遍历一遍所有元素，输出就只需要遍历一遍桶，是非常快速的排序。当待排序元素分布很均匀的时候才能更有效的利用好空间，也弥补了桶排序牺牲空间换时间的不足。当然，桶排序还有痛点:小数，符数。实际使用的时候会根据实际情况采取巧妙的解决办法，比如结合散列表，来提高空间利用率。 public class BucketSort { private int[] buckets; private int[] array; public BucketSort(int range, int[] array) { this.buckets = new int[range]; this.array = array; } public void sort() { if(array != null && array.length > 1) { for(int i = 0; i < array.length - 1; i++) { buckets[array[i]]++; } } } public void print() { for(int i = buckets.length - 1; i >= 0; i--) { for(int j = 0; j < buckets[i]; j++) { System.out.println(i); } } } } 二、冒泡排序 体育老师肯定明白啥叫冒泡排序，每次重新组成班级了，体育课一开始要分成几个小队，让我们站成男女两排，高个在前，跟周围人比较，谁高谁到前面去，然后再报数一二一二，分成四队，简直完美！冒泡排序最坏情况是要n-1轮，并且每轮的每次比较之后都需要交换位置，时间复杂度为O(n^2)。用到的额外空间就是一个临时变量temp。同时冒泡排序是稳定的，遇到相同的元素并不会交换位置，所以对于同样大小的元素相对位置不会改变。 原始的冒泡排序是非常low的，有两种方法可以改进： 标记最后一次比较的位置，比如10，8，5，1，2，这个只需要经过一趟排序就能搞定。 一次冒泡两个元素，对于每一趟比较，正向、反向分别进行把最大和最小的都冒出去，这样可以使排序趟数减少一半。 还有一点可以加在这两个方法之中，就是如果发现没有交换，则说明全部有序，直接退出。详细看下面三段代码，分别对应着上面的原始冒泡，标记最后位置，一次冒两个。 //1. 原始冒泡 public class BubbleSort { private int[] array; public BubbleSort(int[] array) { this.array = array; } public void sort() { int length = array.length; if(length > 0) { for(int i = 1; i < length - 1; i++) { for(int j = 0; j < length - i; j++) { if(array[j] > array[j + 1]) { int temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } } } } } public void sort2() { int length = array.length; if(length > 0) { for(int i = length -1; i > 0; i--) { for(int j = length - 1; j > length - 1 - i; j--) { if(array[j] > array[j - 1]) { int temp = array[j]; array[j] = array[j - 1]; array[j - 1] = temp; } } } } } public void print() { for(int i = 0; i < array.length -1; i++) { System.out.println(array[i]); } } } //2. 标记最后交换位置冒泡 public class BubbleSort { private int[] array; private int mark; private boolean exchange = false; private int count;//用来记录总趟数 public BubbleSort(int[] array) { this.array = array; } public void sort() { int length = array.length; mark = length - 1; if(length > 0) { for(int i = 1; i < length - 1; i++) { exchange = false; int markIndex = mark; for(int j = 0; j < markIndex; j++) { if(array[j] > array[j + 1]) { exchange = true; mark = j + 1; int temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } } // 如果发现没有交换，则说明全部有序，退出 if(!exchange) { break; } count++; } } } public void print() { for(int i = 0; i < array.length; i++) { System.out.println(array[i]); } System.out.println("总趟数：" + count); } } //3. 一次冒泡两个 public class BubbleSort { private int[] array; private boolean exchange = false; private int count; public BubbleSort(int[] array) { this.array = array; } public void sort() { int length = array.length; if(length > 0) { for(int i = 1; i < length - 1; i++) { exchange = false; for(int j = 0; j < length - i; j++) { if(array[j] > array[j + 1]) { exchange = true; int temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } } for(int j = length - i; j > 0; j--) { if(array[j] < array[j - 1]) { exchange = true; int temp = array[j]; array[j] = array[j - 1]; array[j - 1] = temp; } } count++; if(!exchange) { break; } } } } public void print() { for(int i = 0; i < array.length -1; i++) { System.out.println(array[i]); } System.out.println("总趟数：" + count); } } 三、快速排序 名字很吊，快速排序，确实也是，基本是相同数量级所有排序算法中，平均性能最好的，而且简单，用的是分治的思想。快速排序可以说是冒泡排序的改进，冒泡每次只能交换相邻的元素，而快速排序是跳跃式的交换。显然，快速排序最差的情况就是每次都需要交换，是O(n^2)，时间复杂度一般是O(nlogn)。因为使用的是原来的数组空间，但是由于每次划分之后递归调用，会消耗栈的空间，所以空间复杂度一般为O(logn)。同样，最差的情况是每次只完成了一个元素，那就是O(n)了。快速排序是不稳定的，也就是说每次排序对相同值的元素的相对位置会发生改变，冒泡排序则不会。 同样的，相对于原始的快速排序，书里面也给了几个改进措施。 三者取中。如果每次选取基准值都取第一个数，那可能造成每次都需要移动，是算法时间复杂度变为O(n^2)。这里解决办法是，每次取头，尾，中的三个数，取中间大小的作为基准值。 根据规模大小改变算法。在数据量较小的时候切换为其他算法进行排序，一般为5~25。实现略。 分三个区间。大于基准数，小于基准数，和等于基准数的三个区间，这样每次只递归大于和小于部分的。实现略。 并行处理。因为快速排序只对数组中每一小段范围排序，对其它段没有影响，所以可以使用多线程并行处理。实现略。tip:实现省略的几个以后学得更深入了可能会回来再补充。 //1. 原始快速排序 public class QuickSort { private int[] array; public QuickSort(int[] array) { this.array = array; } public void sort() { quickSort(array, 0, array.length - 1); } public void print() { for(int i = 0; i < array.length; i++) { System.out.println(array[i]); } } public void quickSort(int[] src, int begin, int end) { if(begin < end) { int key = src[begin]; int i = begin; int j = end; while(i < j) { while(i < j && src[j] > key) { j--; } if(i < j) { src[i] = src[j]; i++; } while(i < j && src[i] < key) { i++; } if(i < j) { src[j] = src[i]; j--; } } src[i] = key; quickSort(src, begin, i - 1); quickSort(src, i + 1, end); } } } //2. 基准值三者取中 /* *这个参考了别人的博客（链接在底部），但看见他的方法略微繁琐，结合书中原始的快速排序代码，加以了改进。 * */ public class QuickSort { private int[] array; private int count;//记录递归次数 public QuickSort(int[] array) { this.array = array; } public void sort() { quickSort(array, 0, array.length - 1); } public void print() { for(int i = 0; i < array.length; i++) { System.out.println(array[i]); } System.out.println("递归的次数:" + count); } private void quickSort(int[] src, int begin, int end) { if(begin < end) { count++; int i = begin; int j = end; int mid = (begin + end) / 2; findMiddle(src, begin, mid, end); int key = src[i]; while(i < j) { while(i < j && src[j] > key) { j--; } if(i < j) { src[i] = src[j]; i++; } while(i < j && src[i] < key) { i++; } if(i < j) { src[j] = src[i]; j--; } } src[i] = key; quickSort(src, begin, i - 1); quickSort(src, i + 1, end); } } /*这个方法同时完成了两件事，找到中间值，并且把中间值和begin位置的值互换 从而巧妙的把后续求解过程转换成了原始的快速排序过程 */ private static void findMiddle(int[] src, int begin, int mid, int end) { if((src[mid] > src[begin] && src[mid] < src[end]) || (src[mid] > src[end] && src[mid] < src[begin])) { swap(src, begin, mid); }else if((src[end] > src[begin] && src[end] < src[mid]) || (src[end] > src[mid] && src[end] < src[begin])) { swap(src, begin ,end); }else { return; } } private static void swap(int[] src, int a, int b) { int temp = src[a]; src[a] = src[b]; src[b] = temp; } } 四、插入排序 有两种，一种是直接插入排序，一种是二分插入排序。直接插入排序的思想：分为两列，一列已经排好序，一列没有，没有排好序的那列的值一个个加入已经排序好的那列。二分插入排序是在直接插入排序的基础上使用二分查找来找到插入的位置。直接插入排序时间复杂度是O(n^2)，空间复杂度是O(1)，因为是数组内部自己排序，后面新加入的按照一个个与前面已经排好序的比较，再移动，所以可以保持相同值的相对位置不变，所以是稳定的。 插入排序发挥最好的场景是当数列已经近似有序的时候，所以一般与快速排序搭配使用。也就是在快速排序的分区规模达到一定的值比如5~25的时候，而往往这时候每个分区中也近似有序了，所以正好可以切换为使用插入排序来辅助。 希尔排序 原始的直接插入排序的改进就是传说中的————希尔排序。基本思想：把待排序的数列按照一定间隔分组，然后对各个组的数列进行插入排序。这个间隔（说间隔有点不准确，想不到更好的词了，意思不理解可以直接看代码，或者百度一下再回来~）叫做增量，增量逐渐减少到1为止。 对于希尔排序的时间复杂度，因为增量的序列不一定，所以时间复杂度也不确定。增量序列有几种方法，这里先不记录了。如果采用每除以2的增量选择，最好情况仍是待排序数组本身有序，O(n)，最坏情况是O(n^2)。一般认为希尔排序的平均时间复杂度为O(n^(1.3))。希尔排序中会进行分组，排序，同样的值的元素如果不在同一个组里，其相对位置可能变化，所以希尔排序是不稳定的，这与插入排序不同。 //1. 直接插入排序 public class InsertSort { private int[] array; public InsertSort(int[] array) { this.array = array; } public void sort() { if(array == null) { throw new RuntimeException("array is null"); } int length = array.length; if(length > 1) { for(int i = 1; i < length; i ++) { int j = i; int temp = array[i]; for(; j > 0 && array[j - 1] > temp; j--) { array[j] = array[j - 1]; } array[j] = temp; } } } public void print() { for(int i = 0; i < array.length; i++) { System.out.println(array[i]); } } } //2. 希尔排序 /* *这里对于增量的处理，采取每次对长度取半的方式 */ public class ShellSort { private int[] array; public ShellSort(int[] array) { this.array = array; } //这里跟书上不同，我改进了一下（￣︶￣）↗ (说不定性能反而下降了。。) public void sort() { int length = array.length; for(int k = length/2; k > 0; k/=2) { for(int i = k; i < length; i++) { int j = i; int temp = array[i]; for(; j >= k && array[j - k] > temp; j-=k) { array[j] = array[j - k]; } array[j] = temp; } } } public void print() { for(int i = 0; i < array.length; i++) { System.out.println(array[i]); } } } 五、选择排序 思想：每次选择最大或最小的数与第一个交换。比较的次数与数列长度有关，而外部也需要遍历也与长度有关，所以不管在什么情况下，时间复杂度总是O(n^2)。由于不需要一个个移动，时间复杂度比冒泡排序略好。稳定性，比如6，6'，1，第一次交换后变为：1,6',6。发现两个6的相对顺序改变了，所以不稳定。改进：有点跟冒泡排序一次冒两个泡类似，可以同时寻找到最大、最小分别与第一个和最后一个交换。 //1. 简单选择排序 public class SelectSort { private int[] array; public SelectSort(int[] array) { this.array = array; } public void sort() { int length = array.length; for(int i = 0; i < length; i++) { int minIndex = i; for(int j = i + 1; j < array.length; j++) { if(array[j] < array[minIndex]) { minIndex = j; } } if(minIndex != i) { int temp = array[minIndex]; array[minIndex] = array[i]; array[i] = temp; } } } public void print() { for(int i = 0; i < array.length; i++) { System.out.println(array[i]); } } } //2. 同时选择最大和最小 public class SelectSort { private int[] array; public SelectSort(int[] array) { this.array = array; } public void sort() { int length = array.length; int i = 0; for(; i < length - i; i++) { int minIndex = i; int maxIndex = length - i - 1; for(int j = i + 1; j < length - i; j++) { if(array[j] < array[minIndex]) { minIndex = j; } if(array[j] > array[maxIndex]) { maxIndex = j; } } if(minIndex != i) { swap(array, minIndex, i); } if(maxIndex != length - i - 1) { swap(array, maxIndex, length - i - 1); } } } public void print() { for(int i = 0; i < array.length; i++) { System.out.println(array[i]); } } private void swap(int[] array, int a ,int b) { int temp = array[a]; array[a] = array[b]; array[b] = temp; } } 上面提到的算法，除了快速排序空间复杂度是O(logn)之外，其他的都是O(1)。关于稳定性稳定性是指排序之后原有数列中相同值的相对次序是否发生改变，没有改变则是稳定的。稳定性的好处，1. 如果稳定，那么上一趟排序的结果可以被下一趟使用。2.可以避免多余的比较或移动。 选择排序算法考虑时的注意点 待排序的数列长度 记录本身的数据量（通常根据记录中的部分内容排序，也需要考虑一下其他部分数据量的大小） 待排序数列元素结构和分布（比如，分布集中可以考虑桶排序） 对排序稳定性的要求 参考： 《轻松学算法》赵烨 《图解排序算法(五)之快速排序——三数取中法》
