一个排序算法的好坏,一般是通过下面几个关键信息来分析的,下面先介绍一下这几个关键信息,然后再将常见的排序算法的这些关键信息统计出来。
名词介绍
常见的排序算法的这几个关键信息如下:
冒泡排序是一种简单直观的排序算法,它需要多次遍历数据;
主要有这么几步:
这样最终达到整体数据的一个有序性了。
动图演示
冒泡排序:
/** * 冒泡排序 * @param array */ public static void bubbleSort(int[] array){ if(array.length == 0){ return; } for(int i=0;i<array.length;i++){ // 每一次都减少i个元素 for(int j=0;j<array.length-1-i;j++){ // 若相邻的两个元素比较后,前一个元素大于后一个元素,则交换位置。 if(array[j]>array[j+1]){ int temp = array[j]; array[j] = array[j+1]; array[j+1] = temp; } } } }
当数组中的元素已经是正序时,执行效率最高。
当数组中的元素是一个倒序时,执行效率最低,相邻的元素每次比较都需要交换位置。
而且冒泡排序是完全在数据内部进行的,不需要额外的空间,所以空间复杂度是O(1)。
选择排序是一种简单粗暴的排序方式,每次都从数据中选出最大或最小的元素,最终选完了,那么选出来的数据就是排好序的了。
主要步骤:
动图演示
public static void selectSort(int[] array){ for(int i=0;i<array.length;i++){ // 先以i为最小值的下标 int min = i; // 然后从后面的数据中找出比array[min] 还小的值,就替换min为当前下标。 for(int j=i+1;j<array.length;j++){ if(array[j]<array[min]){ min = j; } } // 最终如果最小值的下标不等于i了,那么将最小值与i位置的数据替换,即将最小值放到数组前面来,然后循环整个操作。 if(min != i){ int temp = array[i]; array[i] = array[min]; array[min] = temp; } } }
选择排序总结
所有的数据经过选择排序,时间复杂度都是O(n^2);所以需要排序的数据量越小选择排序的效率越高。
插入排序也是一种比较直观和容易理解的排序算法,通过构建有序序列,将未排序中的数据插入到已排序中序列,最终未排序全部插入到有序序列,达到排序效果。
主要步骤:
动图演示
public static void insertSort(int[] array){ // 第一个元素被认为默认有序,所以遍历无序元素从i1开始。 for(int i=1;i<array.length;i++){ int sortItem = array[i]; int j = i; // 将当前元素插入到前面的有序元素里,将当前元素与前面有序元素从后往前挨个对比,然后将元素插入到指定位置。 while (j>0 && sortItem < array[j-1]){ array[j] = array[j-1]; j--; } // 若当前元素在前面已排序里面不是最大的,则将它插入到前面已经确定了位置里。 if(j !=i){ array[j] = sortItem; } } }
插入排序总结
插入排序也是采用的内部排序,所以空间复杂度是O(1),但是时间复杂度就是O(n^2),因为基本上每个元素都要处理多次,需要反复将已排序元素移动,然后将数据插入到指定的位置。
希尔排序是插入排序的一个升级版,它主要是将原先的数据分成若干个子序列,然后将每个子序列进行插入排序,然后每次拆得子序列数量逐次递减,直到拆的子序列的长度等于原数据长度。然后再将数据整体来依次插入排序。
主要步骤:
选择一个增量序列 t1,t2,……,tk,其中 ti > tj, tk = 1;
按增量序列个数 k,对序列进行 k 趟排序;
每趟排序,根据对应的增量 ti,将待排序列分割成若干长度为 m 的子序列,分别对各子表进行直接插入排序。仅增量因子为 1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。
过程演示
原始未排序的数据。
经过初始增量gap=array.length/2=5分组后,将原数据分为了5组,[12,1]、[29,30]、[5,45]、[16,26]、[15,32]。
将分组后的数据,每一组数据都直接执行插入排序,这样数据已经慢慢有序起来了,然后再缩小增量gap=5/2=2,将数据分为2组:[1,5,15,30,26]、[29,16,12,45,32]。
对上面已经分好的两组进行插入排序,整个数据就更加趋向有序了,然后再缩小增量gap=2/2=1,整个数据成为了1组,整个序列作为了表来处理,然后再执行一次插入排序,数据最终达到了有序。
/** * 希尔排序 * @param array */ public static void shellSort(int[] array){ int len = array.length; int temp, gap = len / 2; while (gap > 0) { for (int i = gap; i < len; i++) { temp = array[i]; int preIndex = i - gap; while (preIndex >= 0 && array[preIndex] > temp) { array[preIndex + gap] = array[preIndex]; preIndex -= gap; } array[preIndex + gap] = temp; } gap /= 2; } }
归并排序是采用的分而治之的递归方式来完成数据排序的,主要是将已有序的两个子序列,合并成一个新的有序子序列。先将子序列分段有序,然后再将分段后的子序列合并成,最终完成数据的排序。
主要步骤:
动图演示
/** * 归并排序 * @param array 数组 * @param left 0 * @param right array.length-1 */ public static void mergeSort(int[] array,int left,int right){ if (right <= left){ return; } // 一分为二 int mid = (left + right)/2; // 对前半部分执行归并排序 mergeSort(array, left, mid); // 对后半部分执行归并排序 mergeSort(array, mid + 1, right); // 将分好的每个子序列,执行排序加合并操作 merge(array, left, mid, right); } /** * 合并加排序 * @param array * @param left * @param middle * @param right */ public static void merge(int[] array,int left,int middle,int right){ // 中间数组 int[] temp = new int[right - left + 1]; int i = left, j = middle + 1, k = 0; while (i <= middle && j <= right) { // 若前面数组的元素小,就将前面元素的数据放到中间数组中 if(array[i] <= array[j]){ temp[k++] = array[i++]; }else { // 若后面数组的元素小,就将后面数组的元素放到中间数组中 temp[k++] = array[j++]; } } // 若经过上面的比较合并后,前半部分的数组还有数据,则直接插入中间数组后面 while (i <= middle){ temp[k++] = array[i++]; } // 若经过上面的比较合并后,后半部分的数组还有数据,则直接插入中间数组后面 while (j <= right){ temp[k++] = array[j++]; } // 将数据从中间数组中复制回原数组 for (int p = 0; p < temp.length; p++) { array[left + p] = temp[p]; } }
归并排序总结
归并排序效率很高,时间复杂度能达到O(nlogn),但是依赖额外的内存空间,而且这种分而治之的思想很值得借鉴,很多场景都是通过简单的功能,组成了复杂的逻辑,所以只要找到可拆分的最小单元,就可以进行分而治之了。
快速排序,和二分查找的思想很像,都是先将数据一份为二然后再逐个处理。快速排序也是最常见的排序算法的一种,面试被问到的概率还是比较大的。
主要步骤:
动图演示
/** * 快速排序 * @param array 数组 * @param begin 0 * @param end array.length-1 */ public static void quickSort(int[] array, int begin, int end) { if (end <= begin) return; int pivot = partition(array, begin, end); quickSort(array, begin, pivot - 1); quickSort(array, pivot + 1, end); } /** * 分区 * @param array * @param begin * @param end * @return */ public static int partition(int[] array, int begin, int end) { // pivot: 标杆位置,counter: 小于pivot的元素的个数 int pivot = end, counter = begin; for (int i = begin; i < end; i++) { if (array[i] < array[pivot]) { // 替换,将小于标杆位置的数据放到开始位置算起小于标杆数据的第counter位 int temp = array[counter]; array[counter] = array[i]; array[i] = temp; counter++; } } // 将标杆位置的数据移动到小于标杆位置数据的下一个位。 int temp = array[pivot]; array[pivot] = array[counter]; array[counter] = temp; return counter; }
快速排序总结
我找的快速排序的模板代码,是比较巧妙的,选择了最后一个元素作为了基准元素,然后小于基准元素的数量,就是基准元素应该在的位置。这样看起来是有点不好懂,但是看明白之后,就会觉得这个模板写的还是比较有意思的。
堆排序其实是采用的堆这种数据结构来完成的排序,一般堆排序的方式都是采用的一种近似完全二叉树来实现的堆的方式完成排序,但是堆的实现方式其实不止有用二叉树的方式,其实还有斐波那契堆。
而根据排序的方向又分为大顶堆和小顶堆:
像Java中的PriorityQueue就是小顶堆。
主要步骤:
动图演示
/** * 堆排序 * @param array */ public static int[] heapSort(int[] array){ int size = array.length; // 先将数据放入堆中 for (int i = (int) Math.floor(size / 2); i >= 0; i--) { heapTopMove(array, i, size); } // 堆顶位置调整 for(int i = size - 1; i > 0; i--) { swapNum(array, 0, i); size--; heapTopMove(array, 0,size); } return array; } /** * 堆顶位置维护 * @param array * @param i * @param size */ public static void heapTopMove(int[] array,int i,int size){ int left = 2 * i + 1; int right = 2 * i + 2; int largest = i; if (left < size && array[left] > array[largest]) { largest = left; } if (right < size && array[right] > array[largest]) { largest = right; } if (largest != i) { swapNum(array, i, largest); heapTopMove(array, largest, size); } } /** * 比较交换 * @param array * @param left * @param right */ public static void swapNum(int[] array,int left,int right){ int temp = array[left]; array[left] = array[right]; array[right] = temp; }
堆排序总结
堆排序的时间复杂度也是O(nlogn),这个也是有一定的概率在面试中被考察到,其实如果真实在面试中遇到后,可以在实现上不用自己去维护一个堆,而是用Java中的PriorityQueue来实现,可以将无序数据集合放入到PriorityQueue中,然后再依次取出堆顶数据,取出堆顶数据时要从堆中移除取出的这个元素,这样每次取出的就都是现有数据中最小的元素了。
计数排序是一种线性时间复杂度的排序算法,它主要的逻辑时将数据转化为键存储在额外的数组空间里。计数排序有一定的局限性,它要求输入的数据,必须是有确定范围的整数序列。
主要步骤:
动图演示
/** * 计数排序 * @param array */ public static void countSort(int[] array){ int bucketLen = getMaxValue(array) + 1; int[] bucket = new int[bucketLen]; // 统计每个值出现的次数 for (int value : array) { bucket[value]++; } // 反向填充数组 int sortedIndex = 0; for (int j = 0; j < bucketLen; j++) { while (bucket[j] > 0) { array[sortedIndex++] = j; bucket[j]--; } } } /** * 获取最大值 * @param arr * @return */ private static int getMaxValue(int[] arr) { int maxValue = arr[0]; for (int value : arr) { if (maxValue < value) { maxValue = value; } } return maxValue; }
桶排序算是计数排序的一个加强版,它利用特定函数的映射关系,将属于一定范围内的数据,放到一个桶里,然后对每个桶中的数据进行排序,最后再将排序好的数据拼接起来。
主要步骤:
动图演示
/** * 桶排序 * @param arr * @param bucketSize * @return */ private static int[] bucketSort(int[] arr, int bucketSize){ if (arr.length == 0) { return arr; } int minValue = arr[0]; int maxValue = arr[0]; // 计算出最大值和最小值 for (int value : arr) { if (value < minValue) { minValue = value; } else if (value > maxValue) { maxValue = value; } } // 根据桶的长度以及数据的最大值和最小值,计算出桶的数量 int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1; int[][] buckets = new int[bucketCount][0]; // 利用映射函数将数据分配到各个桶中 for (int i = 0; i < arr.length; i++) { int index = (int) Math.floor((arr[i] - minValue) / bucketSize); // 将数据填充到指定的桶中 buckets[index] = appendBucket(buckets[index], arr[i]); } int arrIndex = 0; for (int[] bucket : buckets) { if (bucket.length <= 0) { continue; } // 对每个桶进行排序,这里使用了插入排序 InsertSort.insertSort(bucket); for (int value : bucket) { arr[arrIndex++] = value; } } return arr; } /** * 扩容,并追加数据 * * @param array * @param value */ private static int[] appendBucket(int[] array, int value) { array = Arrays.copyOf(array, array.length + 1); array[array.length - 1] = value; return array; }
基数排序是一种非比较型排序,主要逻辑时将整数按位拆分成不同的数字,然后再按照位数排序,先按低位排序,进行收集,再按高位排序,再进行收集,直到最高位。
主要步骤:
动图演示
/** * 基数排序 * @param array */ public static void radixSort(int[] array){ // 获取最高位 int maxDigit = getMaxDigit(array); int mod = 10; int dev = 1; for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) { // 考虑负数的情况,这里扩展一倍队列数,其中 [0-9]对应负数,[10-19]对应正数 (bucket + 10) int[][] counter = new int[mod * 2][0]; // 计数排序 for (int j = 0; j < array.length; j++) { int bucket = ((array[j] % mod) / dev) + mod; counter[bucket] = appendBucket(counter[bucket], array[j]); } // 反向填充数组 int pos = 0; for (int[] bucket : counter) { for (int value : bucket) { array[pos++] = value; } } } } /** * 获取最高位数 */ private static int getMaxDigit(int[] arr) { int maxValue = getMaxValue(arr); return getNumLength(maxValue); } /** * 获取最大值 * @param arr * @return */ private static int getMaxValue(int[] arr) { int maxValue = arr[0]; for (int value : arr) { if (maxValue < value) { maxValue = value; } } return maxValue; } /** * 获取整数的位数 * @param num * @return */ protected static int getNumLength(long num) { if (num == 0) { return 1; } int lenght = 0; for (long temp = num; temp != 0; temp /= 10) { lenght++; } return lenght; } /** * 扩容,并追加数据 * * @param array * @param value */ private static int[] appendBucket(int[] array, int value) { array = Arrays.copyOf(array, array.length + 1); array[array.length - 1] = value; return array; }
基数排序总结
计数排序、桶排序、基数排序这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异:
这次总结了10个经典的排序算法,也算是给自己早年偷的懒补一个补丁吧。一些常用的算法在面试中也算是一个考察方向,但是一般考察都是时间复杂度低的那几个即时间复杂度为O(nlogn)的:快速排序、堆排序、希尔排序。所以这几个要熟练掌握,起码要知道是怎样的实现逻辑(毕竟面试也有口述算法的时候)。
画图:AlgorithmMan