文章目录
算法的时间复杂度
⑴ 找出算法中的基本语句；
算法中执行次数最多的语句，通常是最内层循环的循环体。
⑵ 计算基本语句的执行次数的数量级；
只需保留f(n)中的最高次幂正确即可，忽略所有的低次幂和最高次幂的系数。
⑶ 用大Ο记号表示算法的时间性能。
将基本语句执行次数的数量级放入大Ο记号中。例如：
for (i=1; i<=n; i++)
x++;
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
x++;
其中第一个for循环的时间复杂度为Ο(n)，第二个for循环的时间复杂度为Ο(n2)，则整个算法的时间复杂度为Ο(n+n2)=Ο(n2)。
注、加法原则：T(n)=O(f(n))+O(g(n))=O(max(fn,gn))
常见的算法时间复杂度由小到大依次为：
Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2^n)＜Ο(n!)<O(n^n)
冒泡排序（Bubble Sort）
算法描述：
比较相邻的元素。如果第一个比第二个大，就交换它们两个；
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
针对所有的元素重复以上的步骤，除了最后一个；
重复步骤1~3，直到排序完成。
代码实现
public class Bubble {
static Random random = new Random();
static int[] arr = new int[10];
public static void main(String[] args) {
for (int i = 0; i < arr.length; i++) {
arr[i] = random.nextInt(100);
}
System.out.println("冒泡排序前的数组：" + Arrays.toString(arr));
bubbleSort();
System.out.println("冒泡排序后的数组：" + Arrays.toString(arr));
}
public static void bubbleSort(){
if (arr == null || arr.length <= 1){
return;
}
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - 1 -i; j++) {
if (arr[j] > arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
}
运行结果：
算法分析
最佳情况：T(n) = O(n) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)
稳定性：稳定。
选择排序
算法描述：
n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：
初始状态：无序区为R[1…n]，有序区为空；
第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1…i-1] 和R(i…n）。该趟排序从当前无序区中-选出关键字最
小的记录R[k]，将它与无序区的第1个记录R交换，使R[1…i]和R[i+1…n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
n-1趟结束，数组有序化了。
代码实现
public class Choice {
static Random random = new Random();
static int[] arr = new int[10];
public static void main(String[] args) {
for (int i = 0; i < arr.length; i++) {
arr[i] = random.nextInt(100);
}
System.out.println("选择排序前的数组：" + Arrays.toString(arr));
choiceSort();
System.out.println("选择排序后的数组：" + Arrays.toString(arr));
}
public static void choiceSort(){
if (arr == null || arr.length <= 1){
return;
}
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]){
min = j;
}
}
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
}
运行结果：
算法分析
最佳情况：T(n) = O(n2) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)
稳定性：不稳定。
直接插入排序
算法描述：
从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后； 重复步骤2~5。
代码实现
public class Insert {
static Random random = new Random();
static int[] arr = new int[10];
public static void main(String[] args) {
for (int i = 0; i < arr.length; i++) {
arr[i] = random.nextInt(100);
}
System.out.println("直接插入排序前的数组：" + Arrays.toString(arr));
InsertSort();
System.out.println("直接插入排序后的数组：" + Arrays.toString(arr));
}
public static void InsertSort(){
if (arr == null || arr.length <= 1){
return;
}
for (int i = 1; i < arr.length; i++) {
int insert = arr[i];
int j = i-1;
while(j >= 0 && arr[j] > insert){
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = insert;
}
}
}
运行结果：
算法分析
最佳情况：T(n) = O(n) 最坏情况：T(n) = O(n2) 平均情况：T(n) = O(n2)
快速排序
算法描述：
从数列中挑出一个元素，称为 “基准”（pivot）；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之
后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
代码实现
public class Quick {
static Random random = new Random();
static int[] arr = new int[10];
public static void main(String[] args) {
for (int i = 0; i < arr.length; i++) {
arr[i] = random.nextInt(100);
}
System.out.println("快速排序前的数组：" + Arrays.toString(arr));
QuickSort(arr,0, arr.length-1);
System.out.println("快速排序后的数组：" + Arrays.toString(arr));
}
public static void QuickSort(int[] src, int begin, int end){
if (arr == null || arr.length <= 1){
return;
}
if (begin < end){
int key = arr[begin];
int i = begin;
int j = end;
while(i<j){
while (i < j && src[j] > key){
j--;
}
if(i < j){
src[i] = src[j];
}
while (i < j && src[i] < key){
i++;
}
if (i < j){
src[j] = src[i];
}
}
src[i] = key;
QuickSort(src,begin,i-1);
QuickSort(src, i+1, end);
}
}
}
运行结果：
算法分析
最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(nlogn)
稳定性：不稳定。
希尔排序
算法描述
选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列个数k，对序列进行k 趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1
时，整个序列作为一个表来处理，表长度即为整个序列的长度。
代码实现
public class Shell {
static Random random = new Random();
static int[] arr = new int[10];
public static void main(String[] args) {
for (int i = 0; i < arr.length; i++) {
arr[i] = random.nextInt(100);
}
System.out.println("希尔排序前的数组：" + Arrays.toString(arr));
ShellSort();
System.out.println("希尔排序后的数组：" + Arrays.toString(arr));
}
public static void ShellSort(){
for (int d = arr.length/2; d > 0; d /= 2){
for (int i = d; i < arr.length; i++) {
for (int j = i - d; j >= 0; j -= d){
if (arr[j] > arr[j + d]){
int temp = arr[j];
arr[j] = arr[j + d];
arr[j + d] = temp;
}
}
}
}
}
}
运行结果
算法分析
最佳情况：T(n) = O(nlog2 n) 最坏情况：T(n) = O(nlog2 n) 平均情况：T(n) =O(nlog2n)
稳定性：不稳定。