排序算法大致分为内部排序和外部排序两种 内部排序:待排序的记录全部放到内存中进行排序,时间复杂度也就等于比较的次数 外部排序:数据量很大,内存无法容纳,需要对外存进行访问再排序,把若干段数据一次读入内存使用内部排序的方法进行排序后写入外存,再将这若干个已经排序的数据进行归并,时间复杂度等于IO(访问外存)的次数 1、冒泡算法# 交换排序。属于比较简单直观的排序算法,以升序为例(从小到大),每次比较相邻的两个元素,如果左侧元素比右侧的大,则交换两个元素的位置,每次把循环中最大的元素放在循环的最后,像冒泡一样从小到最大。 1.1 算法步骤#
1.2 时间复杂度# 总共需要比较次数(n为数组元素个数 n >= 1): O(n)=(n−1)+(n−2)+⋯+1=(n−1)∗n2取最高次幂O(n)=n2O(n)=(n−1)+(n−2)+⋯+1=(n−1)∗n2取最高次幂O(n)=n2 1.3 代码实现#public int[] bubbleSort(int[] arr) { // 外层循环,数组长度为 n,循环次数为 n-1 for (int i = 0; i < arr.length - 1; i++) { // 内层循环,循环次数为 n-1-i,找到一个最大值放在,arr[n-1-i]的位置 for (int j = 0; j < arr.length - 1 - i; j++) { // 比较相邻的两个值,把相对大的值放在数组下标大的地方 if (arr[j] > arr[j + 1]) { // swap交换 int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } return arr;} 1.4 图示# 如图,即使第二次循环已经排好序,但是程序不晓得,仍会继续循环进行排序,最后一次,只有两个元素进行排序比较,直接排序完成,排序次数 n-1。 2、快速排序# 交换排序。选择一个基准值,将数组划分两个区域,左侧的值全部比右侧的值小,然后分别对两个区域继续进行区域的划分与排序,直到排序完成。 2.1 算法步骤#
2.2 时间复杂度# 对区域划分取特殊值,假设n为2的幂,每次都将n个数平均划分,所以第一次对一整个区域进行循环n次划分2个区域,第二次对两个区域分别进行循环n2n2次,共n次,划分4个区域,第三次对4个区域分别进行循环n4n4次,共计n次,以此类推,最后一次为第log2n次,划分的每个区域仅有一个元素。即: O(n)=n∗log2nO(n)=n∗log2n 2.3 代码实现#
2.4 图示#3、直接插入排序# 插入排序。每一次把一个待排序的记录,按照值的大小,插入到有序数组的合适位置。 相当于把a[n]分割,先排序数组 a[0] ~ a[1],再 a[0] ~ a[2],直到 a[0] ~ a[n] 全部排序完成。 3.1 算法步骤#
3.2 时间复杂度# 认为第一元素已经排好序,从第二个元素开始向前比较,计算需要比较的次数: O(n)=1+2+3+⋯+n−1=(n−1)∗n2即O(n)=n2O(n)=1+2+3+⋯+n−1=(n−1)∗n2即O(n)=n2 3.3 代码实现#public static int[] insertionSort(int[] arr){ // 从第二个元素开始到最后一个元素 for (int i = 1; i < arr.length; i++) { // 向前遍历 for( int j = i ; j > 0 ; j -- ){ if( arr[j] < arr[j-1] ){ swap( arr, j , j-1 ); } else{ break; } } } return arr;}private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;} 3.4 图示#4、希尔排序# 插入排序。因为设计该算法的人叫Shell,所以叫希尔排序,又称缩小增量排序。思路上是将待排序序列分割成若干个子序列进行直接插入排序,并逐渐缩减少子序列个数,直到针对整体进行一次排序。 4.1 算法步骤#
4.2 时间复杂度# 希尔排序的时间复杂度和增量的选择有关,证明的话我是不会,最坏时间复杂度是O(n2)O(n2),当n在某个范围内时,可以达到O(n1.3)O(n1.3) 4.3 代码实现#
4.4 图示#5、简单选择排序# 选择排序。从未排序序列中查找一个最小值,然后将该值放到已排序序列的末尾位置,循环下去,直到最后一个元素。 5.1 算法步骤#
5.2 时间复杂度# 循环次数为n-1,n-2,n-3,⋯⋯,1 O(n)=(n−1)+(n−2)+⋯+1O(n)=12(n2−n)O(n)=n2O(n)=(n−1)+(n−2)+⋯+1O(n)=12(n2−n)O(n)=n2 5.3 代码实现#public static int[] selectionSort(int[] arr){ // 外层循环经过 n-1 轮比较 for (int i = 0; i < arr.length - 1; i++) { // min用来记录每次比较过程中最小值的下标 int min = i; // 0~i已经排序完成,从i向后比较查找后面序列的最小值 for (int j = i + 1; j < arr.length; j++) { if (arr[j] < arr[min]) { // 记录最小值元下标 min = j; } } // 将找到的最小值和i位置所在的值进行交换 if (i != min) { swap(arr, i ,min); } } return arr;} 5.4 图示#6、堆排序# 选择排序。将待排序列构造诚大根堆,根节点则为序列中最大元素,将该节点与最后一个值交换,把剩余的节点重新构建大根堆,继续进行交换,直到待排序列只剩下一个值。 大根堆(大顶堆):父节点一定大于两个子节点的值,即:arr[i] > arr[2i+1] && arr[i] > arr[2i+2] 将大根堆映射到数组中示例: 6.1 算法步骤#
6.2 时间复杂度#
设元素个数为 n,建堆的高度 k=log2(n+1)k=log2(n+1), 第 i 层的非叶子节点的最大操作(交换)次数为 k-i 第 i 层的节点个数为 2i−12i−1 所以第 i 层总共需要操作 (k−i)(2i−1)(k−i)(2i−1) 次,总共需要操作的次数为 S=(k−1)∗20+(k−2)∗21+(k−3)∗22+⋯+(k−(k−1))∗2k−1−1S=(k−1)∗20+(k−2)∗21+(k−3)∗22+⋯+(k−(k−1))∗2k−1−1 用 2S - S计算 S 的值: S=21+22+⋯+2k−1−(k−1)S=2k−k−1S=21+22+⋯+2k−1−(k−1)S=2k−k−1 将 k=log2(n+1)≈log2nk=log2(n+1)≈log2n 代入得 O(n)=n−log2n−1取最高项O(n)=nO(n)=n−log2n−1取最高项O(n)=n 则初始化大根堆的时间复杂度 O(n) = n 2.重新调整堆 根节点和待排序数组的最后一个元素 a[i] 交换之后,需要重新调整堆,最大调整次数 = a[i] 所在堆的层数 = log2ilog2i,总共需要调整的次数 = (n−1)(log2n)(n−1)(log2n) ,所以调整堆的时间复杂度为 O(n)=nlog2nO(n)=nlog2n 总的时间复杂度 O(n)=n+nlog2n=nlog2nO(n)=n+nlog2n=nlog2n 6.3 代码实现#
6.4 图示#初始化大根堆: 循环取堆顶元素排序:建议自己画二叉树更明晰 完整动图: 7、归并排序# 将两个及以上的有序表合并成一个有序表。以下为两路合并排序。 采用分治法,把无序数组两两分割,分割数次,然后自下至上将两个子序列进行排序,然后合并成一个有序数组,逐渐向上进行两两合并,直到合并成一个有序数组。 7.1 算法步骤#
7.2 时间复杂度# 时间复杂度 = 两个数组归并排序的时间复杂度 + 重建大根堆的时间复杂度 f(n)=2f(n2)+nf(n)=2f(n2)+n n=n2n=n2 : : f(n2)=2f(n4)+n4f(n2)=2f(n4)+n4 n=n4n=n4 : : f(n4)=2f(n8)+n8f(n4)=2f(n8)+n8 ⋯⋯ n=n2m−1n=n2m−1 : : f(n2m−1)=2f(n2m)+n2m−1f(n2m−1)=2f(n2m)+n2m−1 即:f(n)=2f(n2)+nf(n)=2f(n2)+n =2[2f(n4+n4)+n]=2[2f(n4+n4)+n] = $ 22f(\frac{n}{22}) + 2n$ =22[f(2f(n8)+n4)]+2n=22[f(2f(n8)+n4)]+2n = 23f(n23)+3n23f(n23)+3n ⋯⋯ =2mf(n2m)+mn=2mf(n2m)+mn 当数组被分割成仅剩一个元素时,此时分割为2mf(1)+mn2mf(1)+mn 即: n2m=1n2m=1 则:m=log2nm=log2n 代入得f(n)=2log2nf(1)+n∗log2n=n+nlog2nf(n)=2log2nf(1)+n∗log2n=n+nlog2n 所以归并排序的时间复杂度为: O(n)=nlog2nO(n)=nlog2n 7.3 代码实现#public static int[] MergeSort(int[] arr) { // 数组中仅有一个元素==已排序 if (arr.length < 2) { return arr; } // 分割数组的下标 int middle = arr.length / 2; // 将数组分割成arr[0] ~ arr[middle-1] 和 arr[middle] ~ arr[length-1] 两部分 int[] left = Arrays.copyOfRange(arr, 0, middle); int[] right = Arrays.copyOfRange(arr, middle, arr.length); /** * 可以拆分为 * int[] arr1 = MergeSort(left); * int[] arr2 = MergeSort(right); * 对两个分割后的数组分别再进行归并排序 * return merge(arr1, arr2); */ return merge2(MergeSort(left), MergeSort(right));}/** * 将两个数组进行合并方法 1 */protected static int[] merge1(int[] left, int[] right) { // 合并后的数组 int[] result = new int[left.length + right.length]; // i 进行计数,直到等于left或者right数组的长度 int i = 0; // 循环对left和right数组的首个元素进行比较,把小的放入result数组 // 并重新给left或right数组赋值 while (left.length > 0 && right.length > 0) { if (left[0] <= right[0]) { result[i] = left[0]; left = Arrays.copyOfRange(left, 1, left.length); } else { result[i] = right[0]; right = Arrays.copyOfRange(right, 1, right.length); } i++; } // 此时left或right数组有一个已经遍历完毕,直接把剩下的元素全部放入result数组 while (left.length > 0) { result[i] = left[0]; i++; left = Arrays.copyOfRange(left, 1, left.length); } while (right.length > 0) { result[i] = right[0]; i++; right = Arrays.copyOfRange(right, 1, right.length); } return result;}/** * 将两个数组进行合并方法 2 * 个人还是倾向于这个直观的 */private static int[] merge2(int[] left, int[] right) { // 合并后的结果 int[] result = new int[left.length + right.length]; // i,j分别用于遍历left,right数组 int i = 0; int j = 0; // count用于放入result数组时的下标计数 int count = 0; // 循环对left和right数组元素进行比较,并把小的赋值给result[count] // 直到遍历完left或者right数组 while (i < left.length && j < right.length) { if (left[i] < right[j]) { result[count] = left[i]; i++; } else { result[count] = right[j]; j++; } count++; } // 此时left或right数组有一个已经遍历完毕,直接把剩下的元素全部放入result数组 while (i < left.length) { result[count] = left[i]; i++; count++; } while (j < right.length) { result[count] = right[j]; j++; count++; } return result;} 7.4 图示#注:两个图不是同一个算法过程 8、基数排序# 取得最大整数的位数,从个位开始进行比较放入新的数组,再收集起来,此时数组按照个位有序排列,再进位进行比较收集,以此类推,直到最高位比较完成,此时数组全部有序。 8.1 算法步骤#
8.2 时间复杂度# 设n个数的最大值是k位数,需要的桶(收集元素的数组)为r个,进行一次遍历元素收集的时间复杂度为O(n+r),总的时间复杂度就是O(k(n+r)),一般来说,n >> r 且 n >> k,所以可以认为基数排序的时间复杂度为O(n),也可以认为事件复杂度为O(kn)。 8.3 代码实现#
8.4 图示#文章来自 |
|