（2）时间复杂度：算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。去掉常数项+去低阶项+去掉最高阶系数
常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2*n)＜Ο(n!)
1.1 选择 排序
选择排序算法也是比较简单的排序算法,其思路比较直观。选择排序算法在每一步中选取最小值来重新排列,从而达到排序的目的。 选择排序算法通过选择和交换来实现排序,其排序流程如下:
1.首先从原始数组中选择最小的1个数据,将其和位于第1个位置的数据交换。
2.接着从剩下的 n-1 个数据中选择次小的 1 个数据,将其和第2个位置的数据交换。
3.然后不断重复上述过程,直到最后两个数据完成交换。至此,便完成了对原始数组的从小到大的排序。
public class Xzz {
public static void sortXz(int[] arr){
int d,e;
for(int i=0;i<arr.length-1;i++){
d=i;
for(int j=i+1;j<arr.length;j++){
if(arr[j]<arr[d]){ // 若剩余 n-(i+1) 个数据中有小于 a[i]的，则记录该元素下标
d=j;
}
if(d!=i){
e = arr[i];
arr[i] = arr[d];
arr[d] = e;
} } } }
public static void main(String[] args) {
int[] a=new int[20];
Random random=new Random();
for(int i=0;i<20;i++){
a[i]=random.nextInt(100);
}
Xzz.sortXz(a);
for(int i=0;i<a.length;i++){
System.out.printf("%d ",a[i]);
}
}
}
1.2 插入排序
1.将一组数据分成两组，分别为有序组、无序组（一般将数据第一个元素视为有序组，剩余为无序组）。
2.取出无序组第一个元素，按从后向前的顺序，与有序组的元素逐个比较，插入到有序组合适位置。
3.重复步骤 2， 直至无序组元素为空。
插入排序对小规模数据或基本有序数据比较有效。数据有序程度越高，越有效
public class Cr {
public static void InsertSort(int[] arr) {
int k=0,j ;
for(int i=1;i<arr.length;i++){
k=arr[i]; // 从无序组取出第一个元素
j=i-1; // i-1 即为有序组最后一个元素（与待插入元素相邻）的下标
// 按从后向前的顺序，将待插入元素与有序组元素逐个比较
while (j>=0&&k<arr[j]){
arr[j+1]=arr[j]; // 若不是合适位置，有序组元素向后移动
j--;
}
arr[j+1]=k; // 找到合适位置，将元素插入
}
}
public static void main(String[] args) {
int[] a=new int[20];
Random random=new Random();
for(int i=0;i<20;i++){
a[i]=random.nextInt(100);
}
Cr.InsertSort(a);
for(int i=0;i<a.length;i++){
System.out.printf("%d ",a[i]);
}
}
}
1.3 希尔排序（shell排序/缩小增量排序）
先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的），对每个子序列进行直接插入排序。然后缩减增量对子序列进行排序…，直至增量为 1 时，将整个元素序列变为有序。
希尔排序适用于大规模且无序的数据
1.假设共有 n 个元素，第一次取增量 gap = n / 2，对 gap 个元素序列进行插入排序
2.取 gap = gap / 2，对 gap 个元素序列进行插入排序
3.重复步骤 2，直至 gap = 1，将整个元素序列变为有序
public class XXee {
static final int SIZE = 20;
public static void shellSort(int[] array) {
int j, temp, k = 0;
for (int gap = array.length / 2; gap >= 1; gap /= 2) {
// 对子序列进行插入排序
for (int i = gap; i < array.length; i++) {
temp = array[i]; // 取无序组第一个元素，此元素即为待插入元素
j = i - gap; // i-gap 为有序组最后一个元素
// 按从后向前的顺序，将待插入元素与有序组元素逐个比较
while (j >= 0 && temp < array[j]) {
array[j+gap] = array[j];// 若不是合适位置，有序组元素向后移动
j -= gap;
}
array[j+gap] = temp; // 找到合适位置，将元素插入
}
System.out.print("第" + ++k + "步排序结果：");
Arrays.stream(array).mapToObj(item -> item + " ").forEach(System.out::print);
System.out.println();
}
}
public static void main(String[] args) {
int[] array = new int[SIZE];
System.out.println("排序前的数组为：");
for (int i = 0; i < SIZE; i++) {
// 产生 100~199 之间的随机数
array[i] = (int) (100 + Math.random() * 100);
System.out.printf("%d ", array[i]);
if ((i + 1) % 10 == 0)
System.out.println();
}
shellSort(array);
System.out.println("排序后的数组为：");
for (int i = 0; i < array.length; i++) {
System.out.printf("%d ", array[i]);
if ((i + 1) % 10 == 0)
System.out.println();
}
}
}
1.4 快速排序
假设有一个由若干数据组成的序列，
取第一个数据为基准数据 base，指针 i 指向第一个数据，指针 j 指向最后一个数据；
当 i < j 时：先递减 j，从后向前搜索小于 base 的数据，再递增 i ，从前向后搜索大于 base 的数据，若找到，则交换；继续递减 j，递增 i 进行同样的操作，直至 i == j
当 i == j 时：交换 base 和 array[i]，则 base 左侧的数据都小于 base，base 右侧的数据都大于base，此时一次排序结束
以 base 为界限将数据分成两个子序列，对子序列进行同样的操作，…，直到整个序列有序
array[10] = { 150 107 182 178 183 154 141 138 182 169 }
public class QuickSortDemo {
static final int SIZE = 20;
static int k = 0;
public static void quickSort(int[] array, int left, int right) {
// 数组长度为 0 或 1 时直接退出
if (array == null || left > right || (array.length - 1 <= 0))
return;
int base = array[left]; // base：基准数据
int i = left, j = right;// 让 i 指向数据最左侧，让 j 指向数据最左侧
int temp;
while (i != j) {
// 从右向左搜寻小于 base 的数据
while (array[j] >= base && i < j)
j--;
// 从左向右搜寻大于 base 的数据
while (array[i] <= base && i < j)
i++;
// 交换搜寻到的数据
if (i < j) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
// 将基准数放到中间的位置（基准数归位）
array[left] = array[i];
array[i] = base;
/*temp = array[i];
array[i] = array[left];
array[left] = temp;*/
// 一次排序结束，此时 base 左侧的数据全小于 base，右侧的数据全大于base
quickSort(array, left, i - 1); // 快排 base 左侧数据
quickSort(array, i + 1, right);// 快排 base 右侧数据
}
public static void main(String[] args) {
int[] array = new int[SIZE];
System.out.println("排序前的数组为：");
for (int i = 0; i < SIZE; i++) {
// 产生 100~199 之间的随机数
array[i] = (int) (100 + Math.random() * 100);
System.out.printf("%d ", array[i]);
}
quickSort(array, 0, array.length - 1);
System.out.println("
排序后的数组为：");
for (int i = 0; i < SIZE;