常用算法复杂度分析
排序算法
1. 快速排序原理
(1)定义一个基准元素base(我这里定义的是最左面的元素定位基准元素)
(2)定义两个变量i和j,j先从右向左遍历,找到第一个比base小的数就停止,i再从左向右便利找到第一个比base大的数停止
(3)交换i和j指向的元素
(4)直到i和j指向同一个元素,将这个元素与基准元素交换
递归求解即可
2. 时间复杂度:O(nlogn)
public class Qsort { public static void main(String[] args) { int a[]= {3,4,11,2,0,9,8,5,7}; Quicksort(a,0,a.length-1); for (int i : a) { System.out.print(i+" "); } } private static void Quicksort(int[] a, int left, int right) { if(left>right) return; int i=left; int j=right; int base=a[left]; while(i!=j) { while(a[j]>=base&&i<j) j--; while(a[i]<=base&&i<j) i++; int temp = a[i]; a[i]= a[j]; a[j]= temp; } a[left]=a[i]; a[i]=base; Quicksort(a,left,i-1); Quicksort(a,i+1,right); } }
原文链接:
https://www.cnblogs.com/minkaihui/p/4077888.html
https://www.cnblogs.com/flyingdreams/p/11161157.html
https://blog.csdn.net/liang_gu/article/details/80627548
标签: 算法与数据结构