网站首页分辨率做多大的,国内网站建设流程,wordpress md,兰州装修公司位置一般最经典的、最常用的#xff1a;冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。那么我们如何分析一个排序算法呢#xff1f;
1-分析排序算法要点 时间复杂度#xff1a;具体是指最好情况、最坏情况、平均情况下的时间复杂… 一般最经典的、最常用的冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。那么我们如何分析一个排序算法呢
1-分析排序算法要点 时间复杂度具体是指最好情况、最坏情况、平均情况下的时间复杂度。 时间复杂度的系数常数低阶对于排序规模很小的数据在对同一阶时间复杂度的排序算法性能对比的时候我们就要把系数、常数、低阶也考虑进来。 比较次数和交换次数在分析排序算法的执行效率的时候应该把比较次数和交换或移动次数也考虑进去。 排序算法的内存消耗算法的内存消耗可以通过空间复杂度来衡量排序算法也不例外原地排序Sorted in place算法就是特指空间复杂度是O(1)的排序算法。。 排序算法的稳定性如果待排序的序列中存在值相等的元素经过排序之后相等元素之间原有的先后顺序不变。
2-冒泡-插入-选择排序
2.1-冒泡排序(Bubble Sort) 冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置重复n次就完成了n个数据的排序工作。 工作原理原始数据14,15,16,13,12,11冒泡排序的经过如下图
我们展示一下第1轮冒泡出16的过程 下图是多轮冒泡的结果 Java代码体现为了减少不必要的排序次数我们如果发现没有数据交换就可以结束排序这样可以减少循环次数。
Slf4j
public class BubbleSort {public static void main(String[] args) {int[] arr{10,8,9,15,23,6,24};sort(arr);}public static void sort(int[] arr) {int length arr.length;if (length 1) {return;}for (int i 0; i length; i) {boolean flag false;for (int j 0; j length - i - 1; j) {if (arr[j] arr[j 1]) {int temp arr[j];arr[j] arr[j 1];arr[j 1] temp;flag true;}}if(! flag){break;}}log.info(排序后数组arr{},arr);}
}1冒泡的过程只涉及相邻数据的交换操作只需要常量级的临时空间所以它的空间复杂度为O(1)是一个原地排序算法。 2在冒泡排序中只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性当有相邻的两个元素大小相等的时候我们不做交换相同大小的数据在排序前后不会改变顺序所以冒泡排序是稳定的排序算法。 3最好情况下要排序的数据已经是有序的了我们只需要进行一次冒泡操作就可以结束了所以最好情况时间复杂度是O(n)。而最坏的情况是要排序的数据刚好是倒序排列的我们需要进行n次冒泡操作所以最坏情况时间复杂度为O(n^2)。平均情况下的时间复杂度就是O(n^2)。
2.2-插入排序(Insertion Sort) 插入算法的核心思想是取未排序区间中的元素在已排序区间中找到合适的插入位置将其插入并保证已排序区间数据一直有序。重复这个过程直到未排序区间中元素为空算法结束。
原始数组14,15,16,13,12,11排序的流程图如下 Slf4j
public class InsertionSort {public static void main(String[] args) {int[] arr {10, 8, 9, 15, 23, 6, 24};sort(arr);}public static void sort(int[] arr) {int length arr.length;if (length 1) {return;}for (int i 1; i length; i) {int value arr[i];int j i - 1;for (; j 0; j--) {if (arr[j] value) {arr[j 1] arr[j];} else {break;}}arr[j1]value;}log.info(排序后数组arr{}, arr);}
}1从实现过程可以很明显地看出插入排序算法的运行并不需要额外的存储空间所以空间复杂度是O(1)也就是说这是一个原地排序算法。 2在插入排序中对于值相同的元素我们可以选择将后面出现的元素插入到前面出现元素的后面这样就可以保持原有的前后顺序不变所以插入排序是稳定的排序算法。 3最好是时间复杂度为O(n)最坏情况时间复杂度为O(n^2)平均时间复杂度为O(n^2)。
2.3-选择排序Selection Sort 选择排序算法的实现思路有点类似插入排序也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素将最小元素放到已排序区间的第一个位置。 Slf4j
public class SelectionSort {public static void main(String[] args) {int[] arr {10, 8, 9, 15, 23, 6, 24};sort(arr);}public static void sort(int[] arr) {int length arr.length;if (length 1) {return;}int minIndex;//最小值元素索引int min;//最小值元素for (int i 0; i arr.length - 1; i) {minIndex i;min arr[i];for (int j i 1; j arr.length; j) {if (min arr[j]) {min arr[j];minIndex j;}}//交换if (minIndex ! i) {arr[minIndex] arr[i];arr[i] min;}}log.info(排序后数组arr{}, arr);}
}1选择排序空间复杂度为O(1)是一种原地排序算法。 2选择排序是一种不稳定的排序算法。选择排序每次都要找剩余未排序元素中的最小值并和前面的元素交换位置这样破坏了稳定性。 3选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为O(n^2)。
3-小结 冒泡插入选择排序的平均时间复杂度都是O(n^2)三种排序算法对比结果如下图 冒泡排序和插入排序的时间复杂度都是O(n2)都是原地排序算法插入排序要比冒泡排序性能更好。因为冒泡排序的数据交换要比插入排序的数据移动要复杂冒泡排序需要3个赋值操作而插入排序只需要1个冒泡排序耗费更多的时间单位。
