选择排序、冒泡排序、插入排序，时间复杂度都是n*n，但是实际排序性能差别很大，为什么?
一、选择排序、冒泡排序、插入排序，时间复杂度都是n*n，但是实际排序性能差别很大的原因
1、每次迭代的操作数目不同
选择排序和冒泡排序在每次迭代都需要完整地遍历待排序数组中未有序部分的所有元素，而插入排序则只需要遍历已有序数组中与待插入元素相符位置之前的所有元素。
2、执行的基本操作不同
选择排序每次迭代需要一次最小值查找和一次交换操作，冒泡排序每次迭代需要多次相邻元素交换，插入排序每次迭代需要多次数据移位和一次插入操作。
3、不同排序算法对不同数据规模和分布的适应性不同
在待排序的数据规模较小时，冒泡排序或插入排序往往比选择排序更快；而在待排序的数据规模很小时，插入排序的性能甚至比其他两者都要快。此外，当有大量重复元素时，插入排序和冒泡排序都比选择排序更有优势。冒泡排序和插入排序的性能取决于数据分布的混乱程度。当数据分布混乱时，冒泡排序和插入排序的操作数较多，时间复杂度也会达到O(n^2)。但是，当数据分布相对有序时，冒泡排序和插入排序的性能会得到有效改善。在这种情况下，插入排序整体上表现更好，因为它只需要在有序数据集中查找优异插入位置（比较次数很少），并进行少量的数据移动。而冒泡排序需要每次比较相邻的元素并交换它们的位置，如果大量的数据已经有序，则时间消耗明显增加。
二、选择排序简介
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：名列前茅次从待排序的数据元素中选出最?。ɑ蜃畲螅┑囊桓鲈兀娣旁谛蛄械钠鹗嘉恢?，然后再从剩余的未排序元素中寻找到最?。ù螅┰兀缓蠓诺揭雅判虻男蛄械哪┪?。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
代码实现（JAVA版）
import java.util.Arrays;/*选择排序*/public class example2 { public static void main(String[] args) { int[] selectNums = {25, 63, 78, 45, 132, 7}; System.out.println("排序之前：" + Arrays.toString(selectNums)); selectSort(selectNums); System.out.println("排序之后：" + Arrays.toString(selectNums)); } public static void swap(int[]nums,int i,int j){ int temp=nums[i]; nums[i]=nums[j]; nums[j]=temp; } public static void selectSort(int[] nums){ for(int i=0;i三、冒泡排序简介
冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行，直到没有相邻元素需要交换，也就是说该元素列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
代码实现（JAVA版）
public static void bubbleSort(int arr[]) { for(int i =0 ; iarr[j+1]) { int temp = arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } }} 四、插入排序简介
插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了名列前茅个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。
代码实现（JAVA版）
public class Insertion{ public static void sort(Comparable[] a) { //将a[]按升序排列 int N=a.length; for (int i=1;i0&&(a[j].compareTo(a[j-1])<0);j--) { Comparable temp=a[j]; a[j]=a[j-1]; a[j-1]=temp; } } }} 延伸阅读1：时间复杂度简介
在计算机科学中，时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。
相关推荐HOT
更多>>
数据结构里的逐点插入法、排序二叉树是什么?
一、数据结构里的逐点插入法、排序二叉树逐点插入法三角剖分是一种研究方法。三角剖分≠TIN三角剖分是代数拓扑学里最基本的研究方法。 以曲面为...详情>>
2023-10-16 23:58:04
为什么链表读取慢删除却很快?
一、链表读取慢删除却很快的原因链表是一种线性数据结构，它将数据元素存储在称为节点的独立对象中，并通过指针将这些节点连接在一起。链表在读...详情>>
2023-10-16 23:09:51
递归有什么优缺点?
一、递归的优缺点递归是什么程序调用自身的编程技巧称为递归（ recursion）。递归做为一种算法在程序设计语言中广泛应用。一个过程或函数在其定...详情>>
2023-10-16 21:49:27
编写简单电脑应用程序用什么软件和语言?
一、编写简单电脑应用程序用的软件和语言编写电脑应用程序可以使用各种不同的软件和编程语言，具体选择取决于应用程序的功能和需求，以及程序员...详情>>
2023-10-16 21:01:36热门推荐
技术干货
京公网安备 11010802030320号