算法概述
- 定义
排序:假设含有n个记录的序列为{R1,R2,...,Rn},其相应的关键字序列为{K1,K2,...,Kn}。将这些记录重新排序为{Ri1,Ri2,...,Rin},使得相应的关键字值满足条Ki1<=Ki2<=...<=Kin,这样的一种操作称为排序。
通常来说,排序的目的是快速查找。
- 衡量排序算法的优劣:
时间复杂度:分析关键字的比较次数和记录的移动次数
常见的算法时间复杂度由小到大依次为:Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)<…<Ο(2n)<Ο(n!)<O(nn)
空间复杂度:分析排序算法中需要多少辅助内存
一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间,它也是问题规模n的函数。
稳定性:若两个记录A和B的关键字值相等,但排序后A、B的先后次序保持不变,则称这种排序算法是稳定的。
排序算法概述
- 排序算法分类:内部排序和外部排序
内部排序:整个排序过程不需要借助于外部存储器(如磁盘等),所有排序操作都在内存中完成。
外部排序:参与排序的数据非常多,数据量非常大,计算机无法把整个排序过程放在内存中完成,必须借助于外部存储器(如磁盘)。外部排序最常见的是多路归并排序。可以认为外部排序是由多次内部排序组成。
- 十大内部排序算法
数组的排序算法很多,实现方式各不相同,时间复杂度、空间复杂度、稳定性也各不相同:
常见时间复杂度所消耗的时间从小到大排序:
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
注意,经常将以2为底n的对数简写成logn。
冒泡排序(Bubble Sort)
排序思想:
- 比较相邻的元素。如果第一个比第二个大(升序),就交换他们两个。
- 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤,除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较为止。
//冒泡 public static void bubbleSort() { int[] arr = {6, 9, 2, 9, 1, -3, 54, 45, 20}; //遍历 for (int i : arr) { System.out.print(i + "\t"); } //实现数组冒泡麦序 for (int j = 0; j < arr.length - 1; j++) { for (int i = 0; i < arr.length - 1 - j; i++) { if (arr[i] > arr[i + 1]) { int temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } } System.out.println("\n-------------------------"); for (int i : arr) { System.out.print(i + "\t"); } }标签:arr,int,复杂度,元素,算法,数组,排序 From: https://www.cnblogs.com/wdh01/p/17213056.html